1、線性方程組的解法線性方程組的解法(ji f)第一頁，共39頁。線性方程組的解法在計算數學中占有極其重要線性方程組的解法在計算數學中占有極其重要的地位的地位(dwi)。線性方程組的解法大致分為迭代法與直接法兩線性方程組的解法大致分為迭代法與直接法兩大類大類雅可比雅可比(Jacobi)迭代法迭代法舉例說明雅可比迭代法的基本思路舉例說明雅可比迭代法的基本思路 131581079321321321xxxxxxxxx例例4.1特點特點:系數系數(xsh)矩矩陣主對角元均不為陣主對角元均不為零零第1頁/共39頁第二頁，共39頁。 15/ )13(10/ )8(9/ )7(213312321xxxxxxxx

2、x取迭代取迭代(di di)初值初值x1(0) =0， x2(0) =0， x3(0) =0將方程改寫成如下等價將方程改寫成如下等價(dngji)形式形式據此建立迭代據此建立迭代(di di)公式公式 15/ )13(10/ )8(9/ )7()()()1()()()1()()()1(213312321kkkkkkkkkxxxxxxxxx第2頁/共39頁第三頁，共39頁。 x(0) 0 0 0 x(1) 0.7778 0.8000 0.8667 x(2)0.96300.96440.9778 x(3)0.99290.99350.9952 x(4) 0.99870.99880.9991x1* 1.

3、0000，x2* 1.0000，x3* 1.0000準確準確(zhnqu)解解可以看出，迭代每前進一步可以看出，迭代每前進一步(y b)，結果就逼近準確解一步，結果就逼近準確解一步(y b) 迭代過程收斂迭代過程收斂第3頁/共39頁第四頁，共39頁。矩陣矩陣(j zhn)形式形式: 15/1310/89/7015/115/110/1010/19/19/10)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxxfBxx)()1( kk以上這種迭代方法稱雅可比以上這種迭代方法稱雅可比(Jacobi)迭代法。迭代法。基本思想：將方程組的求解問題轉化為重復計基本思想：將方程組的求解問題轉化

4、為重復計算算(j sun)一組彼此獨立的線性表達式。一組彼此獨立的線性表達式。第4頁/共39頁第五頁，共39頁。 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(i = 1,2, ,n; k=0,1,2, ) nijkjijijkjijiiikixaxabax1)(11)()1(1injjijbxa 1(i = 1,2, ,n)設有方程組設有方程組將第將第i個方程的第個方程的第i個變量個變量xi分離出來，據此建立分離出來，據此建立(jinl)分分量形式的雅可比迭代公式量形式的雅可比迭代公式如果如果(rgu)迭代發散迭代發散否則否則迭代收斂

5、迭代收斂*)(limikikxx 第5頁/共39頁第六頁，共39頁。用矩陣形式來表示用矩陣形式來表示(biosh)雅可比迭代公式雅可比迭代公式設有方程組設有方程組: AX = b 其中其中A(aij)n為非奇異為非奇異(qy)矩陣，矩陣，X=(x1, x2, , xn)T, b=(b1, b2, , bn)T，唯一解為，唯一解為X*=(x1*, x2*, , xn*)T將將A分解為：分解為：AU+D+L其中其中 0000U2112nnaaa nnaaa00D2211 0000L2121nnaaa第6頁/共39頁第七頁，共39頁。于是于是 (U+D+L)X = b得得 X D (U+L)X +D

6、b據此得矩陣形式據此得矩陣形式(xngsh)的雅可比迭代公式的雅可比迭代公式 X(k+1)D(U+L)X(k) +Db記記 BD (U+L)， f Db有有B：迭代矩陣：迭代矩陣( k=0,1,2, )X(k+1)= BX(k) + f任取任取 X(0), 迭代計算產生迭代計算產生(chnshng)向向量序列量序列:若若*lim)(xxkk 則迭代則迭代(di di)過程收斂。過程收斂。x* 是方程組是方程組 Ax = b 的解的解X(1), X(2), X(k),第7頁/共39頁第八頁，共39頁。第8頁/共39頁第九頁，共39頁。迭代法適用迭代法適用(shyng)于解大型稀疏方程組于解大型稀

7、疏方程組(萬階以上的方程組萬階以上的方程組,系數系數(xsh)矩陣中零元素矩陣中零元素占很大比例占很大比例,而非零元按某種模式分布而非零元按某種模式分布)背景背景: 電路分析電路分析(fnx)、邊值問題的數值解和、邊值問題的數值解和數學物理方程數學物理方程問題問題: (1)如何構造迭代格式？如何構造迭代格式？ (2)迭代格式是否收斂？迭代格式是否收斂？ (3)收斂速度如何？收斂速度如何？ (4)如何進行誤差估計？如何進行誤差估計？第9頁/共39頁第十頁，共39頁。高斯高斯(o s)塞德爾塞德爾Gauss-Seidel迭代法迭代法Gauss-Seidel迭代法是通過對迭代法是通過對Jacobi迭

8、代法稍加改迭代法稍加改進得到的。進得到的。Jacobi迭代法的每一步迭代新值迭代法的每一步迭代新值 x(k+1)=x1(k+1),x2(k+1) , ,xn(k+1)T 都是用前一步的舊值都是用前一步的舊值 x(k)=x1(k),x2(k) , ,xn(k)T的全部的全部(qunb)分量計算出來的。那么在計算第分量計算出來的。那么在計算第i個個分量分量xi(k+1) 時，已經計算出時，已經計算出 x1(k+1),x2(k+1) , ,xi-1(k+1) (i-1)個分量，這些分個分量，這些分量新值沒用在計算量新值沒用在計算xi(k+1) 上。將這些上。將這些第10頁/共39頁第十一頁，共39頁

9、。injjijbxa 1(i = 1,2,n) nijkjijijkjijiiikixaxabax1)(11)1()1(1(i = 1,2,n; k =0,1,2,)將這些分量利用起來，有可能得到一個收斂更將這些分量利用起來，有可能得到一個收斂更快的迭代公式。快的迭代公式。具體作法具體作法(zu f)：將分量形式的雅可比迭代公：將分量形式的雅可比迭代公式右端前式右端前(i-1)個分量的上標為個分量的上標為k換成換成k+1，即，即分量形式分量形式(xngsh)的高斯的高斯-塞德爾迭代公式。塞德爾迭代公式。第11頁/共39頁第十二頁，共39頁。用矩陣用矩陣(j zhn)形式來表示高斯形式來表示高斯

10、-塞德爾迭代公式塞德爾迭代公式DX(k+1)b-LX(k+1) - UX(k)即即 (D+L)X(k+1) -UX(k)+b如果如果(rgu) (D+L)存在，則存在，則 X(k+1) (D+L) UX(k)+ (D+L) b記記 B(D+L)， f (D+L) b則則( k=0,1,2,)X(k+1)= BX(k) + f矩陣形式的高斯矩陣形式的高斯(o s)-塞德爾迭代公式。塞德爾迭代公式。B：迭代矩陣：迭代矩陣第12頁/共39頁第十三頁，共39頁。例例 131581079321321321xxxxxxxxx15/ )13()(2)(1)1(3kkkxxx 15/1310/89/7015/

11、115/110/1010/19/19/10)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxx9/ )7()(3)(2)1(1kkkxxx 10/ )8()(3)(1)1(2kkkxxx 15/ )13(10/ )8(9/ )7(213312321xxxxxxxxx 000)0(3)0(2)0(1xxx第13頁/共39頁第十四頁，共39頁。例例 131581079321321321xxxxxxxxx15/ )13()1(2)1(1)1(3 kkkxxx 15/1310/89/700010/1009/19/10115/115/10110/1001)(3)(2)(1)1(3)1(2)

12、1(1kkkkkkxxxxxx9/ )7()(3)(2)1(1kkkxxx 10/ )8()(3)1(1)1(2kkkxxx 15/ )13(10/ )8(9/ )7(213312321xxxxxxxxx 000)0(3)0(2)0(1xxx第14頁/共39頁第十五頁，共39頁。 15/1310/89/7135/21350/109/190/109/19/1015/1310/89/700010/1009/19/10115/1150/110110/100115/1310/89/700010/1009/19/10115/115/10110/1001)(3)(2)(1)(3)(2)(1)(3)(2)(

13、1)1(3)1(2)1(1kkkkkkkkkkkkxxxxxxxxxxxx第15頁/共39頁第十六頁，共39頁。Jacobi迭代迭代(di di)算法算法A=9 -1 -1;-1 10 -1;-1 -1 15;b=7;8;13;x=0;0;0;er=1;k=0;while er0.00005 er=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+A(i,j)*x(j); end x(i)=t; y(i)=(b(i)-s)/A(i,i); er=max(abs(x(i)-y(i),er); end x=y;xend 131581079321

14、321321xxxxxxxxx0.7778 0.8000 0.86670.9630 0.9644 0.97190.9929 0.9935 0.99520.9987 0.9988 0.99910.9998 0.9998 0.99981.0000 1.0000 1.00001.0000 1.0000 1.0000第16頁/共39頁第十七頁，共39頁。Gauss-Seidel迭代迭代(di di)算法算法 131581079321321321xxxxxxxxxA=9 -1 -1;-1 10 -1;-1 -1 15;b=7;8;13;x=0;0;0;er=1;k=0;while er0.00005 e

15、r=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+A(i,j)*x(j); end x(i)=(b(i)-s)/A(i,i); er=max(abs(x(i)-t),er); end xend 0.7778 0.8778 0.9770 0.9839 0.9961 0.9987 0.9994 0.9998 0.9999 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000第17頁/共39頁第十八頁，共39頁。從計算結果可以明顯從計算結果可以明顯(mngxin)看出，看出，Gauss-Seidel迭代法比迭代法

16、比Jacobi迭代法效果好。迭代法效果好。一般而言，一般而言， Gauss-Seidel迭代法收斂速度比迭代法收斂速度比Jacobi迭代法快，但這兩種迭代法的收斂范圍迭代法快，但這兩種迭代法的收斂范圍并不完全重合，而只是部分相交，有的時候并不完全重合，而只是部分相交，有的時候Jacobi迭代法可能比迭代法可能比Gauss-Seidel迭代法收迭代法收斂速度更快。甚至可以舉出斂速度更快。甚至可以舉出Jacobi迭代法收斂迭代法收斂而而Gauss-Seidel迭代法發散的例子。迭代法發散的例子。第18頁/共39頁第十九頁，共39頁。Gauss-Seidel迭代法和迭代法和Jacobi迭代法的異同：

17、迭代法的異同：Jacobi迭代法：公式簡單，每次只需做矩陣和向量迭代法：公式簡單，每次只需做矩陣和向量的的 一次乘法；特別適合于并行計算；一次乘法；特別適合于并行計算；不足之處：需存放不足之處：需存放X(k)和和X(k+1)兩個存儲空間。兩個存儲空間。Gauss-Seidel迭代法：只需一個向量存儲空間，一迭代法：只需一個向量存儲空間，一旦計算出了旦計算出了xj(k+1)立即存入立即存入xj(k)的位置，可節約一的位置，可節約一套存儲單元套存儲單元 ；有時起到加速收斂的作用。；有時起到加速收斂的作用。是一種典型的串行算法，每次迭代中必須是一種典型的串行算法，每次迭代中必須(bx)依次依次計算解

18、的各個分量。計算解的各個分量。第19頁/共39頁第二十頁，共39頁。超松馳超松馳(sn ch)(SOR)迭代法迭代法超松馳迭代法是迭代方法的一種超松馳迭代法是迭代方法的一種(y zhn)加速加速方法，其計算公式方法，其計算公式 簡單，但需要選擇合適的松馳簡單，但需要選擇合適的松馳因子，以保證迭代過程有較快的收斂速度。因子，以保證迭代過程有較快的收斂速度。設有方程組設有方程組 AX = b 其中其中A(aij)n為非奇異矩陣，為非奇異矩陣，X=(x1, x2, , xn)T, b=(b1, b2, , bn)T，記，記X(k)為第為第k步迭代近似值，步迭代近似值，則則 r(k) = b AX(k

19、）表示近似解表示近似解X(k)的殘余誤差，引進如下形式的加的殘余誤差，引進如下形式的加速迭代公式速迭代公式第20頁/共39頁第二十一頁，共39頁。 X(k+1) X(k)+w(b AX)w稱作松馳因子。其分量形式稱作松馳因子。其分量形式(xngsh)為為選擇適當的松馳因子，可期望獲得較快的收斂速度。如選擇適當的松馳因子，可期望獲得較快的收斂速度。如果在計算分量果在計算分量xi(k+1) 時，考慮利用已經計算出來的分時，考慮利用已經計算出來的分量量x1(k+1),x2(k+1) , ,xi-1(k+1) ，又可得到一個新的，又可得到一個新的迭代公式迭代公式特別當特別當aii0時，將上面迭代公式應

20、用于方程組時，將上面迭代公式應用于方程組1)()()1( njkjijikikixabwxx(i=1,2, n) nijkjijijkjijikikixaxabwxx)(11)1()()1(iiinjjiiijabxaa 1第21頁/共39頁第二十二頁，共39頁。由此得下列超松馳由此得下列超松馳(SOR)迭代迭代(di di)公式公式)(11)1()()1( nijkjijijkjijiiikikixaxabaxx (i=1,2, n; k = 0,1,2,3, )當當w1時，稱超松馳法；當時，稱超松馳法；當w1時，稱低松時，稱低松馳法；當馳法；當w1時，就是時，就是Gauss-Seidel迭

21、代迭代(di di)公式。公式。所以超松馳所以超松馳(SOR)迭代迭代(di di)法可以看成法可以看成是是Gauss-Seidel迭代迭代(di di)法的加速，法的加速，而而Gauss-Seidel迭代迭代(di di)法是超松馳法是超松馳方法的特例。方法的特例。第22頁/共39頁第二十三頁，共39頁。定理定理(dngl)4.8 若若A是對稱正定矩陣是對稱正定矩陣,則當則當0w2時時SOR迭代法解方程組迭代法解方程組 Ax = b 是收斂是收斂的的定理定理4.9 若若A是嚴格是嚴格(yng)對角占優矩陣對角占優矩陣,則則當當0w0.0005 er=0;k=k+1; for i=1:3 s=

22、0;t=x(i);x(i)=0; for j=1:3 s=s+A(i,j)*x(j); end x(i)=(1-w)*t+w*(b(i)-s)/A(i,i); er=max(abs(x(i)-t),er); endendkk=10 x= 1.1999 1.3999 1.5999=1.2,只需只需k=6第24頁/共39頁第二十五頁，共39頁。 塊迭代法簡介塊迭代法簡介(jin ji)設設 ARnn, xRn, bRn將方程組將方程組A x = b中系數矩陣中系數矩陣A分塊分塊 rrrrrrrrbbbxxxAAAAAAAAA2121212222111211其中其中(qzhng), AiiRnini

23、, AijRninj , xiRni, biRni第25頁/共39頁第二十六頁，共39頁。將將A分解分解(fnji), A = DB LB UB (1) Jacobi塊迭代塊迭代(di di)(2) DB x(k+1) = (LB + UB)x(k) + b ijkjijikiiixAbxA)() 1(i=1,2, r(2)Gauss-Seidel塊迭代塊迭代(di di) DB x(k+1) = LB x(k+1)+ UBx(k) + b rijkjijijkjijikiiixAxAbxA1)(11)1()1(i=1,2, r第26頁/共39頁第二十七頁，共39頁。迭代法的收斂性迭代法的收斂

24、性C o n v e r g e n c e o f iterative method迭代矩陣迭代矩陣(j zhn)譜半譜半徑徑Spectral radius對角占優矩陣對角占優矩陣(j zhn)diagonally dominant matrix第27頁/共39頁第二十八頁，共39頁。原始原始(yunsh)方程方程: Ax = b迭代迭代(di di)格式格式: x(k+1) = Bx(k) + f定理定理(dngl)4.1(迭代法基本定理迭代法基本定理(dngl) 迭代法迭代法 x(k+1) = Bx(k) + f收斂的充要條件是收斂的充要條件是 (B) 1迭代法有著算法簡單，程序設計容易

25、以及可節迭代法有著算法簡單，程序設計容易以及可節省計算機存貯單元等優點。但是迭代法也存在省計算機存貯單元等優點。但是迭代法也存在著收斂性和收斂速度等方面的問題。因此弄清著收斂性和收斂速度等方面的問題。因此弄清楚迭代法在什么樣的條件下收斂是至關重要的。楚迭代法在什么樣的條件下收斂是至關重要的。第28頁/共39頁第二十九頁，共39頁。證證 對任何對任何(rnh) n 階矩陣階矩陣B都存在非奇矩陣都存在非奇矩陣P使使 B = P 1 J P其中其中, J 為為B的的 Jordan 標準型標準型nnrJJJJ 21iinniiiJ 11其中其中, Ji 為為Jordan塊塊其中其中(qzhng),i

26、是矩陣是矩陣B的特征值的特征值, 由由 B = P 1 J P第29頁/共39頁第三十頁，共39頁。B k = (P 1 J P) (P 1 J P) (P 1 J P)= P 1 J k P迭代法迭代法 x(k+1) = Bx(k) + f收斂收斂(shulin) 0Blim kk0Jlim kk0lim kik (i = 1, 2, r)1| i (i = 1, 2, r)1|max1 iri 譜半徑譜半徑 (B) 1第30頁/共39頁第三十一頁，共39頁。1005-1.2604e)B( J 例例 線性方程組線性方程組 Ax = b, 分別分別(fnbi)取系數取系數矩陣為矩陣為 1221

27、11221A1 211111112A2試分析試分析(fnx)Jacobi 迭代法和迭代法和 Seidel 迭代法的迭代法的斂散性斂散性 022101220JB(1)第31頁/共39頁第三十二頁，共39頁。 200320220SB12)( SB (2) A2=2, -1, 1; 1, 1, 1; 1, 1, -2 02/12/11012/12/10JB11180. 1)( JB 第32頁/共39頁第三十三頁，共39頁。 2/1002/12/102/12/10SB12/1)( SB 兩種迭代法之間沒有兩種迭代法之間沒有(mi yu)直接聯系直接聯系對矩陣對矩陣A1,求求A1x = b 的的Jacobi迭代法收斂迭代法收斂,而而Gauss-Seidel迭代法發散迭代法發散;對矩陣對矩陣A2,求求A2x = b 的的Jacobi迭代法發散迭代法發散,而而Gauss-Seidel迭代法收斂迭代法收斂.第33頁/共39頁第三十四頁，共39頁。證證 由由 (k) = B (k-1),得得 | (k)| | B| | (k-1)| (k = 1, 2, 3, )0lim)( kk 所以所以定理定理4.2(迭代收斂的充分條件迭代收斂的充