研究生數(shù)值分析(12)高斯-賽德爾(Gauss-Seidel)迭代法

1、.研究雅可比迭代法，我們發(fā)現(xiàn)在逐個求研究雅可比迭代法，我們發(fā)現(xiàn)在逐個求(1)kX的分量時，當(dāng)計算到的分量時，當(dāng)計算到(1)kix時時,分量分量(1)(1)11,kkixx都已經(jīng)求得，而仍用舊分量都已經(jīng)求得，而仍用舊分量( )( )11,kkixx計算計算(1)kix。由于新計算出的分量比舊分量準(zhǔn)確些，。由于新計算出的分量比舊分量準(zhǔn)確些，(1)(1)11,kkixx求出，馬上就用新分量求出，馬上就用新分量(1)(1)11,kkixx代替雅可比迭代法中代替雅可比迭代法中()()11,kkixx來求來求(1)kix, 這就是高斯這就是高斯-賽德爾賽德爾(Gauss-Seidel)迭代法。迭代法。2

2、高斯高斯-賽德爾（賽德爾（Gauss-Seidel）迭代法）迭代法因此設(shè)想一旦新分量因此設(shè)想一旦新分量.高斯高斯-賽德爾迭代公式如下：賽德爾迭代公式如下：(1)( )( )( )112 213 31111(1)(1)( )( )221 123 32211(1)(1)(1)(1)( )( )1 12 2, 11, 11(1)(1 11()1()1()1(kkkkn nkkkkn nkkkkkkiiii iii iiin niiiknnnnxa xa xa xbaxa xa xa xbaxa xa xaxaxa xbaxa xa 1)(1)(1)2 2,11)kkknn nnna xaxb （5）

3、.其矩陣表示形式為其矩陣表示形式為(1)1(1)( )()kkkXDLXUXb現(xiàn)將現(xiàn)將(1)kX顯式化，由顯式化，由 (1)( )()kkDL XUXb得得 (1)1( )1()()kkXDLUXDLb令令 1()GBDLU（稱為高斯稱為高斯-賽德爾（賽德爾（Gauss-Seidel）迭代矩陣），）迭代矩陣），1()GfDLb則得則得 (1)( )kkGGXB Xf為高斯為高斯-賽德爾迭代法的矩陣表示形式。賽德爾迭代法的矩陣表示形式。.1()GBDLU0GIB1()0IDLU1()()0DLDLU1()0DL()0DLU 上式左端為將系數(shù)矩陣上式左端為將系數(shù)矩陣 A 的對角線及對角線的對角線及

4、對角線以下元素同乘以以下元素同乘以 后所得新矩陣的行列式。后所得新矩陣的行列式。 我們用定理我們用定理2來判斷高斯來判斷高斯-賽德爾迭代公式是否賽德爾迭代公式是否收斂，需要考慮高斯收斂，需要考慮高斯-賽德爾迭代矩陣賽德爾迭代矩陣的特征方程的特征方程即即將上式寫成將上式寫成由于由于所以所以.例例9 用高斯用高斯-賽德爾迭代法解方程組賽德爾迭代法解方程組1231231231023210152510 xxxxxxxxx解：解：相應(yīng)的高斯相應(yīng)的高斯-賽德爾迭代公式為賽德爾迭代公式為(1)( )( )123(1)(1)( )213(1)(1)(1)3120.20.10.30.20.11.50.20.42

5、kkkkkkkkkxxxxxxxxx.取迭代初值取迭代初值(0)(0)(0)(0)123(,)(0,0,0)TTXxxx按此迭代公式進行迭代，計算結(jié)果為按此迭代公式進行迭代，計算結(jié)果為k( )1kx( )2kx( )3kx01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.9999.高斯高斯-賽德爾迭代矩陣賽德爾迭代矩陣GB的特征方程為的特征方程為即即 2(500542)0解得解得 1232717292717290,50050005211021210.于是于是 2717

6、29()0.13721500GB因而高斯因而高斯-賽德爾迭代公式是收斂的。賽德爾迭代公式是收斂的。我們先引入一個叫矩陣譜半徑的概念。我們先引入一個叫矩陣譜半徑的概念。3 迭代法收斂條件與誤差估計迭代法收斂條件與誤差估計.定義定義 矩陣矩陣n nAR的所有特征值的所有特征值(1,2, )iin的模的最大值稱為矩陣的模的最大值稱為矩陣 A 的譜半徑的譜半徑,記作記作( )A即即1()maxiinA A1A 前面前面,我們在應(yīng)用我們在應(yīng)用雅可比迭代法雅可比迭代法與與高斯高斯-賽德爾迭賽德爾迭代法代法解一階線性方程組時，判斷各迭代公式是收斂還解一階線性方程組時，判斷各迭代公式是收斂還是發(fā)散，都要計算雅

7、可比迭代矩陣是發(fā)散，都要計算雅可比迭代矩陣 BJ 與高斯與高斯-賽德爾賽德爾迭代矩陣迭代矩陣 BG 的特征值的特征值.由于矩陣由于矩陣 A 有些算子范數(shù)有些算子范數(shù)(比比如如 與與 )遠比矩陣遠比矩陣 A 的特征值容易計算的特征值容易計算,為此給為此給出如下結(jié)論。出如下結(jié)論。.定理定理3 矩陣矩陣A的譜半徑不超過矩陣的譜半徑不超過矩陣A的任何的任何一種算子范數(shù)一種算子范數(shù) , 即即證明：證明：設(shè)設(shè)為為A的任一特征值，的任一特征值，X為對應(yīng)于為對應(yīng)于的的A的特征向量，即的特征向量，即 AX= X, (X 0) 由范數(shù)的性質(zhì)立即可得由范數(shù)的性質(zhì)立即可得rrrrrXXAXAX因為因為 X 0 ， 所

8、以所以 rA即即A的任一特征值的模都不超過的任一特征值的模都不超過rA于是于是( )rAA( )rAA.定理給出了一階線性定常迭代法定理給出了一階線性定常迭代法(1)( )kkXBXf收斂的充分條件，它表明只要迭代矩陣收斂的充分條件，它表明只要迭代矩陣 B 的某種子的某種子范數(shù)范數(shù)小于小于1，立即可以斷定該迭代過程對任給，立即可以斷定該迭代過程對任給*X 在例在例8例例9中，我們分別用中，我們分別用雅可比迭代法雅可比迭代法和和高斯高斯-賽德爾迭代法賽德爾迭代法解方程組解方程組1231231231023210152510 xxxxxxxxx初始向量都收斂于方程組初始向量都收斂于方程組AX=b的唯

9、一解的唯一解rB.雅可比迭代矩陣雅可比迭代矩陣 00.20.10.200.10.20.40JB0.61JB高斯高斯-賽德爾迭代矩陣賽德爾迭代矩陣 00.20.100.040.1200.0560.068GB0.31GB雅可比迭代過程必收斂；雅可比迭代過程必收斂；高斯高斯-賽德爾迭代過程也收斂。賽德爾迭代過程也收斂。.由定理的誤差估計式由定理的誤差估計式( )*(1)(0)1kkBXXXXB1,2,3,k 可以看出，可以看出，B且可用來估計迭代次數(shù)。且可用來估計迭代次數(shù)。越小收斂速度越快，越小收斂速度越快，在例在例8例例9中，顯然中，顯然GB比比JB小，小，所以高斯所以高斯-賽德爾迭代法比雅可比迭

10、代法收斂速度快。賽德爾迭代法比雅可比迭代法收斂速度快。.若在例若在例8例例9中要求近似解中要求近似解( )kX的誤差的誤差( )*410kXX則由誤差估計式知，只要則由誤差估計式知，只要 k 滿足滿足(1)(0)4101kBXXB將將(0)(1)0.6,(0,0,0) ,(0.3000,1.5000,2.0000)TTJBXX代入得代入得21.18k ，故，故Jacobi迭代迭代22次即可；次即可；(0)(1)0.3,(0,0,0) ,(0.3000,1.5600,2.68400)TTGBXX代入得代入得8.76k ，故，故Gauss-Seidel迭代迭代9次就可以。次就可以。將將.定理定理4

11、 若方程組若方程組AX=b的系數(shù)矩陣的系數(shù)矩陣ijn nAa按行嚴(yán)格對角占優(yōu)或按列嚴(yán)格對角占優(yōu)，即滿足條件按行嚴(yán)格對角占優(yōu)或按列嚴(yán)格對角占優(yōu)，即滿足條件1niiijjj iaa(1,2, )in或或 1njjijiijaa(1,2, )jn則方程組則方程組AX=b有唯一解，且對任意初始向量有唯一解，且對任意初始向量(0)X雅可比迭代法與高斯雅可比迭代法與高斯-賽德爾迭代法都收斂。賽德爾迭代法都收斂。 對于對于雅可比迭代法雅可比迭代法與與高斯高斯-賽德爾迭代法賽德爾迭代法，還，還有一些使用方便的充分條件，其中主要有：有一些使用方便的充分條件，其中主要有：.定理定理5 若方程組若方程組 AX=b

12、的系數(shù)矩陣的系數(shù)矩陣ijn nAa為對稱為對稱正定矩陣。則對任意初始向量正定矩陣。則對任意初始向量 高斯高斯(0)X-賽德爾迭代法賽德爾迭代法都收斂。都收斂。ij n nAa 如在例如在例8例例9中，由于系數(shù)矩陣中，由于系數(shù)矩陣A是嚴(yán)格對角是嚴(yán)格對角占優(yōu)，由定理占優(yōu)，由定理4立即可斷定用雅可比迭代法與高斯立即可斷定用雅可比迭代法與高斯-賽德爾迭代法求解時，迭代過程都收斂。賽德爾迭代法求解時，迭代過程都收斂。 只要方程組只要方程組 AX=b 的系數(shù)矩陣的系數(shù)矩陣 滿足滿足定理定理4或定理或定理5的條件，就可以十分方便地判斷相的條件，就可以十分方便地判斷相應(yīng)迭代過程的收斂性。應(yīng)迭代過程的收斂性。.

13、又如矩陣又如矩陣4222232314A是對稱正定陣（是對稱正定陣（實對稱陣是正定陣的，如果實二次型實對稱陣是正定陣的，如果實二次型12( ,)Tnf x xxX AX正定正定),由定理由定理5可判定用高斯可判定用高斯-賽德爾迭代法求解方程組賽德爾迭代法求解方程組AXb時，迭代過程一定收斂。時，迭代過程一定收斂。.例例10 考察用雅可比迭代法和高斯考察用雅可比迭代法和高斯-賽德爾迭代法賽德爾迭代法1221111,12211Ab 解：解：先計算迭代矩陣先計算迭代矩陣1022()101220JBDLU 解方程組解方程組 AX=b 的收斂性，其中的收斂性，其中.1022()023002GBDLU再計算再計算BJ與與BG的特征值和譜