數值計算方法第七章解線性方程組的數值方法華長生制作1

7.1引言

7.2Gauss消去法第七章解線性方程組的數值方法7.3選主元的Gauss消去法

7.4矩陣的三角分解

7.5向量和矩陣的范數

7.6解線性方程組的迭代法

7.7病態方程組和迭代改善法華長生制作2

7.5向量及矩陣的范數"范數"是對向量和矩陣的一種度量,實際上是二維和三維向量長度概念的一種推廣數域:數的集合,對加法和乘法封閉線性空間:可簡化為向量的集合,對向量的加法和數量乘法封閉,二維向量和三維向量都可以度量其大小和長度高維向量的"長度"能否定義呢?也稱為向量空間華長生制作3定義1.一、向量和矩陣的范數華長生制作4--------(1)--------(2)--------(3)華長生制作5顯然并且由于--------(4)華長生制作6例4.求下列向量的各種常用范數解:定義（向量序列的極限）設為向量序列，記及如果n個數列極限存在且則稱收斂于,記為華長生制作7定理6

設是上任一向量范數,則是的分量的連續函數。定理7設是上向量的任意兩種范數，則存在常數,使得對一切有……（5.1）定理8設是中一上向量序列，且則華長生制作8定義3.華長生制作9例5.不難驗證其滿足定義2的4個條件稱為Frobenius范數,簡稱F-范數而且可以驗證tr為矩陣的跡--------(5)--------(6)類似向量的2-范數華長生制作10定義4.--------(7)簡稱為從屬范數或算子范數華長生制作11顯然，由定義不難推出定義5.由(8)式,可知算子范數和其對應的向量范數是相容的--------(8)--------(9)華長生制作12根據向量的常用范數可以得到常用的矩陣算子范數--------(10)--------(11)--------(12)華長生制作13例6.求矩陣A的各種常用范數解:由于華長生制作14特征方程為華長生制作15容易計算計算較復雜對矩陣元素的變化比較敏感不是從屬范數較少使用使用最廣泛性質較好華長生制作16

7.6解線性方程組的迭代法在用直接法解線性方程組時要對系數矩陣不斷變換如果方程組的階數很高,則運算量將會很大并且大量占用計算機資源因此對線性方程組要求找尋更經濟、適用的數值解法--------(1)華長生制作17如果能將線性方程組(1)變換為--------(2)顯然,(1)式和(2)式同解,我們稱(1)(2)等價對線性方程組(2),采用以下步驟:依此類推華長生制作18--------(3)這種方式就稱為迭代法,以上過程稱為迭代過程迭代法產生一個序列如果其極限存在,即則稱迭代法收斂,否則稱為發散華長生制作19一、簡單迭代法(基本迭代法)設線性方程組(1)的一般形式為華長生制作20依此類推,線性方程組(1)可化為-----(4)華長生制作21--------(5)對(4)作迭代過程則(5)式轉化為矩陣形式--------(6)華長生制作22令華長生制作23故迭代過程(6)化為等價線性方程組為--------(7)稱(5)式和(7)式為解線性方程組(1)的Jacobi迭代法(J法)華長生制作24例6.用Jacobi迭代法求解方程組,誤差不超過1e-4解:華長生制作25華長生制作26華長生制作27依此類推,得方程組滿足精度的解為x12迭代次數為12次x4=3.02411.94780.9205d=0.1573x5=3.00031.98401.0010d=0.0914x6=2.99382.00001.0038d=0.0175x7=2.99902.00261.0031d=0.0059x8=3.00022.00060.9998d=0.0040x9=3.00031.99990.9997d=7.3612e-004x10=3.00001.99990.9999d=2.8918e-004x11=3.00002.00001.0000d=1.7669e-004x12=3.00002.00001.0000d=3.0647e-005華長生制作28分析Jacobi迭代法(5)的迭代過程,將(5)式細化華長生制作29考慮迭代式(7)即將上式改為--------(8)華長生制作30--------(9)上式稱為Gauss-Seidel迭代法,簡稱G-S法利用(8)式展開Gauss-Seidel迭代法也可表示成華長生制作31華長生制作32例7.用Gauss-Seidel迭代法求解例6.解:通過迭代,至第7步得到滿足精度的解x7華長生制作33x1=2.50002.09091.2273d=3.4825x2=2.97732.02891.0041d=0.5305x3=3.00981.99680.9959d=0.0465x4=2.99981.99971.0002d=0.0112x5=2.99982.00011.0001d=3.9735e-004x6=3.00002.00001.0000d=1.9555e-004x7=3.00002.00001.0000d=1.1576e-005從例6和例7可以看出,Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要高.高斯-賽得爾迭代法與雅可比迭代法都具有算式簡單、易在計算機上實現等優點,且每迭代依次一次秩只需計算一次矩陣與向量的乘法.且前者比后者需要的存儲單元要少.對于給定的矩陣線性方程組,用兩種求解時,可能都收斂,也可能一個收斂另一個不收斂.在都收斂的情況下,有時前者收斂快,有時后者收斂快.二者統稱為簡單迭代法.華長生制作34二.解線性方程組的超松弛迭代法

逐次超松弛迭代法(SuccessiveOverRelaxationMethod),簡稱SOR方法是G－S迭代法的一種加速方法，是解大型稀疏矩陣方程組的有效方法之一，它有著廣泛的應用。設有方程組為非奇異矩陣.選取分裂矩陣為帶參數的下三角陣其中為可選擇的松弛因子。于是可得迭代矩陣華長生制作35于是得到解的逐次超松弛迭代公式：……（6.11）其中超松弛迭代法（SOR）的分量形式：設已知第k次近似及第次近似的分量,首先用G－S迭代法計算一個輔助量……（6.12）華長生制作36再由的第個分量與加權平均,定義……（6.13）將(6.12)代入(6.13),得到解的SOR方法：……（6.14）華長生制作37或寫成在SOR方法(6.14)中取就是G－S迭代法.當松弛因子滿足時,迭代法(6.14)稱為低松弛方法;當時迭代法(6.14)稱為超松弛方法。

SOR方法每迭代一次主要計算量時計算一次矩陣乘向量.計算時可用迭代,這時SOR方法只需一組工作單元存放來控制或也可用剩余向量來控制迭代終止。華長生制作38定理12.三、迭代法的收斂條件與誤差估計定義5.--------(9)定理10.矩陣A的譜半徑不超過矩陣A的任何一種算子范數.定理11.華長生制作39定理13.--------(10)--------(11)證明:(1)先證明X=BX+f有唯一解.由定理4,B的特征值的模下證迭代序列收斂于唯一解.因為華長生制作40--------(12)(2)由范樹的性質及上面的不等式(12)因此,結論成立.華長生制作41(3)由不等式(10)及因此,結論成立.于是華長生制作42(10)可以用來估計迭代法的精度,理論上只要在計算時,迭代終止的時間可以用上式判別另外,給出系數矩陣對角占優線性方程組的一個結論定理6.定理7.若方程組AX=b的系數矩陣為對稱正定矩陣,則對任意初始向量X(0),高斯—賽德爾迭代法收斂.定理8.迭代過程X(k+1)=BX(k)+f對任意初始向量X(0)收斂的充分必要條件是迭代局陣的譜半徑p(B)<1;且當p(B)<1時,迭代矩陣譜半徑越小,收斂速度越快.華長生制作43例8試考察用Jacobi方法,G－S迭代法解下面方程組的收斂解由于為嚴格對角占優陣，于是由定理6可知解方程組Ax=b的Jacobi迭代法，G－S迭代法均收斂。華長生制作44

7.7病態方程組和迭代法改善法判斷一個計算方法的好壞,可用算法的穩定性、解的精確程度以及計算量、存儲量的大小等來衡量。然而，同一方法用于不同問題，效果卻可以相差很遠，這就涉及到問題本身的狀態。

本節在分析方程組的初始數據A、b的小擾動（誤差）對解的影響的基上，給出方程組“病態”、”良態“的概念及其衡量標準，并介紹判斷近似解可靠性以及提高計算結果精度的方法。華長生制作45引例

設有方程組其解現考慮常數項有微小的誤差，即其中，得到一個擾動方程組其解為

此例說明,方程組常數項分量只有微小變化(1/100),而方程組的解有較大的變化.也就是說這個方程組的解對于問題的數據b很靈敏.這樣的方程組就是病態方程組。華長生制作46定義.7.7.1病態方程組及誤差分析簡介即有--------(15)華長生制作47--------(16)--------(17)--------(18)所以又因為可得(16)和(17)兩式相乘,得相對誤差華長生制作48(18)式表明,由常數項產生的誤差,最多可將解的相對誤差放大倍所以華長生制作49定義7.--------(20)--------(19)華長生制作50顯然即任意方陣的條件數必不小于1根據算子范數的不同也有不同的條件數:華長生制作51--------(18)--------(19)根據定義7的定義,(18)式和(19)式可表示為華長生制作52定理17

（b擾動對解的影響）則有……（7.4）華長生制作537.7.2迭代改善(可靠性判別)法定理19.--------(21)定理18

（A擾動對解的影響）華長生制作54設為用高斯法求得的計算解，計算剩余向量--------(22)求解--------(23)且計算--------(24).顯然,如果計算及沒有誤差,則是方程組的精確解。事實上，