第八章 線性代數(shù)方程組迭代法

1、第八章第八章迭代法基礎迭代法基礎在實際應用中遇到的系數(shù)矩陣多為大型稀疏在實際應用中遇到的系數(shù)矩陣多為大型稀疏矩陣，如用求解線性方程組的直接法求解，矩陣，如用求解線性方程組的直接法求解，在計算機上會耗費大量的時間和存儲單元。在計算機上會耗費大量的時間和存儲單元。在許多應用問題中使用迭代法。在許多應用問題中使用迭代法。思思路路將將 改寫為改寫為 等價形式等價形式 ，建，建立迭代立迭代 , ,從初值從初值 出發(fā)，得出發(fā)，得到序列到序列 。AxbxBxg(1)( )kkxBxg(0)x()kx研究內(nèi)容：研究內(nèi)容： 如何建立迭代格式？如何建立迭代格式？ 收斂速度？收斂速度？ 向量序列的收斂條件？向量序列

2、的收斂條件？ 誤差估計？誤差估計？一般迭代法一般迭代法定義定義1 1 對方程組對方程組 ，化為等價方程，化為等價方程組組 ，設，設 為任取的初值，將上式寫為為任取的初值，將上式寫為迭代過程迭代過程這種迭代過程稱為這種迭代過程稱為逐次逼近法逐次逼近法，B B 稱為稱為迭代矩陣迭代矩陣。若若 稱逐次逼近法稱逐次逼近法收斂，收斂， 否則，稱否則，稱逐次逼近法逐次逼近法不收斂或發(fā)散不收斂或發(fā)散。(1)( )(0,1,)kkxBxg k( )*lim,kkxx(0)Axb AxBxg(0)x問題：問題：按上述思想迭代產(chǎn)生的向量序列按上述思想迭代產(chǎn)生的向量序列 在什在什 么條件下收斂于方程組么條件下收斂于

3、方程組Ax=bAx=b的解？的解？( )kx引進誤差向量引進誤差向量： ，其中，其中 為方為方程組的解，即有程組的解，即有所以，要使所以，要使 收斂到收斂到 ，則需研究，則需研究 在什么條在什么條件下有件下有 。*( )(1)kkxBxgxBxg( )( )*(1)*(1)2(2)(0)(0)(0)*()()kkkkkkxxB xxBBBxx( )kx*x( )( )*(0,1, )kkxx k*xB( )0()0()kkkBk 迭代法的收斂條件與誤差估計迭代法的收斂條件與誤差估計引理引理 當當k 時，時，Bk 0 0 ( ( B ) 1 ) 1定理定理1 1 設有線性方程組設有線性方程組 ，

4、那么逐次逼近，那么逐次逼近 法對任意初始向量法對任意初始向量 收斂的充分必要條件收斂的充分必要條件 是迭代矩陣是迭代矩陣B B的譜半徑的譜半徑 ( (B B ) )11。xBxg(0)x注：注：要檢驗一個矩陣的譜半徑小于要檢驗一個矩陣的譜半徑小于1 1比較困難，比較困難， 所以我們希望用別的辦法判斷收斂性。所以我們希望用別的辦法判斷收斂性。 注注: 1.1.因為矩陣范數(shù)因為矩陣范數(shù) 都可以直接用矩陣的元素都可以直接用矩陣的元素 計算，因此用定理計算，因此用定理2 2， 很容易判別逐次逼近法的收斂性。很容易判別逐次逼近法的收斂性。 2.2.定理定理2 2是充分條件，當找不到矩陣的某一范數(shù)小于是充

5、分條件，當找不到矩陣的某一范數(shù)小于1 1時，時， 并不能判斷并不能判斷迭代法不收斂。迭代法不收斂。12,BBB(1)(1)()|*|1|kkkBxxxxB1(1)(1)(0)|*|1|kkBxxxxB定理定理2 2 設線性方程組設線性方程組 有惟一解有惟一解 ，若存若存 在一個矩陣范數(shù)使得在一個矩陣范數(shù)使得 | B | 1, 則則迭代收斂迭代收斂, 且有下列誤差估計：且有下列誤差估計：xBxg*xnnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（8 8.1） 1 1雅克比（雅克比（JacobiJacobi）迭代法）迭代法設有設有n n階方程

6、組階方程組幾種常用的迭代法幾種常用的迭代法若系數(shù)矩陣非奇異，且若系數(shù)矩陣非奇異，且 (i = 1, 2, n)，將方程組將方程組0iia()()()11,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax（8.1）改寫成改寫成然后寫成迭代格式然后寫成迭代格式()()()(11,)(22)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax（8.2）（8.2）式

7、也可以簡單地寫為式也可以簡單地寫為), 2, 1(1)(1)1(nixabaxkjnijjijiiiki（8.3）11()()()AxbDL U xbDxL U xbxDL U xD b記記 , ,其中其中A D L U 112233nnaaDaa2131321230000nnnaLaaaaa 1213123230000nnnaaaaaUa 則雅克比迭代法的矩陣形式為：則雅克比迭代法的矩陣形式為：(8.4)(1)1( )1( )()(0,1,)kkkJxDL U xD bB xgk稱稱 為雅克比迭代矩陣。為雅克比迭代矩陣。1()JBDLU1 311 21 11 11 12 322 12 22

8、22 23 13 233 33 33 31230000nnnnnnn nn nn naaaaaaaaaaaaaaaaaaaaaaaa33111112131122212321313231123()00000000JnnnnnnnnBD L Uaaaaaaaaaaaaaaaa (1)( )( )( )( )111221331441111()kkkkknnxba xa xa xa xa(1)(1)( )( )( )2221 12332442221()kkkkknnxba xa xa xa xa(1)(1)(1)( )( )3331)kkkkknnxba xa xa xa x

9、a(1)(1)(1)(1)(1)1 12233111()kkkkknnnnnnnnnnxba xa xa xaxa 寫成矩陣形式：寫成矩陣形式：(1)1(1)( )1(1)( )(1)1( )1( )()()()()kkkkkkkkG SxDLxUxD bDL xUxbxDLUxDLbBxg2 2高斯高斯賽得爾賽得爾(Gauss-Seidel)(Gauss-Seidel)迭代法迭代法(8.5)(8.6)其中其中 稱為稱為高斯高斯賽得爾賽得爾迭代矩陣。迭代矩陣。11(),()G SgD Lb BD L U定理定理4 4 n n階矩陣階矩陣A A是嚴格對角占優(yōu)矩陣的充分必要條件是是嚴格對角占優(yōu)矩陣

10、的充分必要條件是 JacobiJacobi迭代法的迭代矩陣滿足迭代法的迭代矩陣滿足 BBJ J11。3 3JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的收斂性迭代法的收斂性定理定理5 5 如果如果A A是嚴格對角占優(yōu)矩陣，那么是嚴格對角占優(yōu)矩陣，那么JacobiJacobi和和G GS S 迭代法都收斂。迭代法都收斂。定理定理6 6 若若A A是是n n階正定矩陣，那么階正定矩陣，那么G-SG-S迭代法收斂。迭代法收斂。定理定理3 3 n n階矩陣階矩陣A A是嚴格對角占優(yōu)矩陣，則是嚴格對角占優(yōu)矩陣，則A A非奇異，且非奇異，且 所有對角元所有

11、對角元 。0 (1,2, )iiain注意的問題注意的問題（1 1）JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的迭代矩陣不同：迭代法的迭代矩陣不同：BJ =D-1(L+U), B G-S = (D-L)-1U（2 2）JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法收斂性沒有必然的迭代法收斂性沒有必然的 聯(lián)系。即當聯(lián)系。即當Gauss-SeidelGauss-Seidel法收斂時，法收斂時，JacobiJacobi法可能不收法可能不收 斂；而斂；而JacobiJacobi法收斂時，法收斂時，Gau

12、ss-SeidelGauss-Seidel法也可能不收斂法也可能不收斂（3 3）JacobiJacobi迭代和迭代和Gauss-SeidelGauss-Seidel迭代的特征方程：迭代的特征方程：()ijnnAaDLU10(L+U)0(L+U)0JIBIDDJacobiJacobi迭代：迭代：1112121222120nnnnnnaaaaaaaaaGauss-SeidelGauss-Seidel迭代：迭代：10() U0(L)U)0G SIBIDLD1112121222120nnnnnnaaaaaaaaa12312312321).121xxxaxxxxxx123123123221).2223x

13、xxbxxxxxx用用JacobiJacobi迭代法求解收斂，迭代法求解收斂，但用但用 Gauss-SeidelGauss-Seidel法不收斂。法不收斂。（4 4）舉例）舉例：用用JacobiJacobi迭代法求解不收斂，迭代法求解不收斂，但用但用 Gauss-SeidelGauss-Seidel法收斂。法收斂。12123231).221251xxcxxxxx系數(shù)矩陣系數(shù)矩陣A A是正定矩陣，因此用是正定矩陣，因此用 Gauss-SeidelGauss-Seidel法收斂。法收斂。1341231234123410 5783 11).3282322717xxxxxxdxxxxxxxx 線性方程

14、組的系數(shù)矩陣為線性方程組的系數(shù)矩陣為10015183032811227A是嚴格對角占優(yōu)的，所以是嚴格對角占優(yōu)的，所以Jacobi和和Gauss-Seidel迭代格式迭代格式均收斂。均收斂。)(1)1(11)1(1kjnijijkjijijiiikixaxabax(1)()1(1)(1, 2, )kkkiiixxxin)(1)1(11)()1()1 (kjnijijkjijijiiikikixaxabaxx（1）迭代）迭代（2）加速）加速（8.7）()(1)( )1(1)( )(1)kkkkxxDbLxUx(1)( )()(1)kkDL xDU xb(1)1( )1()(1)()kkxDLDU

15、xDLb即即超松馳超松馳迭代法（迭代法（SOR法）法） （Sequential Over-Relaxation)Sequential Over-Relaxation)矩陣形式：矩陣形式：注：注：1.1.稱稱 為為超松弛超松弛迭代矩陣。迭代矩陣。 2.2.稱稱 為為松弛因子。松弛因子。 3.3.當當 時，就是時，就是G-SG-S迭代法；當?shù)ǎ划?時，稱為低時，稱為低 松弛松弛迭代法；當?shù)?；?時，稱為時，稱為超松弛超松弛迭代法。迭代法。 4.SOR4.SOR法也稱為法也稱為G-SG-S迭代法的一種加速方法。迭代法的一種加速方法。 5.5.研究研究SORSOR法就是需要找到最佳法就是需要找到最佳松弛因子，使得松弛因子，使得迭代迭代 過程的收斂速度最快，即過程的收斂速度最快，即 。 6.6.在找最佳在找最佳松弛因子之前，先要