第5節(jié)_迭代法的收斂性

1、課程回顧 迭代法的原理； 迭代法的構(gòu)造； 迭代法的關(guān)鍵問(wèn)題； 分形 迭代法解線(xiàn)性方程組： 最簡(jiǎn)單方法 最有效方法 Jacobi方法 Gauss-Seidel方法 SOR方法 問(wèn)題：如何評(píng)價(jià)不同迭代方法的優(yōu)劣？如何評(píng)價(jià)不同迭代方法的優(yōu)劣？第三章第三章 線(xiàn)性方程組求解的數(shù)值方法線(xiàn)性方程組求解的數(shù)值方法第五節(jié)第五節(jié) 迭代法的收斂性迭代法的收斂性迭代法收斂性 收縮映射原理（Contraction Principle）：(1)( )121212, 01, ( ) ()()()kkx xLxxxL xxxf x：，滿(mǎn)足則收斂fff( ) kx序列收斂證明：(1)( )( )(1)( )(1)(1)(2)2

2、(1)(2)1(1)(0)(1)(0)()() ()() . ()()kkkkkkkkkkkkxxf xf xL xxL f xf xL xxLf xf xLxx10(1)( )0, log () , LkkKkKxxxx 滿(mǎn)足：收縮映射xx 表示取大于 的整數(shù)線(xiàn)性方程組迭代法收斂性lim0( )1kkAnAA引理：設(shè) 為 階方陣，則的充要條件為。lim0lim0 (A)A 0()lim ()=0() ( ) lim ( ) =0( )1kkkkkkkkkkkkAAAAAAAAA：證：必要性 若 由矩陣收斂的定義知 又因 由夾逼定理，有 。又由于： 則： 譜半徑譜半徑-1=.= ( )kkkk

3、kkkuAA uA uuAAA證：設(shè) 為 特征值 對(duì)應(yīng)的特征向量，則：即：為矩陣的特征值。所以：（）線(xiàn)性方程組迭代法收斂性-11-( )( )1021( )( )12lim00.,lim0.kkkkkkkAAAAAAAAAAA：證： 充分性若，取，存在矩陣范數(shù)，使得 則有： 由算子范數(shù)相容性，可得： 由夾逼定理，可得： ,( )AnAA：定理：設(shè) 為任意 階方陣，則對(duì)任意正數(shù)存在矩陣范數(shù)，使得線(xiàn)性方程組迭代法收斂性*( )*( -1)*( -1)*2( -2)( )*(0)*() -() () = . . kkkkkkxxxMxgxxMxgMxxgM xxMxxxMxx性質(zhì)：證明：如果 存在，

4、則 滿(mǎn)足： (0)* . (-)kMxx 第第1步迭代與第步迭代與第k步迭代關(guān)系。步迭代關(guān)系。線(xiàn)性方程組迭代法收斂性(0)(1)( )( ) ()1kkkxgxMxgxM定理：對(duì)任意初始向量和右端項(xiàng) ，由迭代式產(chǎn)生的向量序列收斂是充要條件的.*( )*( )*(0)*(0)( )*(0)*limli-(-m(-)0lim(-)0lim()0). 1kkkkkkkkkknxxxxxMxgxxMxxxnMxxMxMx證:必要性: 設(shè)存在 維向量,使得 則 滿(mǎn)足 由迭代公式有: 于是有 因?yàn)闉槿我?維向量,因此上式成立必須 由上一定理 線(xiàn)性方程組迭代法收斂性( )*( -1)*(0)0)*()11-

5、0-l im0l-(-)(-)im(-)limkkkkkkkkMMI MngI MxgxxMxxM xxMxxxgMxxx 充分性：若,則不是的特征值,因而有,于是對(duì)任意 維向量 ,方程組（）有唯一解,記為,即 并且 又因?yàn)?所以,對(duì)任意初始向量,都有 (0)*(1)( )( ).(-0kkkkMxxxMxgx即由迭代公式產(chǎn)生的向量序列收斂11111011,)00,()0,max1,xBBIBIB xxIB xBxxBxBxBxx性質(zhì)：若矩陣 的某個(gè)算子范數(shù)則必有可逆證明：反證法：設(shè)(有非零解，即： 使得即： 與已知矛盾！線(xiàn)性方程組迭代法收斂性線(xiàn)性方程組迭代法收斂性(0)(1)( )( )1k

6、kkxgMxMxgx推論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-22-

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

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

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

10、三種迭代法求解的收斂性。解：因 為對(duì)稱(chēng)且其各階主子式皆大于零，故 為對(duì)稱(chēng)正定矩陣。由判別條件 ，迭代法與松弛法均收斂。不是嚴(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， 例： 與迭代的迭代矩注

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

12、 ）線(xià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ù) :線(xiàn)性方程組迭代法收斂速度(0)(1)4(1)(0)00.10.207.20

13、.100.20 ,8.3 100.20.2008.40.4,-8.412.932,13MxxMxxk 例：若,則有 即需迭代 次才能滿(mǎn)足精度。線(xiàn)性方程組迭代法收斂速度*-1( )*(1)*(1)-1-1( )*-1(1)()1( -)-()()() () () () kkkkkkkxxxI MgxxM xxM xIMgM IMIM xxxMMxxgI性質(zhì)：證明：如果 存在，則 滿(mǎn)足： -1(1) () kkM IMxx（ ）迭代法收斂速度(1)( )( )*( )*( )(1)1 1kkkkkkxMxgMxxMxxxxM 定理：設(shè)有迭代公式,若,收斂于,則有誤差估計(jì)式：( )*-1( -1)(

14、 )( )*-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;xxeee / 終止迭代。/ 初始化變量x/ 定義迭代誤差容限/ 初始化迭代誤差:/ 迭代 ; ： (1) ;-;

15、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)迭代法算法結(jié)構(gòu)-Matlab1 AIIA 矩陣求逆： :aussSeidel:JacobiG對(duì)角矩陣求逆三角矩陣求逆 上述兩種算法計(jì)算上述兩種算法計(jì)算M矩陣過(guò)程運(yùn)算量小矩陣過(guò)程

16、運(yùn)算量小于矩陣于矩陣A求逆。求逆。迭代法算法低級(jí)語(yǔ)言實(shí)現(xiàn)(0)(0)(0)(0)1(012(0)(0)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

17、)(0)(0)(0)112111112-1(0)111.(),( ,.,),(,.,(-)/(-)/(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)

18、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ì)算譜半徑，

19、實(shí)際工程中可能找不到相關(guān)庫(kù)函數(shù)。 低級(jí)語(yǔ)言實(shí)現(xiàn)無(wú)需計(jì)算矩陣求逆，但是無(wú)法事先判斷迭代是否成功，另外迭代終止條件存在誤差,迭代過(guò)程中計(jì)算量較大。習(xí)題例：教材習(xí)題5121-2-1-2-1;-31-1-31()-311-1-31()-11MMaaaaMaaaMa解：步驟一、寫(xiě)出矩陣：步驟二、計(jì)算特征值： 步驟三、討論： 2222131131 113111 1aaaaaa （） （）（） （） 0.5,2/3)(0,0.5)aa 單調(diào)遞增單調(diào)遞增單調(diào)遞減單調(diào)遞減習(xí)題例：教材習(xí)題5-0.500.511.50.511.522.533.5A = 2, 1; 1, 2B = eye(2) for iii = 1 : 1000 a = iii / 500; a = a - 0.5; M =