電子科大MATLAB第8節(jié)迭代法的收斂性

1、第三章第三章 線性方程組求解的數(shù)值方法線性方程組求解的數(shù)值方法第五節(jié)第五節(jié) 迭代法的收斂性迭代法的收斂性如何評(píng)價(jià)不同迭代方法的優(yōu)劣？如何評(píng)價(jià)不同迭代方法的優(yōu)劣？線性方程組迭代法收斂性*( )*( -1)*( -1)*2( -2)( )*(0)*() -() () = . . kkkkkkxxxMxgxxMxgMxxgM xxMxxxMxx性質(zhì)：證明：如果 存在，則 滿足： (0)* . (-)kMxx 第第k步迭代誤差公式：步迭代誤差公式：線性方程組迭代法收斂性 -1( )*(0)*-1-1-1(0)*-1(0)*12-(-).(-)(-).kkkkkkknMMQQxxMxxQQQQQQxxQ

2、Q xx 如果矩陣可以進(jìn)行特征值分解，即則迭代矩陣可表示為： 如果絕對(duì)值最大特征值（譜半徑）小于如果絕對(duì)值最大特征值（譜半徑）小于1，則收斂，反之發(fā)散。，則收斂，反之發(fā)散。線性方程組迭代法收斂性lim0( )1kkAnAA引理：設(shè) 為 階方陣，則的充要條件為。lim0lim0 (A)A 0()lim ()=0() ( ) lim ( ) =0( )1kkkkkkkkkkkkAAAAAAAAA：證：必要性 若 由矩陣收斂的定義知 又因 由夾逼定理，有 。又由于： 則： 譜半徑譜半徑-1=.= ( )kkkkkkkuAA uA uuAAA證：設(shè) 為 特征值 對(duì)應(yīng)的特征向量，則：即：為矩陣的特征值。

3、所以：（）線性方程組迭代法收斂性-11-( )( )1021( )( )12lim00.,lim0.kkkkkkkAAAAAAAAAAA：證： 充分性若，取，存在矩陣范數(shù)，使得 則有： 由算子范數(shù)相容性，可得： 由夾逼定理，可得： ,( )AnAA：定理：設(shè) 為任意 階方陣，則對(duì)任意正數(shù)存在矩陣范數(shù)，使得線性方程組迭代法收斂性(0)(1)( )( ) ()1kkkxgxMxgxM定理：對(duì)任意初始向量和右端項(xiàng) ，由迭代式產(chǎn)生的向量序列收斂是充要條件的.*( )*( )*(0)*(0)( )*(0)*limli-(-m(-)0lim(-)0lim()0). 1kkkkkkkkkknxxxxxMxg

4、xxMxxxnMxxMxMx證:必要性: 設(shè)存在 維向量,使得 則 滿足 由迭代公式有: 于是有 因?yàn)闉槿我?維向量,因此上式成立必須 由上一定理 線性方程組迭代法收斂性( )*( -1)*(0)0)*()11-0-l im0l-(-)(-)im(-)limkkkkkkkkMMI MngI MxgxxMxxM xxMxxxgMxxx 充分性：若,則不是的特征值,因而有,于是對(duì)任意 維向量 ,方程組（）有唯一解,記為,即 并且 又因?yàn)?所以,對(duì)任意初始向量,都有 (0)*(1)( )( ).(-0kkkkMxxxMxgx即由迭代公式產(chǎn)生的向量序列收斂線性方程組迭代法收斂性(0)(1)( )( )

5、1kkkxgMxMxgx推論1： 對(duì)任意初始向量和右端項(xiàng) ，若, 由迭代式 產(chǎn)生的向量序列收斂.( )|AA證明：矩陣范數(shù)性質(zhì)3： 迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量及右端項(xiàng)無(wú)關(guān)。 對(duì)同一方程組，由于不同的迭代法迭代矩陣不同，可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。迭代法收斂性：1231231232-212223-112-2100111010221001000-100-2-20 xxxxxxxxxJacobiGauss SeidelADL 例：對(duì)方程組討論迭代法與迭代法的收斂性。 解：求迭代矩陣判別其譜半徑是否小于。 0-2200-1000U 迭代法收斂性：-131230-2

6、2-10-1-2-202-2-110220,( )01,JacobiBID AIBBJacobi 迭代法的迭代矩陣為 其特征方程為 因此有于是所以迭代法收斂。迭代法收斂性：-1-121-100100-110(- )-1102210-211000-220-22(- )-11000-102-30-210000022-2-0-23(-2)000-20,Gauss SeidelD LD LMD LUIM 迭代，由 特征方程 特征值為232,()21,M故所以迭代發(fā)散。SOR迭代收斂性：1212-1-11122202,.,det(). ()det()1det()(-)(1-)1(-).(1-)nnnnn

7、MMMMMDLDUDLa aaD 推論 ： 松弛法收斂的必要條件是。證明：設(shè)松弛法的迭代矩陣有特征值。因?yàn)?由定理，松弛法收斂必有 又因?yàn)?1122(1-).det()(1-)102nnnnUa aaM 。特殊矩陣收斂性的判定：1()(1,2, , )nijiiijjj inAaaaiL niAiA定義：若 階方陣滿足且至少有一個(gè) 值，使上式中不等號(hào)嚴(yán)格成立，則稱 為。若對(duì)所有，上式不等號(hào)均嚴(yán)格成立，則稱 弱對(duì)角占優(yōu)陣嚴(yán)為格角占優(yōu)陣。1112112222,0AAAAAAAA定義：如果矩陣 不能通過(guò)行的互換和相應(yīng)的列互換成為形式 其中，為方陣，則稱 為不可約。131102101100110120

8、11P ITAP AP 例： Gauss-Seidel迭代收斂性：,1.-2.01,3.02AxbAJacobiGauss SeidelAA設(shè)有線性方程組下列結(jié)論成立：若 為嚴(yán)格對(duì)角占優(yōu)陣或不可約弱對(duì)角占優(yōu)陣，則迭代法和迭代法均收斂。若 為嚴(yán)格對(duì)角占優(yōu)陣，則松弛法收斂。若 為對(duì)稱正定陣，則松弛法收斂的充要條件為。注：注：Gauss-Seidel法為法為SOR法的特例。法的特例。Gauss-Seidel迭代收斂性：-11112211,122111223-(02)1110-2211-0-2211-022Axb AAAGauss SeidelAJacobiBI D A例：討論用三種迭代法求解的收斂性

9、。解：因 為對(duì)稱且其各階主子式皆大于零，故 為對(duì)稱正定矩陣。由判別條件 ，迭代法與松弛法均收斂。不是嚴(yán)格對(duì)角占優(yōu)陣，故不能用條件 判斷。 迭代法的迭代矩陣為Gauss-Seidel迭代收斂性：3212311221131-224411221( -) (1)021,-1,( )12I BBJacobi其特征方程 得 因而 迭代法不收斂。三種算法收斂性各有優(yōu)劣。三種算法收斂性各有優(yōu)劣。Gauss-Seidel迭代收斂性：3-10,9-4-10100-033,915-00423015( ), ()22Axb AJacobiGauss SeidelBMBM， 例： 與迭代的迭代矩注意：改變方程組中方程的

10、次序，即將系數(shù)矩陣作行交換，會(huì)改變迭代法的收斂陣分別為 譜半徑分別是性。均不收斂。Gauss-Seidel迭代收斂性：,3-109-49-43-10- AxbAxbAAAAxbJacobiGauss Seidel 若交換方程的次序，得的同解方程組 為嚴(yán)格對(duì)角占優(yōu)陣，因而對(duì)方程組用與迭代求解均收斂。線性方程組迭代法收斂速度*( )*(0( )*-1(0)*(0)-1-1(0)(1)*-1)-()()() () () ()( -) kkkkkkxxxxMxxMxIMgMIMIM xxxMIMxxI Mgxg性質(zhì)：證明：如果 存在，則 滿足： -1(0)1 () kMIMxx（ ）第第k步迭代誤差與

11、初始迭代步長(zhǎng)關(guān)系：步迭代誤差與初始迭代步長(zhǎng)關(guān)系：線性方程組迭代法收斂速度(1)( )( )*( )*(1)(0)1 -1-kkkkkxMxgMxxMxxxxM 定理：設(shè)有迭代公式,若,收斂于,則有誤差估計(jì)式： -1*( )*-1(0)1-1( )*(1( )*-1(01)( )0()10()()1)1.15()kkkkkkMMIMIMxMxgxxxMIMxxIMMMxxxxxxMIMxMx（ ）（ ）證：因,故,于是存在，方程組有唯一解 ，取范數(shù) 又因?yàn)?（）代入得 性 矩陣范數(shù)質(zhì)(1)(0)(1)ln lnMxxkkM根據(jù)事先給定的精度 ，可估計(jì)出迭代的次數(shù) :線性方程組迭代法收斂速度(0)

12、(1)4(1)(0)00.10.207.20.100.20 ,8.3 100.20.2008.40.4,-8.412.932,13MxxMxxk 例：若,則有 即需迭代 次才能滿足精度。線性方程組迭代法收斂速度*-1( )*(1)*(1)-1-1( )*-1(1)()1( -)-()()() () () () kkkkkkkxxxI MgxxM xxM xIMgM IMIM xxxMMxxgI性質(zhì)：證明：如果 存在，則 滿足： -1(1) () kkM IMxx（ ）第第k步迭代誤差與前步迭代步長(zhǎng)關(guān)系：步迭代誤差與前步迭代步長(zhǎng)關(guān)系：迭代法收斂速度(1)( )( )*( )*( )(1)1 1k

13、kkkkkxMxgMxxMxxxxM 定理：設(shè)有迭代公式,若,收斂于,則有誤差估計(jì)式：( )*-1( -1)( )( )*-1( -1)( )( )( -1)-( -) (-)-( -)-.1-kkkkkkkkxxM I MxxxxMI MxxMxxM證：因 ( )( -1)11-kkMMxxM當(dāng)不太接近 時(shí)，可用（）作為停機(jī)準(zhǔn)則。迭代法算法結(jié)構(gòu)-Matlab(1)( )i;.1 ,f ,JGMSkMkMxMMgMxggM/-迭代方程 / 初始化：/ 初始化迭代矩陣/ ; 初始化/ 計(jì)算迭代方程譜半徑 / 譜半徑大于等于1，迭代 ; 法不收斂。0 ;.;retu.rnend;while;xxe

14、ee / 終止迭代。/ 初始化變量x/ 定義迭代誤差容限/ 初始化迭代誤差:/ 迭代 ; ： (1) ;-; 1-ktmpxxMxgMex tmpxM （/ 如果迭代誤差大于門(mén)限，繼續(xù)執(zhí)行/計(jì)算/計(jì)算迭代） 誤差 111111 : (), (), () () (1) : :()JGSSORMID AgD bMDJacobiGaussLU gDLbMDLDUgSeideDSORLb11121112122212313231121.nnnnnnnnnnnaaaaaaaaAaaaaaaaDLU注意：注意：L L、U U 前有負(fù)號(hào)前有負(fù)號(hào)迭代法算法低級(jí)語(yǔ)言實(shí)現(xiàn)(0)(0)(0)(0)1(012(0)(0

15、)11.(),( ,.,),(,.,),.2.1.3.1,2,.,4.-,55.,1(,(1,2,., ),)/3-ijnniniiijjiiijj ixba xAabbbn xxxxNkinx xxkaNkk xxin 輸入維數(shù)最大容許迭代次數(shù)置對(duì) 若輸出 停機(jī)；否則轉(zhuǎn) 。若置轉(zhuǎn) ；否則，輸出失敗 信息，停機(jī)。JacobiJacobi算法：算法：( )(1,kkMxx ）評(píng)價(jià)：公式簡(jiǎn)單，每迭代一次只需計(jì)算一次矩陣和向量的乘法，不改變的稀疏性，需兩組工作單元，存。迭代法算法低級(jí)語(yǔ)言實(shí)現(xiàn)(0)(0)(0)(0)(0)112111112-1(0)111.(),( ,.,),(,.,(-)/(-)/

16、(2,)., ,., -.2.11.3.)njjjinijnniiijjijjiijj inAabbbn xxxxNkxba xaxba xa xainx 輸入維數(shù)最大容許迭代次數(shù)置計(jì)算 -11(0)(0)4.-,55.,1,(1,2,.(-)/., ),3nnnjjnnjiix xxkNkk xxinba xa 若輸出 停機(jī)；否則轉(zhuǎn) 。若置轉(zhuǎn) ；否則，輸出失敗信息，停機(jī)。Gauss-SeidelGauss-Seidel算法：算法：迭代法算法低級(jí)語(yǔ)言實(shí)現(xiàn)(0)(0)1111112-1(0)(0)11(0)(0)(0)(0)1121.(),(1-)(-),.,),(,.,),./(1-)(-2.1.3.-)/(ijnnjjjiniiiijjijjiijinjAabbbn xxxxba xaxxba xkxNaxax 輸入維數(shù)最大容許迭代次數(shù) ，參數(shù)置計(jì)算 (0)(0)-1(0)12,., -1)(1-)(4.-,55.,1,(1,2,.-)/., ),3nnnnnjjjiinnix xxkNkk xxinnxxba xa 若輸出 停機(jī)；否則轉(zhuǎn) 。若置轉(zhuǎn) ；否則，輸出失敗 信息，停機(jī)。SORSOR算法：算法：Matlab語(yǔ)言實(shí)現(xiàn)和低級(jí)語(yǔ)言實(shí)現(xiàn)比較 高級(jí)語(yǔ)言中需要進(jìn)行求逆運(yùn)算、計(jì)算譜