第6章_解線性方程組的迭代法計(jì)算方法

1、結(jié)束結(jié)束第第6 6章章 解線性方程組的迭代法解線性方程組的迭代法 線性方程組的直接法，用于階數(shù)不太高的線性方程組效線性方程組的直接法，用于階數(shù)不太高的線性方程組效果較好果較好. .實(shí)際工作中有的線性方程組階數(shù)很高，但其中的大實(shí)際工作中有的線性方程組階數(shù)很高，但其中的大多數(shù)系數(shù)為多數(shù)系數(shù)為0 0，這一類的線性方程組的系數(shù)陣稱為稀疏矩陣，這一類的線性方程組的系數(shù)陣稱為稀疏矩陣. .稀疏矩陣的存貯和計(jì)算有一套技術(shù)處理，可以節(jié)約大量的存稀疏矩陣的存貯和計(jì)算有一套技術(shù)處理，可以節(jié)約大量的存貯空間和計(jì)算工作量貯空間和計(jì)算工作量. .用直接法計(jì)算時(shí)，因一次消元就可以用直接法計(jì)算時(shí)，因一次消元就可以使系數(shù)陣喪

2、失其稀疏性，不能有效利用其稀疏的特點(diǎn)使系數(shù)陣喪失其稀疏性，不能有效利用其稀疏的特點(diǎn). .下文下文介紹的介紹的迭代法就有保持系數(shù)陣稀疏的優(yōu)點(diǎn)，此外迭代法也常迭代法就有保持系數(shù)陣稀疏的優(yōu)點(diǎn)，此外迭代法也常用來提高已知近似解的精度用來提高已知近似解的精度.6.1 6.1 迭代法的一般形式迭代法的一般形式線性方程組線性方程組 Ax=b (6.1) (6.1)其中其中A非奇異，非奇異，b00，因而它有唯一非零解，因而它有唯一非零解. . 1構(gòu)造與構(gòu)造與(6.1)(6.1)等價(jià)的方程組等價(jià)的方程組 x= =Bx+ +f (6.2) (6.2)即使得即使得(6.2)(6.2)與與(6.1)(6.1)同解，其

3、中同解，其中B是是nn矩陣，矩陣，f是是n維向量維向量.結(jié)束結(jié)束則有則有 x=Bx +f，即，即x是是(6.2)的解，當(dāng)然的解，當(dāng)然x也就是也就是Ax=b的解的解.任取一個(gè)向量任取一個(gè)向量x(0)作為作為x的近似解，用迭代公式的近似解，用迭代公式 x(k+1)=Bx(k)+f, (k=0,1,2,) (6.3)產(chǎn)生一個(gè)向量序列產(chǎn)生一個(gè)向量序列x(k)，若，若xxkk)(lim 從以上的討論中，可以看出，迭代法的關(guān)鍵有：從以上的討論中，可以看出，迭代法的關(guān)鍵有： 1 如何構(gòu)造迭代公式如何構(gòu)造迭代公式x(k+1)=Bx(k)+f ？這樣的構(gòu)造形式不止？這樣的構(gòu)造形式不止一種，它們各對應(yīng)一種迭代法一

4、種，它們各對應(yīng)一種迭代法. 2 迭代法產(chǎn)生的向量序列迭代法產(chǎn)生的向量序列x(k)的收斂條件是什么，收斂速的收斂條件是什么，收斂速度如何度如何.后面將進(jìn)行討論后面將進(jìn)行討論.6.2 幾種常用的迭代法公式幾種常用的迭代法公式6.2.1 簡單迭代法簡單迭代法 2結(jié)束結(jié)束按下式進(jìn)行迭代按下式進(jìn)行迭代 (k=0,1,2, )24 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx先看一個(gè)算例：先看一個(gè)算例：例例1 從以上三個(gè)方程中分別解出從以上三個(gè)方程中分別解出x1, x2, x3。

5、1052151023210321321321xxxxxxxxx 324 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0213312321xxxxxxxxx結(jié)束結(jié)束 任取一初始向量，例如任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列，得到迭代序列x(k) (k=0,1,2,)，列表如下表，列表如下表6-1。容易驗(yàn)證，原方程組的精確解為容易驗(yàn)證，原方程組的精確解為 x = (1,2,3) T，從上面的計(jì)，從上面的計(jì)算可看出，算可看出，x(k)收斂于精確解收斂于精確解.一般說來，對方程組：一般說來，對方程組： i=1,2,，n (6.4)并設(shè)并設(shè)aii0(

6、i=1,2,n)，從第，從第i個(gè)方程解出個(gè)方程解出xi，得等價(jià)的方程組，得等價(jià)的方程組：njijijbxa1k012345678x100.30000.80000.91800.97160.98040.99620.99850.9998x201.50001.76001.92601.97001.98971.99611.99861.9998x302.00002.66002.95402.95402.98232.99382.99772.9997 4迭代公式為：迭代公式為：結(jié)束結(jié)束 i=1,2,=1,2, ,n (6.5) (6.5)nijjjijiiiiiixaaabx11111)()()1(1ijnijk

7、jijkjijiiiiikixaxaaabx(6.6)(6.6) 這種迭代形式稱為簡單迭代法，也稱雅可比這種迭代形式稱為簡單迭代法，也稱雅可比(Jacobi)(Jacobi)迭迭代法代法. .,2, 1 ,0,2, 1kni雅可比迭代法雅可比迭代法的矩陣迭代形式的矩陣迭代形式: (推導(dǎo)推導(dǎo))bDfULDBfxBxJJJkJk11)()1(),(其中， 5結(jié)束結(jié)束6.2.2 塞德爾塞德爾 (Seidel) 迭代法迭代法 在簡單迭代法的迭代形式在簡單迭代法的迭代形式(6.6)中，可以看出，在計(jì)算中，可以看出，在計(jì)算 時(shí)，要使用時(shí)，要使用 .但此時(shí)但此時(shí) 已計(jì)算出來已計(jì)算出來.看來此時(shí)可提前使看來此

8、時(shí)可提前使用用 代替代替 ，一般地，計(jì)算，一般地，計(jì)算 (ni2)時(shí)，使時(shí)，使用用 代替代替 (i p1)，這樣可能收斂會快一些，這就，這樣可能收斂會快一些，這就形成一種新的迭代法，稱為塞德爾迭代法。形成一種新的迭代法，稱為塞德爾迭代法。)(1kx) 1(2kx)1(1kx)(1kx)1(1kx)1( kix)1( kpx)(kpx例例2 用塞德爾迭代法計(jì)算例用塞德爾迭代法計(jì)算例1并作比較并作比較.解解 迭代公式為：迭代公式為：24 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkx

9、xxxxxxxx(k=0,1,2, ) 6結(jié)束結(jié)束用它計(jì)算得到的序列用它計(jì)算得到的序列x(k)列表如表列表如表6-2：可見它對這一方程組比簡單迭代法收斂快一些?？梢娝鼘@一方程組比簡單迭代法收斂快一些。塞德爾迭代法的公式如下：塞德爾迭代法的公式如下：111)()1()1(1ijnijkjijkjijiiiiikixaxaaabx, 2 , 1 , 0, 2 , 1kni(6.7)(6.7) Seidel 迭代法的矩陣迭代形式：迭代法的矩陣迭代形式： （推導(dǎo)推導(dǎo)）bLDfULDBfxBxsssksk11)()1()(,)(其中 7k0123456x100.30000.88040.98430.99

10、780.99971.0000 x201.50001.94481.99221.99891.99982.0000 x302.68402.95392.99382.99912.99993.0000結(jié)束結(jié)束6.2.3 逐次超松弛法逐次超松弛法(SOR方法方法)逐次超松弛法可看成塞德爾迭代法的加速，塞德爾迭代法逐次超松弛法可看成塞德爾迭代法的加速，塞德爾迭代法是逐次超松弛法的特例是逐次超松弛法的特例.將塞德爾迭代法的將塞德爾迭代法的(6.7)式式111)()1()1(1ijnijkjijkjijiiiiikixaxaaabx改寫為改寫為11111ijnijkjijkjijiiikikixaxabaxx)(

11、)()()(11111ijnijkjijkjijiiikikikixaxabaxxr)()()()()(記11111ijnijkjijkjijiiikikikikixaxabaxrxx)()()()()()(則 8結(jié)束結(jié)束稱此公式為逐次超松弛法稱此公式為逐次超松弛法(SOR法法).從從(6.9)式不難推出式不難推出SOR方法的矩陣迭代形式：方法的矩陣迭代形式：bLDfUDLDBfxBxkk11)()1()(, )1()(其中為加快收斂，在增量為加快收斂，在增量 前加一個(gè)因子前加一個(gè)因子 ，得，得)(kir) 20()8 . 6(11)()1()()1(ijnijkjijkjijiiikikix

12、axabaxx)9 . 6(1111)() 1()() 1(ijnijkjijkjijiiikikixaxabaxx）（或改寫為下面定理下面定理6.8可以看到，必須取可以看到，必須取02，當(dāng)，當(dāng)=1時(shí)，就是時(shí)，就是Seidel迭代法迭代法.當(dāng)當(dāng)取得適當(dāng)時(shí)，對塞德爾迭代法有加速效果取得適當(dāng)時(shí)，對塞德爾迭代法有加速效果. 9結(jié)束結(jié)束例例3 用塞德爾迭代法和取用塞德爾迭代法和取=1.45的逐次超松弛法計(jì)算下列方的逐次超松弛法計(jì)算下列方程組的解，當(dāng)程組的解，當(dāng) 時(shí)退出迭代，初值取時(shí)退出迭代，初值取x(0)=(1,1,1)T 。7110|max)()(kikixx3322242024321321321x

13、xxxxxxxx由表由表6-和表和表6-可見，達(dá)到同樣的精度可見，達(dá)到同樣的精度Seidel迭代法要迭代法要72步，而取步，而取=1.45的逐次超松弛法只要的逐次超松弛法只要25步，可見當(dāng)松弛因步，可見當(dāng)松弛因子選擇適當(dāng)時(shí)，逐次超松弛法有明顯加速收斂作用，它常子選擇適當(dāng)時(shí)，逐次超松弛法有明顯加速收斂作用，它常用于求解大型線性方程組。用于求解大型線性方程組。 10結(jié)束結(jié)束6.3 迭代法的一般形式的收斂條件迭代法的一般形式的收斂條件6.3.1 一般迭代過程一般迭代過程 在什么條件下收斂在什么條件下收斂.定理定理6.1 對任意初始向量對任意初始向量x(0)和和f, 由上式產(chǎn)生的迭代序列由上式產(chǎn)生的迭

14、代序列x(k)收斂的充要條件是收斂的充要條件是(B)1.證證: 1)必要性：必要性：,*)(*)(xxfBxxxxkkk記有收斂于設(shè)fBxxkk)()(1 11.)(011*)(*)(*) 1(1kkkkkkkkBBBxxBfBxfBxxx有有.1)(0, 0lim, )(0也是任意的，,01*)0(0)0(BBkBxxxkkk章定理有由第必須有要有對任意的結(jié)束結(jié)束2)充分充分性：性：的特征值，不是則設(shè)BB1, 1)(定理定理6.1是迭代法收斂的基本定理，它不但能判別收斂，也能是迭代法收斂的基本定理，它不但能判別收斂，也能判別不收斂的情況判別不收斂的情況.但由于但由于(B)的計(jì)算往往比解方程組

15、本身更困的計(jì)算往往比解方程組本身更困難，所以本定理在理論上的意義大于在實(shí)用上的意義難，所以本定理在理論上的意義大于在實(shí)用上的意義.從上面的定理可以看到，迭代法的收斂與否與從上面的定理可以看到，迭代法的收斂與否與B的性態(tài)有關(guān)，的性態(tài)有關(guān)，與初始向量與初始向量x(0)和右端向量和右端向量 f 無關(guān)。無關(guān)。. 12成立，即有唯一解，記為于是有fBxxxfxBIBI*.)(, 0|.)(011*)(*)1(仍成立仍成立，則kkkkBxxBxx.lim,0lim.0lim0*)(成立即所以章定理有由第xxBkkkkkk結(jié)束結(jié)束定理定理6.2 若若|B|=q1，則由迭代格式，則由迭代格式x(k+1)=Bx

16、(k)+f 和任意初和任意初始向量始向量x(0)產(chǎn)生的迭代序列產(chǎn)生的迭代序列x(k)收斂于準(zhǔn)確解收斂于準(zhǔn)確解x*。本定理是迭代法收斂的充分條件，它只能判別收斂的情況本定理是迭代法收斂的充分條件，它只能判別收斂的情況，當(dāng)，當(dāng)|B|1時(shí)，不能斷定迭代不收斂。但由于時(shí)，不能斷定迭代不收斂。但由于|B|,特別是特別是|B|1和和|B|的計(jì)算比較容易，也不失為一種判別收斂的方法的計(jì)算比較容易，也不失為一種判別收斂的方法。同時(shí)當(dāng)同時(shí)當(dāng)|B|1時(shí)可以用來估計(jì)迭代的次數(shù)，或用來設(shè)置退出時(shí)可以用來估計(jì)迭代的次數(shù)，或用來設(shè)置退出計(jì)算的條件。計(jì)算的條件。 13 由于由于 (B)難于計(jì)算，而由第二章定理難于計(jì)算，而由

17、第二章定理4有有(B) |B| ，|B|1時(shí)，必有時(shí)，必有 (B) 1，于是得到：，于是得到： 14)10.6(|1|)1()0(*)(xxqqxxkk利用此定理可以在只計(jì)算出利用此定理可以在只計(jì)算出x(1)時(shí)，就估計(jì)迭代次數(shù)時(shí)，就估計(jì)迭代次數(shù)k，但估，但估計(jì)偏保守，次數(shù)偏大計(jì)偏保守，次數(shù)偏大.定理定理6.4 若若|B|=q1 ，則，則x(k)的第的第k次近似值的近似程度有如下次近似值的近似程度有如下估計(jì)式：估計(jì)式：)11.6(|1|)()1(*)1(kkkxxqqxx本定理可用于程序中設(shè)置退出條件，即只要相鄰兩次的迭代本定理可用于程序中設(shè)置退出條件，即只要相鄰兩次的迭代結(jié)果之差足夠小時(shí)，迭代

18、向量對精確解的誤差也足夠小結(jié)果之差足夠小時(shí)，迭代向量對精確解的誤差也足夠小.定理定理6.3 若若|B|=q1，則迭代格式，則迭代格式x(k+1) =Bx(k)+f產(chǎn)生的向量序產(chǎn)生的向量序列列 x(k)中中結(jié)束結(jié)束.,3212421245211102121021AA例例4 就例就例1中的系數(shù)陣中的系數(shù)陣A1和例和例3中的系數(shù)陣中的系數(shù)陣A2討論簡單迭代討論簡單迭代法和塞德爾迭代法的收斂性法和塞德爾迭代法的收斂性.因?yàn)橐驗(yàn)閨BJ|=0.61，由定理，由定理6.2知簡單迭代法收斂。知簡單迭代法收斂。.)(0402010020102001ULDBJ解：解：1）就）就A1討論討論.)(068005600

19、1200400102001ULDBS因?yàn)橐驗(yàn)閨BS|=0.31，由定理，由定理6.2知知Seidel迭代法收斂。迭代法收斂。 15結(jié)束結(jié)束用定理用定理6.2無法判斷簡單迭代法收斂性，現(xiàn)計(jì)算無法判斷簡單迭代法收斂性，現(xiàn)計(jì)算(BJ)。.)(0323121021412101ULDBJ2）就）就A2討論討論.|061323231212141213IBJ解之有三實(shí)根：解之有三實(shí)根：1=0.9207, 2 =-0.2846, 3 =-0.6361.所以所以(BJ)=0.92071，故簡單迭代法收斂，故簡單迭代法收斂. 16結(jié)束結(jié)束.)(21310854104121000020012032142411ULD

20、BS|BS|=0.875，故塞德爾迭代法收斂，故塞德爾迭代法收斂.6.3.2 從矩陣從矩陣A判斷收斂的條件判斷收斂的條件 能否直接由矩陣能否直接由矩陣 A 的性態(tài)，討論的性態(tài)，討論 Ax = b 使用迭代法使用迭代法是否收斂是否收斂. .討論前必須先介紹幾個(gè)概念：討論前必須先介紹幾個(gè)概念：1.1.對角優(yōu)勢對角優(yōu)勢 若若 A=(=(aij) )n nn n 滿足滿足且至少有一個(gè)且至少有一個(gè)i值，使值，使 成立，稱成立，稱A具有具有對角優(yōu)對角優(yōu)勢勢；niaanijjijii, 211nijjijiiaa1 17結(jié)束結(jié)束若若 稱稱A具有具有嚴(yán)格對角優(yōu)勢嚴(yán)格對角優(yōu)勢.niaanijjijii, 2 ,

21、 11定理定理6 6. .5 5 若若 A 具有嚴(yán)格對角優(yōu)勢，則具有嚴(yán)格對角優(yōu)勢，則A非奇異。非奇異。2. 2. 不可約不可約 如果矩陣如果矩陣 A 能通過行對換和相應(yīng)的列對換，能通過行對換和相應(yīng)的列對換，變成：變成： 的形式，的形式，其中其中 A11 和和 A22 為方陣，為方陣，則稱則稱 A 可約可約，反之稱，反之稱 A 不可約不可約.2212110AAA定理定理6 6. .6 6 A不可約，且具有對角優(yōu)勢，則不可約，且具有對角優(yōu)勢，則A非奇異非奇異. .以上兩個(gè)定理的證明要使用較多的數(shù)學(xué)知識，本書從略以上兩個(gè)定理的證明要使用較多的數(shù)學(xué)知識，本書從略.定理定理6 6. .7 7 A 具有嚴(yán)

22、格對角優(yōu)勢或具有嚴(yán)格對角優(yōu)勢或 A 不可約且具有對角優(yōu)不可約且具有對角優(yōu)勢，則簡單迭代法和塞德爾迭代法都收斂勢，則簡單迭代法和塞德爾迭代法都收斂. .證明：證明： 18定理定理6.8 逐次超松弛法收斂的必要條件是逐次超松弛法收斂的必要條件是02.例例5 5 用定理用定理6 6.5.5檢驗(yàn)例檢驗(yàn)例1 1中方程組的矩陣中方程組的矩陣A ，判斷該方程組，判斷該方程組用迭代法時(shí)是否收斂？用迭代法時(shí)是否收斂？ 解解 因?yàn)橐驗(yàn)?2111021210A 10 10 -2+-1-2+-1， 10 10 -2+-1 -2+-1， 5 5 -1+-2 -1+-2，所以，所以A A具有嚴(yán)格對角優(yōu)勢，具有嚴(yán)格對角優(yōu)勢，該方該方程組用程組用簡單迭代法和塞德爾簡單迭代法和塞德爾迭代法時(shí)收斂。迭代法時(shí)收斂。結(jié)束結(jié)束 定理定理6.9 如果如果A實(shí)實(shí)對稱正定對稱正定，且，且02，則逐次超松弛法收斂，則逐次超松弛法收斂.推論推論: 當(dāng)當(dāng)A實(shí)對稱正定時(shí)，實(shí)對稱正定時(shí)，Ax=b使用塞德爾迭代法收斂使用塞德爾迭代法收斂. 最后提一下關(guān)于最后提一下關(guān)于的選取，的選取，的選取影響的選取影響(B) 的大小，使的大小，使(B)最小的最小的值稱為最佳松弛因子，記為值稱為最佳松弛因子，記為 opt. opt