第4章 解線性方程組迭代法2017_2

1、14 松弛法(1)( )(1)121(1)( )( )111(1)( )11 (,), 1 ()Tkkkninkkkiijjijjiijj iinkkiijjijjjj iiiGaussSeidelxxxxxxxGaussSeidelxb xb xgxba xa xxa 可認(rèn)為是對迭代法加速。記其中由迭代公式得到。于是有( )( )(1)( )(1,2, )kikkkinxGaussSeidelkxxxx 可以把看作迭代的修正項(xiàng)，即第 次近似解以此項(xiàng)修正后得到新的近似解 2(1)( )(1)1(1)( )11 (1)() (kkkkiiiinkkkiiijjijjjj iiixxxxxxxxb

2、a xa xai 松弛法是將乘上一個參數(shù)因子作為修正項(xiàng)而得到新的近似解，具體公式為即1,2, ) 111nAxbGaussSeidel按上式計(jì)算的近似解序列的方法稱為松弛法，稱為松弛因子。當(dāng)時稱為低松弛；是迭代；時稱為超松弛法。3(1)( )( )1(1)1( )1( )( )1(1)1( )11111 () (1)1()(kkkkkkkkkxxxxD LxD UxD bxxD LxD UxD bID LID LDL松弛法迭代公式的矩陣表示：因det（） ，故（） 與存在。(1)111)111(1 () (1)() () (1) () ) kkxDLDU xD DD LDLDDLbMDLDU有

3、松弛法的迭代矩陣為松弛因子的選取對收斂速度影響極大，但目前尚無可供實(shí)用的計(jì)算最佳松弛因子的方法。通常是根據(jù)系數(shù)矩陣的性質(zhì)及實(shí)際經(jīng)驗(yàn)，通過試算來確（）定松弛因子。4(0)1212323(1)(1)1(1)( )11(11 1.4,(1,1,1) ,21 2021.8 +() (1)()Tkkkkiiiiinkkkiiijjijjjj iiikxxxxxxxxxxxxxba xa xax 例：取用超松弛法解方程組解：由)( )( )12(1)( )(1)( )2213(1)( )(1)332(0)(9)0.40.7(1)0.40.7()(0,1,2,)0.40.7(1.8)(1,1,1)(1.20

4、0,1.3996,1.6001) (1.2,1.4,1.6)kkkkkkkkkTTTxxxxxxkxxxxxx 將代入上式開始迭代，精確解5松弛法計(jì)算過程如下：1(0)(0)(0)(0)12(0)(0)11111121(0)(0)111.()(,)(,)2.13. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbnxxxxNkxxba xaxxba xa xa 輸入，維數(shù) ， ，參數(shù)，最大容許迭代次數(shù)。置。計(jì)算，1(0)1(0)(0) (2,1) (1)() /4.55.1(1,2, )3nnnnnjjnnjiiinxxba xaxxxkNkkxxin

5、，。若，輸出 ，停機(jī)；否則轉(zhuǎn) 。若，置，轉(zhuǎn) ；否則，輸出失敗信息，停機(jī)。65 迭代法的收斂條件一、矩陣的譜半徑11212 (1,2, ) ( )max(,) (,)(1,2,), (iii nnkkkknAninAAAAAAAAk 迭代法的收斂與迭代矩陣的特征值有關(guān)。定義：設(shè) 為 階方陣，為 的特征值，稱絕對值最大的特征值的絕對值為矩陣 的譜半徑，記為稱為矩陣 的譜。由特征值的定義知，矩陣的譜是因而22) ( )( ()()kkAuuA uA AuAuAuAAu）7二、迭代法的收斂條件(0)( )(4.2) ( )1.kx Bx fxgxB設(shè)線性方程組 =+ 有唯一解,則對任意初始向量和右端項(xiàng)

6、 ，由迭代格式產(chǎn)生的向量序列收斂的充要條件是 定理4.3 （ ： 充要條件）*1*101()().kkkkkxBxfxxB xxBxxxBxf證:*11lim()0lim0( )1.kkkkxxBB因此8注注: :因?yàn)橐驗(yàn)?都可以直接用矩陣都可以直接用矩陣的元素計(jì)算，因此的元素計(jì)算，因此, ,用推論用推論1 1容易判別迭代法容易判別迭代法的收斂性的收斂性. .1,FBBB(0)( ) 1 (4.2)kxfBx對任意初始向量和右端項(xiàng) ，若，由迭代格式產(chǎn)生的向量序列收斂.1() 推論 充分條件注注: :要檢驗(yàn)一個矩陣的譜半徑小于要檢驗(yàn)一個矩陣的譜半徑小于1 1，比較困難，所，比較困難，所 以，我們

7、希望用別的辦法判斷收斂性以，我們希望用別的辦法判斷收斂性. . 9 02.松弛法收斂的必要條件是 2() 推論必要條件由定理由定理4.3, , 有有定理定理4.4 Jacobi 迭代法收斂的迭代法收斂的充要條件充要條件是是 (B) 1.由推論由推論1, 得到得到定理定理4.5 若若 | B | 1，則，則 Jacobi 迭代法收斂迭代法收斂. (充分條件充分條件)Jacobi迭代法收斂的條件迭代法收斂的條件定理定理4.6 GS 迭代法收斂的迭代法收斂的充要條件充要條件是是 (B) 1.定理定理4.7 若若 | B | 1，則，則 GS 迭代法收斂。迭代法收斂。Gauss - Seidel迭代法

8、收斂的條件迭代法收斂的條件12 021 12,1上例說明了確實(shí)只是松弛法收斂的必要條件，而非充要條件，因?yàn)镚auss-Seidel迭代即為的情形。判斷定理雖然給出了判別迭代收斂的充要條件，但要求逆矩陣和特征值。推論 與 僅分別給出了收斂的充分與必要條件，許多情形下不能起作用由推論 無法判別收斂性。 對一些特殊的系數(shù)矩陣可給出幾個常用的判別收斂條件。131 ()(1,2, )nijiiijjj inAaaainiAiA定義：若 階方陣滿足且至少有一個 值，使上式中不等號嚴(yán)格成立，則稱 為弱對角占優(yōu)陣。若對所有，上式不等號均嚴(yán)格成立，則稱為嚴(yán)格對角占優(yōu)陣。131112112222 ,0110210

9、 110011012011P ITAAAAAAAAAP AP 定義：如果矩陣 不能通過行的互換和相應(yīng)的列互換成為形式其中，為方陣，則稱 為不可約。 例：141.JacobiGauss-SeidelA若 為嚴(yán)格對角占優(yōu)陣或不可約弱對角占優(yōu)陣，則迭代法和迭代法均收斂。2.01,A若 為嚴(yán)格對角占優(yōu)陣，則松弛法收斂。3.02A若 為對稱正定陣，則松弛法收斂的充要條件為。1012210 1 102121115012A BABAB 若線性方程組的系數(shù)矩陣分別為 , ：則， 為嚴(yán)格對角占優(yōu)陣，故Jacobi與Gauss-Seidel迭代均收斂。 為非嚴(yán)格對角占優(yōu)陣，但為對稱正定陣， =1.4故松弛法收斂。

10、 ,Axb設(shè)有線性方程組下列結(jié)論成立：例例10 判別判別,下列方程組使用下列方程組使用 J-迭代法迭代法,G-S迭代法求迭代法求解是否收斂解是否收斂?12412341231234102 52 92403 48 1 2 61xxxxxxxxxxxxxx解解 此方程組是嚴(yán)格按行對角占優(yōu)的此方程組是嚴(yán)格按行對角占優(yōu)的, 所以使用所以使用J-法收斂，法收斂，G-S迭代法收斂迭代法收斂.16-111/ 21/ 2,1/ 211/ 21/ 21/ 213(02)101/ 21/ 2 -1/ 201/ 21/ 21/ 20Axb AAAABI D A 例11：討論用三種迭代法求解的收斂性。解：因 為對稱且其

11、各階主子式皆大于零，故 為對稱正定矩陣.由判別條件 ，Gauss-Seidel迭代法與松弛法均收斂.不是弱對角占優(yōu)陣，故不能用條件 判斷。Jacobi迭代法的迭代矩陣為173212311221131 224411221 () (1)021,1, ()12 IBBJa co b i 其 特 征 方 程得因 而迭 代 法 不 收 斂 。Jacobi迭代法收斂的條件續(xù)迭代法收斂的條件續(xù)定理定理4.8若方程組若方程組 Ax=b 的系數(shù)陣的系數(shù)陣 A 是主對角嚴(yán)格占是主對角嚴(yán)格占優(yōu)陣或不可約弱對角占優(yōu)陣，則用優(yōu)陣或不可約弱對角占優(yōu)陣，則用 Jacobi 迭代法求迭代法求解必收斂。解必收斂。定理定理4.9

12、 若方程組若方程組 Ax=b 的系數(shù)陣的系數(shù)陣 A 是主對角嚴(yán)格占是主對角嚴(yán)格占優(yōu)陣或不可約弱對角占優(yōu)陣，則用優(yōu)陣或不可約弱對角占優(yōu)陣，則用 GS 迭代法求解迭代法求解必收斂。必收斂。定理定理4.10 若方程組若方程組 Ax=b 的系數(shù)陣的系數(shù)陣 A 是正定矩陣，是正定矩陣，則用則用 GS 迭代法求解必收斂。迭代法求解必收斂。Gauss - Seidel迭代法收斂的條件續(xù)迭代法收斂的條件續(xù)20 310 , 9410100033 , 91500423015( ),()22AxbAJacobiGaussSeidelBMBM改變方程組中方程的次序，即將系數(shù)矩陣作行交換，會改變迭代法的收斂性。例12：

13、與迭代的迭代矩陣分別為譜半徑分別是。均不收斂。21 ,31094 94310AxbA xbAAAA xbJacobiGaussSeidel若交換方程的次序，得的同解方程組為嚴(yán)格對角占優(yōu)陣，因而對方程組用與迭代求解均收斂。22 310 , 9410100033 , 91500423015( ),()22AxbAJacobiGaussSeidelBMBM改變方程組中方程的次序，即將系數(shù)矩陣作行交換，會改變迭代法的收斂性。例12：與迭代的迭代矩陣分別為譜半徑分別是。均不收斂。23 ,31094 94310AxbA xbAAAA xbJacobiGaussSeidel若交換方程的次序，得的同解方程組為嚴(yán)格對角占優(yōu)陣，因而對方程組用與迭代求解均收斂。