數(shù)值分析 第6章 解線(xiàn)性方程組迭代法

1、數(shù)理學(xué)院數(shù)理學(xué)院SCHOOL OF MATHEMATICS AND PHYSICS6 .1 引言引言6 .2 Jacobi迭代迭代6 .3 GaussSeidel迭代迭代6.4超松弛迭代法超松弛迭代法(SOR)第第6章章 解線(xiàn)性方程組的迭代法解線(xiàn)性方程組的迭代法對(duì)方程組對(duì)方程組bAx 做等價(jià)變換做等價(jià)變換gGxxbMNxMxbNxMxbxNMbAx11)(如：令如：令NMA，則，則則可以構(gòu)造序列則可以構(gòu)造序列g(shù)xGxkk)()1( 若若*)(xxkbAxgxGx* *同時(shí)：同時(shí)：*)(*)()()1(xxGGxGxxxkkk*)()0(1xxGk0kG所以，序列收斂所以，序列收斂與初值的選取無(wú)

2、關(guān)與初值的選取無(wú)關(guān).(6.1)（6.2）6.1 引言引言定義定義6.1：（收斂矩陣）0kG定理：定理：矩陣矩陣G為收斂矩陣，當(dāng)且僅當(dāng)為收斂矩陣，當(dāng)且僅當(dāng)G的譜半徑的譜半徑eps) x1=x2; for(i=0;in;i+) x2i=0; for(j=0;ji;j+) x2i += Aij*x1j for(j=i+1;jn;j+) x2i += Aij*x1j x2i=(bi -x2i)/Aii 4、輸出解x2 迭代矩陣迭代矩陣ULDA記記nnaaD1100001,121nnnaaaL0000, 1112nnnaaaU易知，易知，Jacobi迭代有迭代有bxULD)(bxULDx)(bDxULD

3、x11)(bDgADIULDG111 , )( 收斂條件收斂條件 迭代格式收斂的充要條件是迭代格式收斂的充要條件是(G) 1 ，充分條件是，充分條件是|G|emg for i=1:n sum=0; for j=1:n if i=j sum=sum+A(i,j)*x1(j); end end x2(i)=(b(i)-sum)/A(i,i); end r=max(abs(x2-x1); x1=x2; k=k+1; if kN disp(迭代失敗，返回); return; endendx=x1;A=8 -3 2;4 11 -1;6 3 12；b=20;33;36;X0=0;0;0;x,k=Jacob

4、i(A,b,X0,100,0.001)在命令窗口輸入：x = 3.00028156796144 1.99991182189570 0.99974047656463k = 9運(yùn)行結(jié)果：)(1)(1)(1 )1(11,)1(11)1(2)(2)(323)1(12122)1(21)(1)(21211)1(1nknnnknnnknknnkkkknnkkbxaxaaxbxaxaxaaxbxaxaax6.3 GaussSeidel迭代迭代)(11)(11)1()1(nijkjijijkjijiiikixaxabax在在Jacobi迭代中，使用最新計(jì)算出的分量值迭代中，使用最新計(jì)算出的分量值Gauss-Se

5、idel迭代算法迭代算法1、輸入系數(shù)矩陣A和向量b，和誤差控制eps2、x2=1,1,.,1 /賦初值3、while( |A*x2-b|eps) for(i=0;in;i+) for(j=0;ji;j+) x2i += Aij*x2j for(j=i+1;jn;j+) x2i += Aij*x2j x2i= (bi- x2i)/Aii 4、輸出解x2 迭代矩陣迭代矩陣)()()1(1)1(bUxLxDxkkkbDUxDxLDIkk1)(1)1(1)(bDLDIUxDLDIxkk111)(111)1()()(bLDUxLDxkk1)(1)1()()(bLDgULDG11)( , )( 是否是原來(lái)

6、的方程的解？是否是原來(lái)的方程的解？A=(D-L)-U系數(shù)矩陣對(duì)應(yīng)的分解公式：系數(shù)矩陣對(duì)應(yīng)的分解公式： 收斂條件收斂條件 迭代格式收斂的充要條件是迭代格式收斂的充要條件是(G) 1 ，充分條件是，充分條件是|G|emg x0=y; y =G*x0+f;n=n+1; end y nA=8 -3 2;4 11 -1;6 3 12；b=20;33;36;X0=0;0;0;x,k=Jacobi(A,b,X0,0.001)在命令窗口輸入：運(yùn)行結(jié)果：y = 2.99984238664111 2.00007213359433 1.00006077328086n = 5(0)1807109,8 ,(0,0,0)

7、9117Abx 1、預(yù)處理、預(yù)處理9117180,71098Ab 2、迭代格式、迭代格式例例3)8(91)7(81)7(91)1(1)1(3)1(1)1(2)(3)(2)1(1kkkkkkkxxxxxxx(1)(2)(3)(4)(0.7778,0.9722,0.9753)(0.9942,0.9993,0.9994)(0.9999,0.9999,0.9999)(1.0000,1.0000,1.0000)xxxx3、結(jié)果、結(jié)果101/21/2()1011/21/20BDLU1、Jacobi迭代迭代211111112A特征值為特征值為3504IB12,350,2i 101/21/2()01/21/2

8、001/2BDLU2、GaussSiedel迭代迭代12,310,2 例例4例例5方程組方程組Ax=b中，中，證明當(dāng)證明當(dāng)時(shí)時(shí)GS法收斂，而法收斂，而J法只在法只在時(shí)才收斂時(shí)才收斂. 111aaaaaaA12/1 a2/12/1 a解解只要證只要證 12/1 a時(shí)時(shí)A正定即可，由順序主子式正定即可，由順序主子式 得得于是得到于是得到 12/1 a1|0111, 01221 aaaa0)21()1(321det2233 aaaaA2/1 a對(duì)對(duì)J法，由于迭代矩陣法，由于迭代矩陣 是是J法收斂的充要條件法收斂的充要條件.故故J法只在法只在時(shí)才收斂時(shí)才收斂.當(dāng)當(dāng)a=0.8時(shí)，時(shí)，GS法收斂，而法收斂

9、，而J法不收斂。法不收斂。 000aaaaaaBJ0)2()(23)det(2323 aaaaBIJ 2/1|1|2|)( aaBJ 2/1| a16 . 1)( JB 練習(xí)練習(xí) 設(shè)方程組設(shè)方程組試考察用試考察用J法和法和GS法求解的收斂性。法求解的收斂性。 解解 其中其中 J法迭代矩陣法迭代矩陣 38 . 04 . 028 . 04 . 014 . 04 . 0321321321xxxxxxxxxULDA 18 . 04 . 08 . 014 . 04 . 04 . 010008 . 0004 . 04 . 00,08 . 04 . 0004 . 0000),1 , 1 , 1 (ULdia

10、gD08 . 04 . 08 . 004 . 04 . 04 . 00)(1ULDB0)32. 08 . 0)(8 . 0(8 . 04 . 08 . 04 . 04 . 04 . 0)det(2BI故用故用J法解此方程組不收斂。法解此方程組不收斂。 GS法迭代矩陣為法迭代矩陣為 672. 032. 0064. 016. 004 . 04 . 000008 . 0004 . 04 . 0018 . 008. 0014 . 0001)(1ULDG18 . 0|)(GG故解此方程組的故解此方程組的GS迭代法是收斂的迭代法是收斂的 6.3.3 迭代的收斂速度迭代的收斂速度gGxx迭代公式0|,|00

11、)( eeBekk誤差關(guān)系如下：于是于是|)0()(kkBee 根據(jù)算子范數(shù)定義可知根據(jù)算子范數(shù)定義可知|max|max|)0()(0)0()0(0)0()0(eeeeBBkekek 所以所以是迭代是迭代k次后誤差向量次后誤差向量的范數(shù)與初始誤差向量的范數(shù)與初始誤差向量的范數(shù)之比的最大值的范數(shù)之比的最大值.若要求迭代若要求迭代k次后次后|kB)(ke)0(e |,|)0()(0)(kkkBeeee即即這里這里是一個(gè)小數(shù)，通常是一個(gè)小數(shù)，通常emg x0=y y =lw*x0+f;n=n+1; end y nA=4 3 0;3 4 -1;0 -1 4;b=24;30;-24;X0=1;1;1;y

12、,n=sor(A,b,1,X0,1e-7)6.4.2 SOR迭代法收斂性迭代法收斂性 根據(jù)迭代法收斂性定理，根據(jù)迭代法收斂性定理，SOR法收斂的充分必要條件為法收斂的充分必要條件為 ，收斂的充分條件為，收斂的充分條件為 ，但要計(jì)算，但要計(jì)算 比較復(fù)雜，通常都不用此結(jié)論，而直接根據(jù)方程組的比較復(fù)雜，通常都不用此結(jié)論，而直接根據(jù)方程組的系數(shù)矩陣系數(shù)矩陣A判斷判斷SOR迭代收斂性迭代收斂性.1)(G1|GG定理定理11 設(shè)設(shè) 則解方程則解方程的的SOR迭代法收斂的必要條件是迭代法收斂的必要條件是02 證明證明由由SOR迭代矩陣迭代矩陣的表達(dá)式的表達(dá)式(3.4) 于是于是 ), 2 , 1(0,)(n

13、iaRaAiinnijbAx G)1()(1UDLDGnDDUDLDG)1 ()1det(det)1det()det(det11SOR迭代收斂必要條件迭代收斂必要條件另一方面，設(shè)另一方面，設(shè) 的特征值為的特征值為 由特征根性質(zhì)，有由特征根性質(zhì)，有 若若SOR法收斂，則法收斂，則 ，由，由 則得則得02.證畢證畢.Gn,1|1 |det|max)(/1/111nnniniGG1)(G1)(|1 |G定理定理12若若則解則解Ax=b的的SOR迭代法迭代法(3.3)對(duì)對(duì)迭代收斂迭代收斂. 證明證明設(shè)設(shè) 對(duì)稱(chēng)正定，且對(duì)稱(chēng)正定，且02，的特征值為的特征值為 對(duì)應(yīng)特征向量對(duì)應(yīng)特征向量x0,由由(3.4)得

14、得因因 為實(shí)對(duì)稱(chēng)矩陣，故為實(shí)對(duì)稱(chēng)矩陣，故 nnRAnRxG(可能是復(fù)數(shù)可能是復(fù)數(shù))，xLDxUD)()1(ULDAULT上式兩邊與上式兩邊與x作內(nèi)積，得作內(nèi)積，得(3.5) 因因A正定，故正定，故D也正定，記也正定，記 又記又記 ),(),(),(),)(1 (xLxxDxxUxxDx0),( pxDxixLx),(由復(fù)內(nèi)積性質(zhì)得由復(fù)內(nèi)積性質(zhì)得 于是由于是由(3.5)有有 由于由于A正定及正定及02，故，故 于是于是 ixLxxxLxUxT),(),(),(iapiap)1 (2222222)()(|apapp02),(),(),(),(apxUxxLxxDxxAx. 0)2)(2()()(2

15、2papapapp定理定理3.3設(shè)設(shè) 為對(duì)稱(chēng)正定的三對(duì)角矩陣，為對(duì)稱(chēng)正定的三對(duì)角矩陣， 是解方程是解方程Ax=b的的J法迭代矩陣，若法迭代矩陣，若 ，記，記 ，則，則SOR法的最優(yōu)松弛因子法的最優(yōu)松弛因子為為(3.6) 且且 (3.7) 根據(jù)定理，根據(jù)定理， nnRAJB1)(JB)(JBb2112b 2104/ )1(4)(222 bbuG)(min)( Gb 說(shuō)明說(shuō)明GS法比法比J法快一倍法快一倍. 圖圖4-1 由由(3.7)可知，當(dāng)可知，當(dāng)=1， 收斂速度為收斂速度為 ： )()(22JBG )(2)(ln2)(ln)(JJBRBGGR 例例8對(duì)例對(duì)例7中的方程組，用中的方程組，用SOR

16、迭代法求最優(yōu)松弛因子迭代法求最優(yōu)松弛因子 ，并研究其收斂速度，并研究其收斂速度. 解解由于由于 是對(duì)稱(chēng)正定的三對(duì)角矩陣，是對(duì)稱(chēng)正定的三對(duì)角矩陣，SOR迭代收斂迭代收斂. 故故 b410143034A85)det(,025. 0025. 0075. 0075. 003JJBIB625. 0)(,790. 08/5)(GBJ而而SOR最優(yōu)松弛因子最優(yōu)松弛因子 故故 .若要使誤差若要使誤差 24. 1375. 012)(1122JbB24. 0)(bG|10|)0(7)(eek取取k=12即可即可. 例例7中取中取=1.25已近似已近似 故它收斂很快，實(shí)際計(jì)算時(shí)迭代故它收斂很快，實(shí)際計(jì)算時(shí)迭代14次可達(dá)到小數(shù)后次可達(dá)到小數(shù)后7位精度位精度.24. 1 b 2944.11)(10ln7 bGRk 4271. 124. 0ln)(ln)(bbGGR對(duì)對(duì)=1的的GS法，由法，由 達(dá)到與達(dá)到與SOR法的同樣精度法的同樣精度.迭代次數(shù)迭代次數(shù) 故故k34與實(shí)際計(jì)算結(jié)果相符與實(shí)際計(jì)算結(jié)果相符 294.34)(10ln7 GRk470. 0625. 0ln)(ln)( GGR 松弛迭代算法松弛迭代算法1、輸入系數(shù)矩陣A、向量b和松弛因子omega，和誤差控制eps2、x2=1,1,.,1 /賦初值3、while( |A*x2-b