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

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

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

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

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

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

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

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

8、22 22 23 13 233 33 33 31230000nnnnnnn nn nn naaaaaaaaaaaaaaaaaaaaaaaa33111112131122212321313231123()00000000JnnnnnnnnBD L Uaaaaaaaaaaaaaaaa )(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434) 1(232) 1(13133) 1(3bxaxaxaxaaxknnkkkk)(1)1(11)1(33)

9、1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 寫成矩陣形式：寫成矩陣形式：(1)1(1)( )1(1)( )(1)1( )1( )()()()()kkkkkkkkG SxDLxUxD bDL xUxbxDLUxDLbBxg2 2高斯高斯賽得爾賽得爾(Gauss-Seidel)(Gauss-Seidel)迭代法迭代法(7.5)(7.6)其中其中 稱為稱為高斯高斯賽得爾賽得爾迭代矩陣。迭代矩陣。11(),()G SfD Lb BD LU定理定理4 4 n n階矩陣階矩陣A A是嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要條件是是嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要條件是 JacobiJacob

10、i迭代法的迭代矩陣滿足迭代法的迭代矩陣滿足 BBJ J11。3 3JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的收斂性迭代法的收斂性定理定理5 5 如果如果A A是嚴(yán)格對(duì)角占優(yōu)矩陣，那么是嚴(yán)格對(duì)角占優(yōu)矩陣，那么JacobiJacobi和和G GS S 迭代法都收斂。迭代法都收斂。定理定理6 6 若若A A是是n n階正定矩陣，那么階正定矩陣，那么G-SG-S迭代法收斂。迭代法收斂。定理定理3 3 n n階矩陣階矩陣A A是嚴(yán)格對(duì)角占優(yōu)矩陣，則是嚴(yán)格對(duì)角占優(yōu)矩陣，則A A非奇異，且非奇異，且 所有對(duì)角元所有對(duì)角元 。0 (1,2, )iiain注

11、意的問題注意的問題（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)系。即當(dāng)聯(lián)系。即當(dāng)Gauss-SeidelGauss-Seidel法收斂時(shí)，法收斂時(shí)，JacobiJacobi法可能不收法可能不收 斂；而斂；而JacobiJacobi法收斂時(shí)，法收斂時(shí)，Gauss-SeidelGauss-Seide

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

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

14、015183032811227A是嚴(yán)格對(duì)角占優(yōu)的，所以是嚴(yán)格對(duì)角占優(yōu)的，所以Jacobi和和Gauss-Seidel迭代格式迭代格式均收斂。均收斂。)(1)1(11)1(1kjnijijkjijijiiikixaxabax(1)()(1)(1)(1, 2, )kkkiiixxxin)(1)1(11)()1()1 (kjnijijkjijijiiikikixaxabaxx（1）迭代）迭代（2）加速）加速（7.7）()(1)( )1(1)( )(1)kkkkxxDbLxUx(1)( )()(1)kkDL xDU xb(1)1( )1()(1)()kkxDLDU xDLb即即超松馳超松馳迭代法（迭代

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