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

1、1 1 引言引言第第6 6章章 解線性代數(shù)方程組的迭代法解線性代數(shù)方程組的迭代法考慮線性方程組也就是 AX=b. (1.1)nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 低階稠密的線性方程組用直接法(如高斯消去法和三角分解法)。大型稀疏非帶狀的線性方程組(n很大,且零元素很多.如偏微方程數(shù)值解產(chǎn)生的線性方程組,n104)的求解問(wèn)題？零元素多，適合用迭代法。我們將介紹迭代法的一般理論及雅可比迭代法、高斯塞德?tīng)柕?、超松弛迭代法，研究它們的收斂性。例? 1 求解線性方程組(1.2) .361236,33114,2023832132132

2、1xxxxxxxxx記為Ax=b,即 .36332012361114238321 xxx 精確解x*=(3,2,1)T.改寫(xiě)(1.2)為(1.3) ).3636( ),334( ),2023(21121331111232811xxxxxxxxx或?qū)憺閤=B0 x+f,即 .000123611338203211231261111148283321 xxx xxx任取初值,如x(0)=(0,0,0)T,代入(1.3)得到x(1)=(2.5,3,3)T.反復(fù)迭代(1.4) .12/)3636(,11/)334( ,8/)2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkk

3、kkkkxxxxxxxxx即 x(k+1)=B0 x(k)+f， (k=0,1,2,)解。逐步逼近此方程的精確序列代法產(chǎn)生的向量從此例可以看出，由迭其中)()10()10()10()10(x.*,000187.0 ,)9998813.0 ,999838.1 ,000032.3(kTxxx. fBxxbAx 變形得到等價(jià)的一般地，由(1.5) * *,fBxxx則設(shè)有唯一解(1.6) ,)()1()0(fBxxxkk則可構(gòu)造迭代序列又設(shè)任取初值.)6 . 1 (1) 1) )迭代法(迭代法(定義定義一階定常迭代法近似解的方法稱為逐步代入求，用公式對(duì)于方程組fBxx.,*,*)(lim)2()(否

4、則迭代法發(fā)散是解顯然，則稱此記為存在若xxx迭代法收斂迭代法收斂kk . )5 . 1 ()6 . 1 (*,)0()()1()()(BBxxkkkkk得則由引進(jìn)誤差向量 .lim0lim )(0 0kkkkB收斂： . ) )0 0( (kkBB滿足什么條件下要研究 .)(的收斂性有以上討論，需研究kx.lim), 2 , 1( lim ,),(,),( )()()(21)()(2)(1)()(xxxxnixxRxxxxRxxxxRxkkkikiknTnnTknkkknk，記為收斂于則稱向量序列使若存在，設(shè)向量序列定定義義2 2.lim), 2 , 1,( lim )(,)( )()(AAA

5、AAAkkkijkijknnijnnkijknjiaaRaRa，記為收斂于則稱，若設(shè)矩陣序列定定義義3 3.1|0,02,01 1222，考查其極限且，設(shè)矩陣序列kkkkkAAA例例2 2. 01limlimlim1kkkkkkkkk為任意一種向量范數(shù)。其中顯然，|0,|x-|limlim )()(kkkkxxx.|0limlim 的任一算子范數(shù)為矩陣，其中。用矩陣算子范數(shù)來(lái)描述矩陣序列極限概念可以AAAAkkkk定定理理1 1. 0lim,0lim xAxAkknkkR定定理理2 2，證畢。時(shí)就證明了列元素極限均為零，當(dāng)?shù)牡诒硎緞t，個(gè)坐標(biāo)向量為第立，取反之，若定理的右邊成立。所以就有定理的右

6、邊成有，故對(duì)一切則若屬范數(shù)有證明：對(duì)任一種矩陣從0lim, 2 , 1, 0lim. 0|lim,0|lim , 0lim . |x| |x|kkkjkkjkknkkkkkkAnjjAeAejxxARxAAAA. 1|B| )3(. 1)( )2(; 0lim ) 1 (: ,)( . )()()1(，使陣范數(shù)至少存在一種從屬的矩的譜半徑則下列三個(gè)條件等價(jià)設(shè)矩陣，其中矩陣的冪構(gòu)成，即的收斂性，這種序列由有關(guān)的矩陣序列下面討論一種與迭代法BBBBkknnkijnnkkkRbRBBfBxx定理3定理3. 1)(), 1( 10lim0limBriJBikkkk).(|lim | , 1Bkkknn

7、BRB則為任意一種矩陣范數(shù)，設(shè)定理4定理4的各種迭代法。就得到解陣，選取為迭代法的迭代矩陣，稱其中代法從而可構(gòu)造一階定常迭也就是分裂矩陣。于是為的某種近似，稱容易求解，一般選擇為且使，為可選擇的非奇異矩陣其中分裂為將的迭代法。立它為非奇異矩陣，下面建其中設(shè)有方程組bAxMAMIBbMfAMIAMMNMBbMNxMxbAxMAdMxMNMAAAbAxkk11111)()1(11.,)( , , fBxxfBxx迭代法及其收斂性. 1)()8 . 1 (1.8) (1.7) )0()()1(BxfBxxfBxx收斂迭代法則對(duì)任意初始向量及一階定常迭代法設(shè)有方程組一個(gè)充分必要條件。下面給出迭代法收斂

8、的kk定理5定理5例3，P184例4，P185，則的某種算子范數(shù)如果有定常迭代法及一階設(shè)有方程組迭代法收斂的充分條件充分條件。代法收斂的一個(gè)，下面利用范數(shù)判別迭由于1 ).8 . 1 ()7 . 1 ( |)( qBBBB) )定理6(定理6(；，且，意）迭代法收斂，即對(duì)任（fBxxxxx*lim 1)()0(kk；）（)0()(* 2xxxxkkq；）（) 1()()(1* 3kkkqqxxxx.1* 4)0() 1 ()(xxxxqqkk）（ 定理6只給出迭代法收斂的一個(gè)充分條件，即使條件|B|1超松馳,1低松馳; 4)控制迭代終止的條件:例例3 3 用上述迭代法解線性代數(shù)方程組)()()

9、()1(1)()1(maxkkkikinikkxx Axbrxx或初值x(0)=0，寫(xiě)出計(jì)算格式。1111 43214111141111411114xxxxP195. 1)()5 . 3(3.5) (3.4) )0()() 1(BxfBxxfBxx收斂迭代法則對(duì)任意初始向量及一階定常迭代法設(shè)有方程組kk定理4定理41) Jacobi: BJ=D-1(L+U)，fJ=D-1b;2) Gauss-Seidel: BG=(D-L)-1U，fG= =(D-L)-1b;3) SOR: BSOR=(D-wL)-1(1-w)D+wU，fSOR= w(D-wL)-1b.迭代的統(tǒng)一格式：x(k+1)=Bx(k)

10、+f.)1()(1)(;)(, 1)();(1)(, 111UDLDLLULDGGULDJJDULDAAbAx，其中迭代法收斂其中塞德?tīng)柕ㄊ諗扛咚?，其中雅可比迭代法收斂則非奇異非奇異設(shè)SORRnn推論推論例例5 5 考察用雅可比迭代法求解線性方程組(1.2) .361236,33114,20238321321321xxxxxxxxx.53,52 1221xxxx和. ;, ),2( 11221211否則為不可約矩陣為可約矩陣則稱為方陣，使得如果存在置換陣設(shè)矩陣AAAAAAPPPA0 0定義4定義4TnnnR定義定義3 3 （1）按行嚴(yán)格對(duì)角占優(yōu)：nijiiijjniaa1), 2 , 1(

11、 |,|（2）按行弱對(duì)角占優(yōu)：nijiiijjniaa1), 2 , 1( |,|上式至少有一個(gè)不等號(hào)嚴(yán)格成立。二、某些特殊二、某些特殊方程組的迭代收斂性方程組的迭代收斂性21212212110)(ddyyAAAbPxPAPPTTT.210123321310210321301212201 ),( ,4110140110410114 , 11122211DCBA，都不為零考察矩陣iiinnnnncbabacbacbacb例7例7，則有有精確解非奇異其中仍考慮*,xAbAxnnR定理定理6(6(對(duì)角占優(yōu)定理)若矩陣A A按行(或列)嚴(yán)格對(duì)角占優(yōu)，或按行(或列)弱對(duì)角占優(yōu)且不可約；則矩陣A A非奇異

12、。定理定理7 7 若矩陣A A按行(或列)嚴(yán)格對(duì)角占優(yōu),或按行(或列)弱對(duì)角占優(yōu)不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。證明證明 若矩陣A按行嚴(yán)格對(duì)角占優(yōu)，或按行(或列)弱對(duì)角占優(yōu)不可約，則GS迭代收斂。假若不然，(BG)1，即迭代矩陣BG的某一特征值使得|1，并且. |)( |)( |)( | |0 ULDLDULDIBIG11.|)( | ,|)( | 001ULDLD又事實(shí)上矛盾從而非奇異可約或按行弱對(duì)角占優(yōu)且不按行嚴(yán)格對(duì)角占優(yōu)但是 . ., ,)( ,ULD. | )(nijijijijnijijijijiiaaaaa111111. )( ,nnnnnnnnnn

13、nnnnnnaaaaaaaaaaaaaaaaULD1211112111121222211111211類似地，若矩陣A按行嚴(yán)格對(duì)角占優(yōu)，或按行(或列)弱對(duì)角占優(yōu)不可約，則Jacobi迭代收斂。假若不然，(BJ)1，即迭代矩陣BJ的某一特征值使得|1，并且. | | )( | |0 ULDDULDIBIJ11.| | ,| 001ULDD又事實(shí)上矛盾從而非奇異可約或按行弱對(duì)角占優(yōu)且不按行嚴(yán)格對(duì)角占優(yōu)但是 . ., , ,ULD. | )(nijijijijnijijijijiiaaaaa111111. ,nnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaULD121111211112

14、1222211111211. 20 ,SOR 則松弛因子迭代收斂若定理8定理8. |)1 ( | )det()1 ()det(| | )1det()det(| |)1()det(| )det(|)( , ,SOR 1112121nnnnnDDUDLDUDLDLLL于是特征值為迭代矩陣為設(shè)證明證明2.0 , 1)(|1 | SOR即迭代收斂，所以因?yàn)長(zhǎng)定理定理9 9 對(duì)于線性方程組AxAx=b b，若A A為對(duì)稱正定矩陣，則當(dāng)02時(shí)，SOR迭代收斂. 證明證明 只需證明1（其中為L(zhǎng)的任一特征值）.)()1( ,)1()( , ,1yLDyUDyyUDLDyyyL或于是的特征向量為相應(yīng)于設(shè),)()()1 ( ),(),(),(),)(1 ( ).(),(),(),(),( ),(),(iiiiTyLyyDyyUyyDyyLyLyyyyLyUyyLyyDy于是，則，記. 1)()1 (| 2222222. 0)2)(2()()1 (,2)(022yy,ULD定理定理10 10 對(duì)于線性代數(shù)方程組Ax=b， 若A按行(或列)嚴(yán)格對(duì)角占優(yōu)，或按行(