數(shù)值分析幾種常用的迭代法.ppt

6.3 幾種常用的迭代法,華長(zhǎng)生制作,2,記 ，A非奇異，且對(duì)角元 ，可以把 A 分解為,其中,雅可比迭代法,華長(zhǎng)生制作,3,方程組Ax=b等價(jià)于,由此構(gòu)造迭代公式：,其中迭代距陣 和向量 為,稱(chēng)之為Jacobi 迭代法（簡(jiǎn)稱(chēng) J 法），稱(chēng) 為雅可比迭代矩陣。,華長(zhǎng)生制作,4,雅可比法的分量形式為,由前面的定理知雅可比迭代關(guān)于任意初始向量收斂 的充要條件為 ，充分條件為,利用這些判別 J 法的收斂性，有時(shí)不太方便，對(duì)于大型方程組，要求出迭代矩陣譜半徑 是不容易的。下面給出一些容易驗(yàn)證收斂性的充分條件，先討論對(duì)角占優(yōu)矩陣的性質(zhì)。,華長(zhǎng)生制作,5,定義 1 若 滿(mǎn)足,則稱(chēng) A 為嚴(yán)格對(duì)角占優(yōu)矩陣。若滿(mǎn)足,且其中至少有一個(gè)嚴(yán)格不等式成立，則稱(chēng) A 為弱對(duì)角占優(yōu)矩陣。,華長(zhǎng)生制作,6,定義2 設(shè) ，若A不能經(jīng)過(guò)行置換與相應(yīng)的列置換 化為,其中 和 均為方陣，則稱(chēng) A 為不可約的，否則稱(chēng) A 為可約的。,定理 若A為嚴(yán)格對(duì)角占優(yōu)矩陣，或不可約的弱對(duì)角占優(yōu)矩陣，則解 方程組 的 J 法關(guān)于任意初始向量收斂。,設(shè) ，這里只給出A為嚴(yán)格對(duì)角占優(yōu)陣時(shí)的證明。,對(duì) J法，迭代矩陣 ，易得,。,由A的嚴(yán)格對(duì)角占優(yōu)性，得到 ，所以 J 法收斂。,證,華長(zhǎng)生制作,7,與雅可比法相應(yīng)的高斯-賽德?tīng)柕?在J 法中，計(jì)算 時(shí)，分量 已經(jīng)算出，所以可考慮,在J法中的求和分成兩部分，從而得到與雅可比迭代法相應(yīng)的高斯-賽德?tīng)柕?這就是Gauss-Seidel 迭代法，簡(jiǎn)稱(chēng) GS 法。,華長(zhǎng)生制作,8,將上式寫(xiě)成距陣形式,整理為簡(jiǎn)單迭代的形式,其中迭代矩陣 和向量 為,Jacobi 迭代法和 Gauss-Seidel 迭代法的分量形式供計(jì)算編程用，它們 的矩陣形式供研究迭代序列是否收斂等理論分析用。,華長(zhǎng)生制作,9,解 用 J 法計(jì)有,華長(zhǎng)生制作,10,GS 法迭代4次的計(jì)算結(jié)果是,精確解為（1，1，1），從計(jì)算結(jié)果看，本例用 GS 法顯然比用 J 法收斂快，但并不是任何時(shí)候GS法都比J法快，甚至有J法收斂而GS法不收斂的例子。,華長(zhǎng)生制作,11,顯然，高斯-賽德?tīng)柗P(guān)于任意初始向量收 斂的充要條件是 另外與雅可比法相仿有如下結(jié)論：,定理 若A為嚴(yán)格對(duì)角占優(yōu)矩陣，或不可約的弱對(duì)角占優(yōu)矩陣，則解 方程組Ax=b 的G S 法關(guān)于任意初始向量收斂。,華長(zhǎng)生制作,12,例.,判別下列方程組用J法和G-S法求解是否收斂,解:,(1) 求Jacobi法的迭代矩陣,華長(zhǎng)生制作,13,因此不能用范數(shù)判斷,所以,即Jaobi迭代法收斂,(2) 求Gauss-Seidel法的迭代矩陣,華長(zhǎng)生制作,14,所以Gauss-Seidel迭代法發(fā)散,華長(zhǎng)生制作,15,無(wú)論是解線(xiàn)性方程組的Jacobi迭代法和GS迭代法,都涉及到收斂速度問(wèn)題,如何加快迭代法的速度呢？,如何改善迭代法的適用范圍呢？,逐次超松弛（SOR）迭代法,華長(zhǎng)生制作,16,考慮解線(xiàn)性方程組的Gauss-Seidel迭代法,-(1),華長(zhǎng)生制作,17,令,因此,-(2),華長(zhǎng)生制作,18,上式稱(chēng)為逐次超松弛法(SOR迭代法),逐次超松弛法(SOR迭代法)的矩陣形式為,兩邊乘上D，整理為簡(jiǎn)單迭代法的形式為,華長(zhǎng)生制作,19,令,華長(zhǎng)生制作,20,SOR法化為,G-S迭代法,G-S法為SOR法的特例, SOR法為G-S法的加速,例1.,用G-S法和SOR法求下列方程組的解,要求精度1e-6,取初值（0，0，0）,華長(zhǎng)生制作,21,解:,(1)G-S迭代法,華長(zhǎng)生制作,22,gauss_seidel.m,x,k=gauss_seidel(a,b,1,1,1,1e-6) 1 1 1 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431 . 0.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944 1.9999946 k = 71,x= 0.999995 0.999994 1.999995,滿(mǎn)足精度的解,迭代次數(shù)為71次,華長(zhǎng)生制作,23,(1)SOR迭代法,1 1 1 0.6375000 0.0121875 1.3199063 0.2004270 0.3717572 1.3122805 0.6550335 0.5340119 1.6922848 0.7058468 0.7733401 1.7771932 0.9999990 0.9999976 1.9999991 0.9999984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999996 0.9999998 1.9999997 k = 24,x= 1.000000 1.000000 2.000000,滿(mǎn)足精度的解,迭代次