【百家大講堂】第186期：一種新的概率舍入誤差分析方法

　　講座題目：一種新的概率舍入誤差分析方法

　　報  告 人：Nick Higham

　　時　   間：2019年4月24日（周三）15:30-16:30

　　地　   點：中關村校區研究生樓302

　　主辦單位：研究生院、數學學院

　　報名方式：登錄北京理工大學微信企業號---第二課堂---課程報名中選擇“【百家大講堂】第186期：一種新的概率舍入誤差分析方法”

【主講人簡介】

  

"Nick Higham, 1985年獲得曼徹斯特大學數值分析博士學位. 現任英國曼徹斯特大學教授, 是世界著名的數值分析專家. 英國皇家學院院士(2007), 美國工業與應用數學學會(SIAM)會士（2009），歐洲科學院院士（2016). 曾任SIAM主席(2017-2018). 以對數值算法的精度和穩定性方面的主要工作著稱. 曾獲多個獎項，包括Alston S. Householder獎，1988 Leslie Fox 獎，1999 Junior Whitehead 獎，Royal Society Wolfson Research Merit 獎及2008 Fr?hlich獎. 著有《Functions of Matrices: Theory and Computation》《Accuracy and Stability of Numerical Algorithms》《Handbook of Writing for the Mathematical Sciences》，《MATLAB Guide》等書. 

"

"Nick Higham, obtained Ph.D. of numerical analysis in University of Manchester in 1985. Now he is a professor of Manchester and a world-renowned expert in numerical analysis. Fellow of the Royal Society(2007), Fellow of SIAM(2009), Member of Academia Europaea(2016).Chairman of SIAM in 2017-2018. He is well known for his research on the accuracy and stability of numerical algorithms. Honours include the Alston S. Householder Award VI,the 1988 Leslie Fox Prize, a 1999 Junior Whitehead Prize, Royal Society Wolfson Research Merit Prize, and the 2008 Fr?hlich Prize. Higham is also author of Functions of Matrices: Theory and Computation, Accuracy and Stability of Numerical Algorithms, Handbook of Writing for the Mathematical Sciences，MATLAB Guide and so on."

【講座信息】

內容簡介（中文）

"對于問題大小n和單位舍入u，數值線性代數中的傳統舍入誤差分析導致涉及常數/gamma^{n} = nu /（1-nu）的后向誤差界限。鑒于大規模且可能低精度的計算，這樣的界限可能難以提供任何有用的信息。我們開發了一種新的概率舍入誤差分析，可應用于各種算法。通過使用集中不等式并對舍入誤差進行概率假設，我們證明了在幾個核心線性代數計算中，/gamma^{n}可以用松弛常數/widetilde/gamma}^{n}代替。

與/sqrt{nlogn}u成比例，其概率下限為獨立于n的數量。使用n而不是/gamma^{n}，新常量/ widetilde/gamma}^{n}增長得慢得多。我們的結果有三個關鍵特征：它們是向后誤差范圍;它們是準確的，而不是第一順序;并且它們對任何n都有效，這與通過應用中心極限定理獲得的結果不同，中心極限定理僅適用于n/to/infty。我們提供的數值實驗表明，對于隨機矩陣和現實矩陣，邊界可以比標準的確定性邊界小得多，并且可以用n進行正確的漸近增長。我們還確定了兩種特殊情況，其中分析所依據的假設無效且邊界不成立。我們的分析首次為經驗法則提供了一個嚴格的基礎：“由于舍入誤差傳播的統計效應，人們可以將誤差的平方根保持不變”。"

"Traditional rounding error analysis in numerical linear algebra leads to backward error bounds involving the constant /gamma^{n} = nu/(1-nu) , for a problem size n and unit roundoff u. In the light of large-scale and possibly low-precision computations, such bounds can struggle to provide any useful information. We develop a new probabilistic rounding error analysis that can be applied to a wide range of algorithms. By using a concentration inequality and making probabilistic assumptions about the rounding errors, we show that in several core linear algebra computations gamma^{n} can be replaced by a relaxed constant /widetilde/gamma}^{n}

proportional to /sqrt{nlogn}u with a probability bounded below by a quantity independent of n. The new constant /widetilde/gamma}^{n} grows much more slowly with n than gamma^{n}. Our results have three key features: they are backward error bounds; they are exact, not first order; and they are valid for any n, unlike results obtained by applying the central limit theorem, which apply only as n/to/infty. We provide numerical experiments that show that for both random and real-life matrices the bounds can be much smaller than the standard deterministic bounds and can have the correct asymptotic growth with n. We also identify two special situations in which the assumptions underlying the analysis are not valid and the bounds do not hold. Our analysis provides, for the first time, a rigorous foundation for the rule of thumb that “one can take the square root of an error constant because of statistical effects in rounding error propagation”.

"