計算方法_第八章_解線性方程組的迭代法_高斯迭代法_迭代法的收斂性

1、1計 算 方 法第八章第八章 線性方程組的解法線性方程組的解法計算方法課程組28.08.0 引引 言言重要性重要性：解線性代數(shù)方程組的有效方法在計算數(shù)學(xué)和：解線性代數(shù)方程組的有效方法在計算數(shù)學(xué)和科學(xué)計算中具有特殊的地位和作用。如科學(xué)計算中具有特殊的地位和作用。如彈性力學(xué)、電彈性力學(xué)、電路分析、熱傳導(dǎo)和振動路分析、熱傳導(dǎo)和振動、以及社會科學(xué)及定量分析商、以及社會科學(xué)及定量分析商業(yè)經(jīng)濟(jì)中的各種問題。業(yè)經(jīng)濟(jì)中的各種問題。 求解線性方程組求解線性方程組 的求解方法，其中的求解方法，其中 ， 。 A xbn nAR,nx bR假設(shè)假設(shè) 非奇異，則方程組有唯一解非奇異，則方程組有唯一解. .*12(,)T

2、nxx xxA38.08.0 引引 言言 分類分類： 線性方程組的解法可分為線性方程組的解法可分為直接法直接法和和迭代法迭代法兩種方法。兩種方法。(a)直直接法接法： 對于給定的方程組，在沒有舍入誤差的假設(shè)下，對于給定的方程組，在沒有舍入誤差的假設(shè)下，能在預(yù)定的運算次數(shù)內(nèi)求得精確解。最基本的直接法是能在預(yù)定的運算次數(shù)內(nèi)求得精確解。最基本的直接法是Gauss消去法，重要的直接法全都受到消去法，重要的直接法全都受到Gauss消去法的啟發(fā)。消去法的啟發(fā)。 計算代價高計算代價高.(b)迭代法：迭代法：基于一定的遞推格式，產(chǎn)生逼近方程組精確解的基于一定的遞推格式，產(chǎn)生逼近方程組精確解的近似序列近似序列.

3、收斂性是其為迭代法的前提，此外，存在收斂速收斂性是其為迭代法的前提，此外，存在收斂速度與誤差估計問題。度與誤差估計問題。簡單實用簡單實用, 誘人。誘人。48.1 雅可比雅可比Jacobi迭代法迭代法 (AX=b)迭代法的基本思想迭代法的基本思想例題分析例題分析Jacobi迭代公式迭代公式5 與解與解f (x)=0 的不動點迭代相類似，將的不動點迭代相類似，將AX=b改寫改寫為為X=BX+f 的形式，建立雅可比方法的迭代格式：的形式，建立雅可比方法的迭代格式： 其中，其中，B稱為迭代矩陣。其計算精度可控，特別稱為迭代矩陣。其計算精度可控，特別適用于求解系數(shù)為大型稀疏矩陣適用于求解系數(shù)為大型稀疏矩

4、陣(sparse matrices)的的方程組。方程組。8.1 8.1 雅可比雅可比JacobiJacobi迭代法迭代法 (AX=b)(AX=b)迭代法的基本思想迭代法的基本思想 (1)( )kkxBxf 6問題問題: :(a) 如何建立迭代格式？如何建立迭代格式？(b) 向量向量序列序列 x(k) 是否收斂以及收斂條件是否收斂以及收斂條件? ?(1)( )kkxBxf AXb 72 例題分析例題分析: 其準(zhǔn)確解為其準(zhǔn)確解為X*= 1.1, 1.2, 1.3 ?？紤]解方程組考慮解方程組.xxxxxxxxx1231231231027 21028 354 2 (1)3.1Jacobi迭代法迭代法8

5、2 例題分析例題分析: 建立與式建立與式(1)(1)相等價的形式：相等價的形式：.xxxxxxxxx1232133120 10 20 720 10 20 830 20 20 84 (2)其準(zhǔn)確解為其準(zhǔn)確解為X*=1.1, 1.2, 1.3?？紤]解方程組考慮解方程組.xxxxxxxxx1231231231027 21028 354 2 (1)3.1Jacobi迭代法迭代法92 例題分析例題分析: 其準(zhǔn)確解為其準(zhǔn)確解為X*=1.1, 1.2, 1.3。建立與式建立與式(1)(1)相等價的形式：相等價的形式：.xxxxxxxxx1232133120 10 20 720 10 20 830 20 20

6、 84考慮解方程組考慮解方程組.xxxxxxxxx1231231231027 21028 354 2( )( )( )xxx0001230取迭代初值取迭代初值據(jù)此建立迭代公式：據(jù)此建立迭代公式： ( +1)( )( )123( +1)( )( )213( +1)( )( )312=0.1+0.2+0.72=0.1+0.2+0.83=0.2+0.2+0.84kkkkkkkkkxxxxxxxxx10迭代結(jié)果如下表迭代結(jié)果如下表：迭 代 次 數(shù)迭 代 次 數(shù) x1 x2 x30 0 0 01 0 . 7 2 0 . 8 3 0 . 8 42 0 . 9 7 1 1 . 0 7 1 . 1 53 1

7、. 0 5 7 1 . 1 5 7 1 1 . 2 4 8 24 1 . 0 8 5 3 5 1 . 1 8 5 3 4 1 . 2 8 2 8 25 1 . 0 9 5 0 9 8 1 . 1 9 5 0 9 9 1 . 2 9 4 1 3 86 1 . 0 9 8 3 3 8 1 . 1 9 8 3 3 7 1 . 2 9 8 0 3 97 1 . 0 9 9 4 4 2 1 . 1 9 9 4 4 2 1 . 2 9 9 3 3 58 1 . 0 9 9 8 1 1 1 . 1 9 9 8 1 1 1 . 2 9 9 7 7 79 1 . 0 9 9 9 3 6 1 . 1 9 9 9

8、3 6 1 . 2 9 9 9 2 41 0 1 . 0 9 9 9 7 9 1 . 1 9 9 9 7 9 1 . 2 9 9 9 7 51 1 1 . 0 9 9 9 9 3 1 . 1 9 9 9 9 3 1 . 2 9 9 9 9 11 2 1 . 0 9 9 9 9 8 1 . 1 9 9 9 9 8 1 . 2 9 9 9 9 71 3 1 . 0 9 9 9 9 9 1 . 1 9 9 9 9 9 1 . 2 9 9 9 9 91 4 1 . 1 1 . 2 1 . 31 5 1 . 1 1 . 2 1 . 311 11,0(1,2, )1()(1,2, )nijjiiiinii

9、ijjjiij ia xbainxba xina(1)11()(1,2, )nkkiiijijiij ixba xina 設(shè)方程組設(shè)方程組 AX=b , 通過分離變量的過程建立通過分離變量的過程建立Jacobi迭代公式，即迭代公式，即 由此我們可以得到由此我們可以得到 Jacobi 迭代公式迭代公式：8.1 Jacobi8.1 Jacobi迭代公式迭代公式12(1)1( )1()kkxDLU xD b 雅可比迭代法的矩陣表示雅可比迭代法的矩陣表示 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 nnnnnnnnnnnnbxaxaaxbx

10、axaaxbxaxaax11112212122211212111.1.1.10 iia寫成矩陣形式：寫成矩陣形式：A =LUD()()AxbDLU xbDxLU xb 11()xDLU xD b BfJacobi 迭代陣迭代陣138.2 8.2 高斯高斯- -塞德爾迭代法塞德爾迭代法 (AX=b)(AX=b)(1)kix kkkixxx (1)(1)(1)121,( )( )( )121,kkkixxx 注意到利用注意到利用JacobiJacobi迭代公式迭代公式計算計算時，已經(jīng)計算好了時，已經(jīng)計算好了的值，而的值，而JacobiJacobi迭代公式并不利用這些最新的近似值計算，迭代公式并不利

11、用這些最新的近似值計算，仍用仍用1(1)(1)111()(1,2, )inkkkiiijjijjjj iiixba xa xina 這啟發(fā)我們可以對其加以改進(jìn)這啟發(fā)我們可以對其加以改進(jìn), ,即在每個分量的計算中盡即在每個分量的計算中盡量利用最新的迭代值，得到量利用最新的迭代值，得到上式稱為上式稱為 Gauss-Seidel 迭代法迭代法. .14)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3b

12、xaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 寫成寫成矩陣形式：矩陣形式：(1)1(1)()1()kkkxDLxUxDb (1)()()kkDL xUxb (1)1( )1()()kkxDLUxDLb BfGauss-Seidel 迭代陣迭代陣8.2 8.2 高斯高斯- -塞德爾迭代法塞德爾迭代法15其準(zhǔn)確解為其準(zhǔn)確解為X*=1.1, 1.2, 1.3。.kkkkkkkkkxxxxxxxxx1232133121111110 10 20 720 10 20 830 20 20 84考慮解方程組考慮解方

13、程組.xxxxxxxxx1231231231027 21028 354 2高斯高斯- -塞德爾迭代法算例塞德爾迭代法算例高斯高斯- -塞德爾迭代格式塞德爾迭代格式16迭代次數(shù)迭代次數(shù) x1 x2 x3 0 0 0 0 1 0.72 0.902 1.1644 2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999

14、8 1.1 1.2 1.317開始Niyxii10,01i0T iiiiaTbx/ )(Ni 1iiix y jjxyNj,1Ni ix打印結(jié)果1ii( 0 )()1, 2.1, 21, 2,.0,0,1, 23 .0,1, 2114 .1ijiiiijiiikiijjiiiNAaBbXxYyabbainajnbinnxxyinxkninjnbaxijxai 線 形 方 程 組 組 數(shù)系 數(shù) 矩 陣常 數(shù) 矩 陣迭 代 過 程 中 的 解 上 一 輪 迭 代 的 解將的 值 賦 給計 算 步 驟 ： 輸 入 原 始 數(shù) 據(jù) 輸 入 初 使 迭 代 值迭 代 計 算如， 則精 度 判 斷15 .

15、1, 2iiiiinxyjnyxxin 如則轉(zhuǎn) 第 三 步 再 計 算打 印 計 算 結(jié) 果的 值TFTFT,1i jiabNijN輸 入1,ijjjNij TTa x 如18 逐次超松弛迭代法逐次超松弛迭代法(Successive Over Relaxation Method，簡寫為，簡寫為SOR)可以看作帶參數(shù)可以看作帶參數(shù)的高斯的高斯-塞德塞德爾迭代法，是爾迭代法，是 G-S 方法的一種修正或加速，是求解大方法的一種修正或加速，是求解大型稀疏矩陣方程組的有效方法之一。型稀疏矩陣方程組的有效方法之一。8.3 8.3 超松馳迭代法超松馳迭代法SOR方法方法1. SOR基本思想基本思想 19

16、設(shè)方程組設(shè)方程組AX=b, 其中，其中，A=(aij) 為非奇異陣，為非奇異陣， x=(x1, x2, , xn)T, b=(b1, b2, , bn)T.假設(shè)已算出假設(shè)已算出 x(k) ，8.3 8.3 超松馳迭代法超松馳迭代法SOR方法方法2. SOR算法的構(gòu)造算法的構(gòu)造 ), 2 , 1()(1111) 1() 1(nixaxabaxnijkjijijkjijiiiki(1)(1)( )(1)( )( )(1)()kkkiiikkkiiixxxxxx 稱為松弛因子稱為松弛因子 利用高斯利用高斯-塞德爾迭代法得塞德爾迭代法得:208.3 8.3 超松馳迭代法超松馳迭代法SOR方法方法2.

17、SOR算法的構(gòu)造算法的構(gòu)造 ( (基于基于G-S迭代迭代) ) 解方程組解方程組AX=b的逐次超松弛迭代公式：的逐次超松弛迭代公式： ), 2 , 1()()(11)1()()1(nixaxabaxxxxnijkjijijkjijiiiiikiki顯然，當(dāng)取顯然，當(dāng)取=1=1時，上式就是高斯時，上式就是高斯- -塞德爾迭代公式塞德爾迭代公式. .218.3 8.3 超松馳迭代法超松馳迭代法SOR方法方法2. SOR算法的構(gòu)造算法的構(gòu)造(基于基于Jacobi迭代迭代) 得到解方程組得到解方程組 AX=b 的逐次超松弛迭代公式：的逐次超松弛迭代公式： (1)( )( )1() (1,2, )kki

18、iinkiiijjjiixxxxba xina 顯然，上式就是顯然，上式就是 基于基于Jacobi 迭代的迭代的 SOR 方法方法.22下面令下面令 ，希望通過選取合適的希望通過選取合適的 來加速收斂，這就是來加速收斂，這就是松弛法松弛法 。inkkiijjijjjba xa x- -1 1( ( + +1 1) )( ( ) )= =1 1j j= =i i- - -3. SOR算法的進(jìn)一步解釋算法的進(jìn)一步解釋 SOR方法方法inkkkiiijjijjj iiixba xa xa- -1 1( ( + +1 1) )( ( + +1 1) )( ( ) )j j= =1 1= = + +1

19、11 1= =- - -kkiiiirxa( ( + +1 1) )( ( ) )= =+ +其中其中ri(k+1) =相當(dāng)于在相當(dāng)于在 的基礎(chǔ)上的基礎(chǔ)上加個余項加個余項生成生成 。)(kix)1( kix0 1(漸次漸次)超松弛法超松弛法1kkkiiiiirxxaw( ( + +1 1) )( () )( ( ) )= =+ +23利用利用SOR方法方法解方程組解方程組SOR例題分析例題分析: :其準(zhǔn)確解為其準(zhǔn)確解為x* *=1, 1, 2.=1, 1, 2.xxxxxxxxx1 12 23 31 12 23 31 12 23 34 4- - 2 2- -= = 0 0- -2 2+ + 4

20、 4- - 2 2= = - -2 2( (1 1) )- - - 2 2+ + 3 3= = 3 3xxxxxxxxx123123213213312312= 0.5+0.25= 0.5+0.25= 0.5+0.5-0.5(2)= 0.5+0.5-0.5(2)1212=+1=+13333建立與式建立與式(1)(1)相等價的形式：相等價的形式：24據(jù)此建立據(jù)此建立G-S迭代公式：迭代公式：(k+1)(k)k123(k+1)(k+1)(k)213(k+1)(k+1)(k+1)312= 0.5+ 0.25= 0.5+ 0.5- 0.5(3)12=+ 133xxxxxxxxx取迭代初值取迭代初值: :

21、( (0 0) )( (0 0) )( (0 0) )1 12 23 3= = = =1 1xxx,=1.5,=1.5,迭代結(jié)果如下表迭代結(jié)果如下表. . SORSOR迭代公式為：迭代公式為：(k+1)(k)(k)(k)1123(k+1)(k)(k+1)(k)2213(k+1)(k)(k+1)(k+1)3312= (1-)+(0.5+0.25)x= (1-)+(0.5+0.5-0.5)(4)12= (1-)+(+1)33xw xwxxw xwxxxw xwxx25GS迭代法須迭代迭代法須迭代85次得到準(zhǔn)確值次得到準(zhǔn)確值 x*=1, 1, 2;而而SOR方法只須方法只須55次即得準(zhǔn)確值次即得準(zhǔn)確

22、值. 由此可見，適當(dāng)?shù)剡x擇松弛由此可見，適當(dāng)?shù)剡x擇松弛因子因子，SOR法具有法具有明顯的明顯的加速收斂效果加速收斂效果. . 逐次超松弛迭代法逐次超松弛迭代法次數(shù)次數(shù) x1 x2 x3 1 0.625000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 15 0.991521 0.985318 1.987416 25 0.998596 0.998234 1.998355 55

23、 1.00000 1.0000 2.000026 關(guān)于關(guān)于SOR方法的說明：方法的說明：(1)顯然，當(dāng)顯然，當(dāng) 時，時，SOR方法就是方法就是Gauss- Seidel方法。方法。(2)SOR 方法每一次迭代的主要運算量是計算一次矩陣與向量方法每一次迭代的主要運算量是計算一次矩陣與向量的乘法。的乘法。(3) 時稱為超松弛方法，時稱為超松弛方法， 時稱為低松弛方法。時稱為低松弛方法。(4)計算機(jī)實現(xiàn)時可用計算機(jī)實現(xiàn)時可用 控制迭代終止，或用控制迭代終止，或用 (5)SOR方法可以看成是方法可以看成是Gauss-Seidel方法的一種修正。方法的一種修正。111(1)( )11maxmaxkkii

24、ii ni nxxx ( )( )kkrbAx27 （迭代法基本定理）（迭代法基本定理） 設(shè)有方程組設(shè)有方程組 ，對于任意的初始向，對于任意的初始向量量 ，迭代公式，迭代公式 收斂的充要條件是迭收斂的充要條件是迭代矩陣代矩陣 的譜半徑的譜半徑 . . 8.4 8.4 迭代法的收斂性迭代法的收斂性- -充要條件充要條件xBxf(1)( )kkxBxf(0)xB( )1B 迭代法的基本定理在理論分析中有重要意義。迭代法的基本定理在理論分析中有重要意義。28定理定理2：設(shè)設(shè)X*是方程組是方程組AX = b的同解方程的同解方程X = BX + F 的準(zhǔn)確解的準(zhǔn)確解，若迭代公式中迭代矩陣若迭代公式中迭代

25、矩陣B的某種范數(shù)的某種范數(shù)，)1()(*)(1kkkXXqqXX(1)0()1(*)(1XXqqXXKk(2)1B則有則有 在具體使用上，由于在具體使用上，由于 ，因此，我們利，因此，我們利用范數(shù)可以建立判別迭代法收斂的充分條件。用范數(shù)可以建立判別迭代法收斂的充分條件。 ( )BB29關(guān)于解某些特殊方程組迭代法的收斂性關(guān)于解某些特殊方程組迭代法的收斂性定義：定義：( (對角占優(yōu)陣對角占優(yōu)陣) ) 設(shè)設(shè)(1) (1) 如果如果 元素滿足元素滿足 稱稱 為為嚴(yán)格對角占優(yōu)陣嚴(yán)格對角占優(yōu)陣(2) (2) 如果如果 元素滿足元素滿足 且上式至少有一個不等式嚴(yán)格成立，且上式至少有一個不等式嚴(yán)格成立， 稱稱 為為弱對角占優(yōu)陣弱對角占優(yōu)陣。()ijn nAaA1(1,2, )niiijjjiaainAA1(1,2, )niiijjjiaainA30 設(shè)設(shè) ，如果：，如果： 為嚴(yán)格對角占優(yōu)，則解為嚴(yán)格對角占優(yōu)，則解 的的Jacobi迭代法，迭代法， Gauss-Seidel迭代法均收斂。迭代法均收斂。AxbAAxb3132103)(2103)(151)1(3)(321)