數(shù)值第3章解線性方程組的迭代法

1、第第3 3章章 解線性方程組的迭代法解線性方程組的迭代法 迭代法是從某一取定的初始向量x x(0)出發(fā),按照一個(gè)適當(dāng)?shù)牡?,逐次計(jì)算出向量x x(1), x x(2),使得向量序列x x(k)收斂于方程組的精確解.迭代法是一類逐次近似的方法.其優(yōu)點(diǎn)是,算法簡便,程序易于實(shí)現(xiàn). 迭代法的基本思想是，把n元線性方程組nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 （3.1） 或 Ax=b改寫成等價(jià)的方程組 nnnnnnnnnnngxmxmxmxgxmxmxmxgxmxmxmx2211222221212112121111 ，或x=Mx+

2、g由此建立方程組的迭代公式 x(k+1)=Mx(k)+g , k=0,1,2, (3.2)其中M稱為迭代矩陣迭代矩陣。 對任意取定的初始向量x x(0),由(3.2)式可逐次算出迭代向量x x(k),k=1,2, 如果向量序列x(k) 收斂于x*,由(3.2)式可得 x*=Mx*+g 從而x x*是方程組x=Mx+g的解,也就是方程組Ax=b的解. 這種求解線性方程組的方法稱為迭代法迭代法 ,若迭代序列x(k)收斂,則稱迭代法收斂,否則稱迭代法發(fā)散. 1 Jacobi迭代法和迭代法和Gauss-Seidel迭代法迭代法 Jacobi方法是由方程組(3.1)中第k個(gè)方程解出x xk,得到等價(jià)方程

3、組:從而得迭代公式nnnnnnnnnnnnnnnnnnnabxaaxaaxaaxabxaaxaaxaaxabxaaxaaxaax1122112222223222312221211111131113211121, 3 , 2 , 1,) 3 . 3()(1)(2)(1)1(222)(222)(2223)(2221)1(111)(111)(1113)(1112)1(112131232kabxaaxaaxaaxabxaaxaaxaaxabxaaxaaxaaxnnnknnnnknnnknnnkknkkkknkkknnnn式(3.3)稱為JacobiJacobi迭代法迭代法,簡稱為J J迭代法迭代法.

4、. ,則J迭代法可寫成 x x(k+1)=BxBx(k)+g g k=0,1,2, 可見 ,J J迭代法的迭代矩陣為0002122222211111112nnnnnnnnaaaaaaaaaaaaBTnnnababab),(222111g若記, 2 , 1 , 0, 2 , 1,)(11)(11)()1(knixaxabaxnijkijijkijiiikjji J J法也記為G-SG-S迭代法也可記為, 3 , 2 , 1,)4 . 3()1(1)1(2)1(1)1(222)(222)(2223)1(2221)1(111)(111)(1113)(1112)1(112131232kabxaaxaa

5、xaaxabxaaxaaxaaxabxaaxaaxaaxnnnknnnnknnnknnnkknkkkknkkknnnn式(3.4)稱為Gauss-SeidelGauss-Seidel迭代法迭代法,簡稱為G-SG-S迭代法迭代法. . 若在J J迭代法中,充分利用新值, 則可以得到如下的迭代公式, 2 , 1 , 0, 2 , 1,)(11)(11)1()1(knixaxabaxnijkijijkijiiikjji方程組的精確解為x x*=(1,1,1)T. 解解 J J迭代法計(jì)算公式為例例1 用J法和G-S法求解線性方程組141035310214310321321321xxxxxxxxx57)

6、(2103)(1101)1(321)(3103)(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxx取初始向量x x(0)=(0,0,0)T,迭代可得4 . 1, 5 . 0, 4 . 1)1(3)1(2)1(1xxx11. 1, 2 . 1,11. 1)2(3)2(2)2(1xxx計(jì)算結(jié)果列表如下:可見,迭代序列逐次收斂于方程組的解, 而且迭代7次得到精確到小數(shù)點(diǎn)后兩位的近似解.kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.9

7、6450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636 G-S G-S迭代法的計(jì)算公式為: 同樣取初始向量x x(0)=(0,0,0)T, 計(jì)算結(jié)果為 由計(jì)算結(jié)果可見,G-S迭代法收斂較快.取精確到小數(shù)點(diǎn)后兩位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.57)1(2103)1(1101)1(321)(3103)1(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxxkx1(k)x

8、2(k)x3(k)x(k)-x*012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956 為了進(jìn)一步研究,從矩陣角度來討論上述迭代法. 對線性方程組AxAx=b b,記 D D=diag(a11,a22,ann)000121323121nnnnaaaaaaL000,122311312nnnnaaaaaaU則有 A A=D D-L L-U U于是線性方程組 AxAx=b b 可寫成 (D D-L L-U U)x x=b b等價(jià)于 DxDx=(L L+U U)x x+b b 或或

9、 x x=D D-1(L L+U U)x x+D D-1b b 由此建立J J迭代法迭代公式 x x(k+1)=D D-1(L L+U U)x x(k)+D D-1b b k=0,1,2,或?qū)懗?x x(k+1)=BxBx(k)+g g k=0,1,2,其中000)(21222222111111121nnnnnnnnaaaaaaaaaaaaULDBnnnababab2221111,bDgG-SG-S迭代法迭代公式可寫成 x x(k+1)=D D-1LxLx(k+1)+D D-1UxUx(k)+D D-1b b 討論迭代法 x(k+1)=Mx(k)+g k=0,1,2, Dx Dx(k+1)=L

10、xLx(k+1)+UxUx(k)+b b (D D-L L)x x(k+1)=UxUx(k)+b b x x(k+1)=(D D-L L)-1UxUx(k)+(D D-L L)-1b b 所以G-SG-S迭代法可以寫成 x x(k+1)=GxGx(k)+g g k=0,1,2,其中 G G=(D D-L L)-1U U , g g=(D D-L L)-1b b 2 2 迭代法的一般形式與收斂性迭代法的一般形式與收斂性的收斂性. 記誤差向量e e(k)=x x(k)-x x*,則迭代法收斂就是e e(k)0 0.由于 x(k+1)=Mx(k)+g k=0,1,2, x*=Mx*+g k=0,1,

11、2,所以 e(k+1)=Me(k) , k=0,1,2,遞推可得 e(k)=Mke(0) , k=0,1,2,可見,當(dāng)k時(shí), e e(k)0 0 Mk O O. 對任意初始向量x x(0),迭代法收斂(M)1.定理定理3.1 證證 若MkO O, 則k(M)=(Mk)Mk0,所以(M)1. 若(M)0,使得(M)+1.則MkMk (M)+)k 0. 若若M1,則對任意x x(0),迭代法收斂,而且 定理定理3.2)6 . 3(0)(1)k*(k)xxM1Mxx)5 . 3(1)1()(*)(kkkxxMMxx 證證 由于 x(k+1)=Mx(k)+g x(k)=Mx(k-1)+g x*=Mx*

12、+g所以 x(k+1) -x(k)=M(x (k) -x(k-1) ) , x(k+1) x*=M(x (k) x* )于是有 x(k+1) -x(k) Mx (k) -x(k-1) x(k+1) x*Mx (k) x* x(k+1) -x(k) =(x (k+1) x* )-(x(k) x* ) x (k) x*-x(k+1) x* x(k+1) -x(k) =(x (k+1) x* )-(x(k) x* ) x (k) x*-x(k+1) x* (1-M)x(k) x*所以)()1(*)(11kkkxxMxx)1()(1kkxxMM)0()1(1xxMMk 定理3.2只是收斂的充分條件,并

13、不必要,如7 . 005 . 08 . 0M則M1=1.2,M=1.3,M2=1.09,MF=1.17但(M)=0.81,所以迭代法是收斂的.由(3.5)式可見,M越小收斂越快,且當(dāng)x (k) -x(k-1) 很小時(shí),x(k) x*就很小,實(shí)際上用x (k) -x(k-1) 作為迭代終止的條件.例如kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.000251

14、0.998236410.50.20.0710.03550.011590.0057950.0017636x (6) -x(5) =0.011339,x(7) x(6)=0.0056695 由(3.6)式可得:若使x(k) x* ,只需可以事先估計(jì)達(dá)到某一精度需要迭代多少步.)0()1(1xxMMk , 即M(0)(1)xx)M(1ln/ )ln(k 用J J迭代法求例1中方程組的解,取x(0)=(0,0,0)T,若使誤差x(k)-x*10-5,問需要迭代多少次? 解解 由例1知,x x(1)=(1.4,0.5,1.4)T,于是有,x x(1)-x x(0)=1.4 ,B B=0.5 .例例2 0

15、0010310110351101103Bk應(yīng)滿足095.185 . 0ln/ )4 . 1105 . 0ln(5k故取k=19, 即需要迭代19次.3 J3 J迭代法和迭代法和G-SG-S迭代法的收斂性迭代法的收斂性 定理定理3.33.3 J J迭代法收斂(B)1;若B1J J迭代法收斂; G-SG-S迭代法收斂(G)1;若G1 G-SG-S迭代法收斂; 定義定義3.13.1 若n階矩陣A=(aij)滿足:niaaiinijjij, 2 , 1,1則稱矩陣A是嚴(yán)格對角占優(yōu)矩陣嚴(yán)格對角占優(yōu)矩陣. 引理引理 若A是嚴(yán)格對角占優(yōu)矩陣, 則det(A)0. 證證 A=D-L-U=D(E-D-1(L+U

16、)=D(E-B)因此, (B)B1,故=1不是B B的特征值,det(E E-B B)0. 定理定理3.43.4 設(shè)A是嚴(yán)格對角占優(yōu)矩陣,則解線性方程組Ax=b的J J迭代法和G-SG-S迭代法均收斂. 因?yàn)锳是嚴(yán)格對角占優(yōu)矩陣, 所以det(D)0, 而且1max11nijjiiijniaaB所以, det(A)0. 證證 由于B1, 所以J J迭代法收斂. 設(shè)是G G的任一特征值, 則滿足特征方程 det(E-G)= det(E-(D-L)-1U) = det(D-L)-1)det(D-L)-U)=0所以有 det(D-L)-U)=0nnnnnnaaaaaaaaa212222111211U

17、L)(D 若|1, 則矩陣(D-L)-U 是嚴(yán)格對角占優(yōu)矩陣, 這與 det(D-L)-U)=0矛盾, 所以|1,于是(G)1時(shí)稱為超松弛迭代超松弛迭代, , 當(dāng)當(dāng)1時(shí)稱為欠松弛迭代欠松弛迭代. ., 2 , 1 , 0, 2 , 1)7 . 3()()(11)1()()1(knixaxabaxxnijkijijkijiiikikjji 其矩陣形式 x(k+1)=x(k)+D-1(b+Lx(k+1)+(U-D)x(k) , k=0,1,2,于是有 Dx(k+1)=Dx(k)+(b+Lx(k+1)+(U-D)x(k) 所以 x(k+1)=(D-L)-1 (1-)D+Ux(k)+(D-L)-1b

18、,k=0,1,2,因此,SOR方法的迭代矩陣為 =(D-L)-1 (1-)D+U SORSOR方法收斂( )1;若 1,則SORSOR方法收斂. 定理定理3.73.7 若SORSOR方法收斂, 則02.定理定理3.6 證證 設(shè)SORSOR方法收斂, 則( )1,所以 |det( )| =|12 n|1而 det( ) =det(D-L)-1 (1-)D+U) =det(E-D-1L)-1 det(1-)E+D-1U) =(1-)n于是 |1-|1, 或 02定理定理3.8 設(shè)A是嚴(yán)格對角占優(yōu)矩陣,則解方程組Ax=b的SORSOR方法,當(dāng)01時(shí)收斂. 定理定理3.93.9 設(shè)A是對稱正定矩陣,

19、則解方程組Ax=b的SORSOR方法,當(dāng)00 (Uy,y)=(y,Ly)=(Ly,y) =-i 0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y) =-2所以)()()1 (ii2222222)()(|當(dāng)02時(shí),有 (-+)2-(-)2= (2-)(2-) = (2-)(2-)0所以|21, 因此( )1,即SOR方法收斂.可得 =2/ 設(shè)是B的任一特征值, y是對應(yīng)的特征向量, 則 (L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)當(dāng)A對稱正定時(shí),即2-0時(shí),|0而 (2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =+2即,當(dāng)A對稱正定時(shí),JacobiJa

20、cobi迭代法收斂2D-A正定. SORSOR方法收斂的快慢與松弛因子的選擇有密切關(guān)系.但是如何選取最佳松弛因子,即選取=*,使( )達(dá)到最小,是一個(gè)尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗(yàn)上可取1.41.6. 用SORSOR方法解線性方程組7910431017210424321321321xxxxxxxxx 解解 SORSOR方法迭代公式為方程組的精確解是x x*=(2,1,-1)T.例例4)91047(9)101723(17)42410(4)(3)1(2)1(1)(3)1(3)(3)(2)1(1)(2)1(2)(3)(2)(1)(1)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx取x x(0)=(0,0,0)T,=1.46,計(jì)算結(jié)果如下:kx1(k)x2(k)x3(k)01232003.652.321669102.56613991.999998700.88458820.42309390.69482611.00000130-0.2021098-0.22243214-0.4952594-1.0000034 從結(jié)果可見 ,迭代20次時(shí)已獲得精確到小數(shù)點(diǎn)后五位的近似解.如果取=1.25,則需要迭代56次才能得到具有同樣精度的近似解;如果取=1,則需迭代110次以上.練習(xí)題練習(xí)題第第75頁頁 習(xí)題習(xí)題33