?????????????????????????????????????????????????? 穩(wěn)定性是數(shù)值分析的一個(gè)基本問題。

????????????????????????????????????????????????????????????????????????????????????????????????? --L N. Trefethen?

?

????? 一個(gè)問題定義為由數(shù)據(jù)的向量空間 X 到解空間 Y 的一個(gè)函數(shù) f:X->Y。相應(yīng)地，一個(gè)算法可以看成是兩個(gè)相同空間之間的另外一個(gè)映射 f{bar}:X->Y。注意，前者大部分情況下是一個(gè)連續(xù)系統(tǒng)，而由于計(jì)算機(jī)浮點(diǎn)數(shù)表示的原因后者是離散系統(tǒng)（即里面表示的數(shù)字是可數(shù)的，而針對(duì)浮點(diǎn)數(shù)而言，它不僅可數(shù)，而且是有限個(gè)數(shù)的）。離散系統(tǒng)要表達(dá)出連續(xù)系統(tǒng)必然要進(jìn)行舍入。因而，f^{bar}的結(jié)果勢(shì)必要受到舍入誤差的影響。數(shù)值穩(wěn)定性要解決的是一個(gè)算法，是否能夠使用離散系統(tǒng)取得“正確答案”[1]。

????? 顯然，一個(gè)好的算法應(yīng)該保證對(duì)于給定的 x，考慮計(jì)算的相對(duì)誤差(||f(x)-f{bar}(x)||)/||f(x)||，自然地，我們期望相對(duì)誤差很小，由于計(jì)算機(jī)浮點(diǎn)數(shù)精度的限制，它有個(gè)界限，不妨記作e_{mach}，如果對(duì)每個(gè)x，有(||f(x)-f{bar}(x)||)/||f(x)|| = O(e_{mach})，我們就可以說算法 f{bar} 對(duì)問題 f 是準(zhǔn)確的。進(jìn)一步地，由于?f{bar} 的定義域是離散的，如果對(duì)于每個(gè)x，(||f(x)-f{bar}(x{bar})||)/||f(x)|| = O(e_{mach})，對(duì)某些滿足||x-x{bar}||/||x{bar}||的x成立，則說算法?f{bar}是穩(wěn)定的。另外，如果f{bar}(x{bar})=f(x)對(duì)于滿足||x-x{bar}||/||x{bar}||=O(eps_{mach})的x成立，則說算法是向后穩(wěn)定的。值得注意的是，有些算法是穩(wěn)定的但不是向后穩(wěn)定的，如計(jì)算sin(x)或cos(x)。給出這么多鋪墊，涉及到的符號(hào)和術(shù)語也很多，連我自己都覺得有些繞，如果只是了解大概內(nèi)容，上面的內(nèi)容可以忽略，而直觀的解釋參見下面敘述的數(shù)值例子。

????? 假設(shè)一個(gè)算法向后穩(wěn)定，且關(guān)于問題的條件數(shù)較小的話，那么可以得到準(zhǔn)確的結(jié)果。這個(gè)結(jié)論由定理保證：假設(shè)一個(gè)向后穩(wěn)定的算法在具有條件數(shù)k的問題f:X->Y，則相對(duì)誤差滿足：||f{bar}(x)-f(x)||/||f(x)|| = O(k*eps_{mach})。

????? 實(shí)踐已經(jīng)證明，數(shù)值代數(shù)的大多數(shù)算法而言，向前誤差分析比起向后誤差分析更難于實(shí)施（注1）。除此之外，很多時(shí)候，向后誤差分析能更合理地反映出算法的誤差。給出了一個(gè)數(shù)值例子[1]，關(guān)于一個(gè)隨機(jī)矩陣Q和R（注2），然后計(jì)算它們的乘積，不妨記作A，使用Householder三角化方法[2]對(duì)它進(jìn)行QR分解，得到數(shù)值解Q1和R1，接著分析數(shù)值解和理想解之間的誤差，結(jié)果表明數(shù)值的結(jié)果僅有2位或者3位有效數(shù)字（考慮相對(duì)誤差），而實(shí)際計(jì)算過程中采用double型浮點(diǎn)數(shù)（即有16位有效數(shù)字）。而數(shù)值解的兩個(gè)矩陣的乘積Q1*R1和矩陣A之間的誤差能夠達(dá)到15位的有效數(shù)字。另外，如果對(duì)Q和R進(jìn)行微小擾動(dòng)得到Q2和R2，兩者的乘積Q2*R2和A之間的相對(duì)誤差卻僅僅能夠達(dá)到了3位有效數(shù)字。從結(jié)果上來看，Q2（或R2）比Q1（或R1）更接近于Q（或R），但是乘積Q2*R2卻比乘積Q1*R1更接近于A（Q1和R1中的誤差被Wilkinson稱為“魔鬼相關(guān)”的）。這個(gè)例子表明，使用向后誤差分析比向前誤差分析更合理。

????? 關(guān)于向后穩(wěn)定性的兩點(diǎn)結(jié)論：

????? 一，Householder三角形化以及相應(yīng)的使用它來進(jìn)行QR因子分解求解線性方程組Ax=b向后誤差穩(wěn)定的，前者用數(shù)學(xué)語言表達(dá)出來的形式為：令矩陣A的QR因子分解是由Householder三角形化進(jìn)行數(shù)值計(jì)算得到因子Q1和R1，則有Q1*R1=A+dA， ||dA||/||A||=O(eps_{mach})對(duì)某個(gè)dA成立。

????? 二，關(guān)于矩陣特征值有如下的Weyl定理：設(shè) A 和 E 是n*n階對(duì)稱陣，設(shè) alpha_1>=alpha_2>=...>=alpha_n 是 A 的特征值，而 alpha_{bar}_1>=alpha_{bar}_2>=...alpha_{bar}_n 是 A_{bar}=A+E 的特征值，則 |alpha_i - alpha_{bar}_i|<=||E||_2。雖然該定理是向前誤差分析的結(jié)果，但是常常利用該定理可以確定QR迭代法（向后誤差穩(wěn)定）算法計(jì)算得到的數(shù)值特征值的誤差界[3]。

???? 注1：一般而言，大的向前誤差可能是一個(gè)病態(tài)問題或者是一個(gè)不穩(wěn)定算法的結(jié)果。

???? 注2：作為一個(gè)法則，隨機(jī)三角形矩陣的列空間序列作為矩陣元素的函數(shù)是極端病態(tài)的。

????

參考文獻(xiàn)：

???? [1] 數(shù)值線性代數(shù) Chap14-17，L N. Trefethen，David Bau, lll 著，陸金甫，關(guān)治譯，人民郵電出版社，2006年

???? [2] 矩陣計(jì)算（第三版），Gene H.Golub，Charles F.Van Loan 著，袁亞湘等譯，人民郵電出版社，2011年

???? [3] 應(yīng)用數(shù)值線性代數(shù) Chap5，J W. Demmel 著，王國榮譯，人民郵電出版社，2007年????

???

作者：caicailiu 出處：http://www.cnblogs.com/liuyc/? 歡迎轉(zhuǎn)載或分享，但請(qǐng)務(wù)必聲明文章出處。

轉(zhuǎn)載于:https://www.cnblogs.com/liuyc/p/6240767.html

總結(jié)

以上是生活随笔為你收集整理的数值分析之数值稳定性篇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。