擾動(dòng)誤差分析.doc

第2章 線性代數(shù)方程組數(shù)值解法I：直接法考慮方程組 (非奇異， 且 ) (2.6.1)設(shè)有誤差 有誤差，則因此引起解有誤差，即有擾動(dòng)方程組 現(xiàn)在來(lái)研究如何通過(guò)和對(duì)的影響作出估計(jì)。定理2.6.1 設(shè) 方程組(2.6.1)中分別有擾動(dòng)，因而解向量有誤差;又足夠小，使得 ，則有誤差估計(jì)式 證明 由 兩邊取范數(shù)有得到 得到 又注意到有 從而得到 ，故上述不等式左邊乘以，右邊圓括號(hào)第一項(xiàng)乘以，第二項(xiàng)乘以，并從括號(hào)中提出，則得(2.6.3)定理的結(jié)果實(shí)際包含兩種特殊情形：(1) A精確，即 ，有擾動(dòng)，從而 (2) 有擾動(dòng)，精確，即，這時(shí) 當(dāng)很小時(shí)，上式可近似表示為 2條件數(shù)與病態(tài)方程組定義 2.6.1 設(shè)為非奇異矩陣，稱數(shù) 即 為矩陣的條件數(shù)。矩陣的條件數(shù)的一些基本性質(zhì)：(1) 任何非奇異矩陣，對(duì)任一算子范數(shù)均有 (2) 根據(jù)定義 ,可得 (3) 若 為正交陣，即，則 又非奇異，則(4)設(shè) 與為按模最大和最小的特征值，則 特別地，若（即A對(duì)稱），則 若對(duì)稱正定，則 證明 略定理 2.6.2 （事后誤差估計(jì)）設(shè)方程組 ,非奇異，是精確解，是近似解，剩余向量 ,則有估計(jì)式 證明： 因，得 ，從而，于是，又由 ，于是得估計(jì)式右端 類似地，由上述 ，得，或 ，由 得，綜合兩式得估計(jì)式兩端 例 2.6.13事后誤差估計(jì)定理 2.6.2 設(shè) 方程組，非奇異，非奇異，是精確解，是近似解，剩余向量 ,則 有估計(jì)式 例題講解2例題2.1 對(duì)方程組Ax=b, A非奇異不一定能作順序Gauss消去過(guò)程，或者說(shuō)，A非奇異不一定有LU分解。證 這類命題只需舉一個(gè)反例即可。反例要盡可能簡(jiǎn)單，這里可考慮2階、元素為1或0。構(gòu)造反例一般要經(jīng)過(guò)多次“失敗-修正”過(guò)程?？紤]A= ，易見(jiàn)A非奇異。顯然，順序Gauss消去過(guò)程的第1步就不能進(jìn)行。從LU分解來(lái)看，設(shè)有A=LU分解，則有=于是有b=0和ab=1同時(shí)成立，這就自相矛盾了。例題2.2 設(shè)方程組 =試手算（或輔以計(jì)算器）分別用 （1）順序Guass消去法 （2）列主元Gauss消去法（3）直接三角分解法求解，要求計(jì)算中取4位有效數(shù)字，最后結(jié)果舍入成3位有效數(shù)字。上述方程組用4位浮點(diǎn)數(shù)進(jìn)行計(jì)算而舍入為3位有效數(shù)字的精確解為： 解 （1）順序Gauss消去過(guò)程計(jì)算有 第1步消元 第2步消元 回代過(guò)程求解并舍入得 （2）列主元Gauss消去過(guò)程計(jì)算有 選主元換行 第1步消元 選主元，仍為 第2步消元 回代過(guò)程求解并舍入 （3）令A(yù)=LU，用Doolittle分解計(jì)算得 由Ly=b 解得 有Ux=y 解得 與精確解比較可見(jiàn)，列主元Gauss消去法的解精確度最高；其他兩種方法的解精確度較差，但彼此接近（這正好符合兩種方法實(shí)質(zhì)是一樣的情況）。例題2.3 Gauss消去法的一種自然而又簡(jiǎn)單的改進(jìn)是所謂Gauss-Jordan消去法。先考慮順序Gauss消去法過(guò)程的情形。它只是把a(bǔ)這一列中a下面的元素消為0，而Gauss-Jordan消去過(guò)程則把a(bǔ)這一列元素的a以外全部消去為0，并且約化a=1。為此，需進(jìn)行n步消元，第n列也消為只剩下一個(gè)元素1，其余均為0（因此，0在這里也是必要的）。這樣一來(lái)，不用回代過(guò)程，方程組的解就在b的位置上?，F(xiàn)在依據(jù)上述導(dǎo)引，做（1） 試用Gauss-Jordan消去法解方程組 =（2） 試給出Gauss-Jordan算法的核心部分。（3） 由上述兩點(diǎn)能得出什么思考？解（1）用增廣矩陣的演變來(lái)描述求解過(guò)程于是有x=（2，2，3）。 （2）Gauss-Jordan消去法算法的核心部分為： 對(duì)k=1,2,，n，做 a(j=k，k+1，n，n+1) 對(duì)k=1，2，nik,做 a a-aa(j=k+1,n,n+1) 輸出解x=a(i=1,2,n)（4） 從上述做法可引發(fā)如下思考：Gauss-Jordan消去過(guò)程自然也可考慮加上選主元和換行的技巧；就計(jì)算量而言，Gauss-Jordan消去過(guò)程顯然要大（可推導(dǎo)其乘除運(yùn)算次數(shù)為級(jí)，而順序Gauss消去過(guò)程乘除運(yùn)算次數(shù)為級(jí)）。因此，用Gauss-Jordan消去法解方程組并不經(jīng)濟(jì)。但它有什么用途呢？這又引出一個(gè)新的思考。例題2.4設(shè)LR為非奇異下三角陣，試（） 寫(xiě)出求解方程組Lx=的計(jì)算公式；（） 統(tǒng)計(jì)上述求解過(guò)程的乘除法次數(shù)；（） 給出求L的計(jì)算公式。解（）這是解下三角方程組的遞推公式：（）乘除法運(yùn)算，第一式有次，第二次=2時(shí)有2次，=時(shí)有n次，故上述公式的乘除運(yùn)算次數(shù)有=/2 (次)（）因L非奇異，存在，且由矩陣知識(shí)知也為下三角陣，記由，即考慮I的對(duì)角線元素，顯然有于是得?？紤]I對(duì)角線以下的元素，即對(duì)，則有于是得例題2.5設(shè)A=（aij）Rn*n 對(duì)稱，其順序主子式i0(i=1,2,n),試（1） 證明分解A=LDLT存在唯一，其中L為單位下三角陣，D為對(duì)角陣；（2） 寫(xiě)出利用此分解求解方程組Ax=b的步驟（這稱為改進(jìn)的平方根法）；（3） 用改進(jìn)的平方跟法解方程組解 （1）由A的順序主子式不為零，故存在唯一分解式A=LU，L為單位下三角陣，U為上三角陣。改寫(xiě)A=LU=LDU0 ，D為對(duì)角陣，U0為單位上三角陣。由A對(duì)稱，有A=AT=（LDU0）T=（DLT），又由分解的唯一性即得=L或U0=LT，于是代入可得A=LU=LDU0=LDLT存在唯一。（2）將A=LDLT代入Ax=b得LDLTx=b，令DLTx=y（即LTx=D-1y），則Ly=b，改進(jìn)平方根法如下：1） 將A直接分解為A=LDLT，即求出L，D；2） 求解下三角方程組Ly=b，得y；3） 求解上三角方程組LTx=D-1y，得x。（3）令A(yù)=LDLT由矩陣乘法并對(duì)比等式兩邊得 d3=2/3解Ly=b即 得y=解LTx=D-1y即得x=（1，-1，2）T可見(jiàn)改進(jìn)平方根法比原始平方根法避免了開(kāi)方運(yùn)算；另一方面，改進(jìn)平方根法對(duì)滿足LU分解條件的對(duì)稱矩陣（不一定要正定）都適用。例題2.6 已知方程組Ax=b的系數(shù)矩陣形如：A=其中A的n-1階、主子距陣，*為其實(shí)數(shù)，。試設(shè)計(jì)一個(gè)求解上述方程組基于追趕的解決方案解 把A記為A=其中Bn-1為A的n-1階（對(duì)三角型）主子距陣，V，UR. 對(duì)用追趕法可作三角分解=P-Q再對(duì)A作三角分解，A=其中ZR(N-1)由下三角方程組Pz=v求出，WR(N-1)由方程組Q=uT(即下三角方程組QtW=U)求出， 由+=算出。由此，求解上述方程組的解決方案如下：（1）對(duì)用追趕法求出P，Q；（2）解下三角方程組Pz=v,求出z；（3）解下三角方程組QtW=U求出W；（4）計(jì)算=-z;（5）前推解下三角方程組y=b求出y;（6）回代解上三角方程組x=y求出x；例題2.7 設(shè)三對(duì)角方程組Ax=b,其中A= x= d=(1) 試建立A的順序主子式(k=1,2,n)的逆推公式。(2) 試設(shè)計(jì)求解上述三對(duì)角方程組的另一種有別于一般追趕法(基于LU分解)的新算法。解 補(bǔ)充記=1，則顯然有 = =一般地，猜想 =(k=3,4,n)用歸納法證明：當(dāng)k=2時(shí)，上式成立。現(xiàn)假設(shè)有=則由=可知上述猜想成立。綜上所述，可得遞推公式：(2)由Ax=d的第一個(gè)方程可得 (1)即得由表示的關(guān)系式。將它代入第二個(gè)方程，又可得由表示的關(guān)系式如此繼續(xù)代入，直到第個(gè)方程，于是有如下形式的關(guān)系式 (k=2,3, ) (2)其中和待定?，F(xiàn)將形式如(2)的關(guān)系式代入Ax=d的第k(k=2,3, )個(gè)方程，則有 整理可得 (k=2,3, ) (3)與關(guān)系式(2)比較得 (k=2,3, ) (4)注意到方程組中的記號(hào)，令，。由(4)中取k=1,可得，代入(1)得，可見(jiàn)(2)式對(duì)k=1也成立；又由(4)中取k=n,則可得，而由于方程組Ax=d的第n個(gè)方程可以寫(xiě)成，其中，從而上述的代入可直至第n個(gè)方程，也就是說(shuō)(2)和(3)式對(duì)也成立，于是有。綜上所述，可得解三對(duì)角方程組的新算法如下：例題2.8 證明下列兩個(gè)命題(其中均為算子范數(shù))：(1) 設(shè)B且，則 IB非奇異； 。(2)設(shè)非奇異，奇異，則 證明 (1)這個(gè)命題通常被作為矩陣范數(shù)和譜半徑理論中的一個(gè)通用定理，它與本章2.6節(jié)提供的定理2.61和定理2.62組成最基本的3個(gè)定理?，F(xiàn)用反證法證明命題(1)。若IB奇異，則齊次方程組(IB)x=0 有非零解，且，于是有和。即有。