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

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

　　報(bào)  告 人：Nick Higham

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

　　地　   點(diǎn)：中關(guān)村校區(qū)研究生樓302

　　主辦單位：研究生院、數(shù)學(xué)學(xué)院

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

【主講人簡介】

  

"Nick Higham, 1985年獲得曼徹斯特大學(xué)數(shù)值分析博士學(xué)位. 現(xiàn)任英國曼徹斯特大學(xué)教授, 是世界著名的數(shù)值分析專家. 英國皇家學(xué)院院士(2007), 美國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)(SIAM)會(huì)士（2009）,，歐洲科學(xué)院院士（2016). 曾任SIAM主席(2017-2018). 以對(duì)數(shù)值算法的精度和穩(wěn)定性方面的主要工作著稱. 曾獲多個(gè)獎(jiǎng)項(xiàng),，包括Alston S. Householder獎(jiǎng)，1988 Leslie Fox 獎(jiǎng),，1999 Junior Whitehead 獎(jiǎng),，Royal Society Wolfson Research Merit 獎(jiǎng)及2008 Fr?hlich獎(jiǎng). 著有《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èi)容簡介（中文）

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

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

"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”.

"