第5章線性方程組的迭代法

1、1第二章第二章 線性方程組的迭代線性方程組的迭代解法解法第二節(jié)第二節(jié) 迭代法的收斂性迭代法的收斂性第三節(jié)第三節(jié) 超松弛迭代法超松弛迭代法第一節(jié)第一節(jié) 基本迭代方法基本迭代方法21 基本迭代方法基本迭代方法一、問題的提出一、問題的提出1直接方法的缺陷直接方法的缺陷(以以Gauss消去法為代表消去法為代表)： 對于低中階數(shù)（對于低中階數(shù)（n100）的線性方程組十分有效，但）的線性方程組十分有效，但n很大時，特別是由某些微分方程數(shù)值解所提出來的線性方很大時，特別是由某些微分方程數(shù)值解所提出來的線性方程組，由于舍入誤差的積累以及計算機(jī)的存貯困難，直接程組，由于舍入誤差的積累以及計算機(jī)的存貯困難，直接方

2、法卻無能為力。方法卻無能為力。 2解決方法：（利用迭代方法）解決方法：（利用迭代方法） 迭代方法：把線性方程組的數(shù)值求解問題化為一迭代方法：把線性方程組的數(shù)值求解問題化為一個迭代序列來實現(xiàn)。個迭代序列來實現(xiàn)。 3具體做法具體做法 (2) 取任意初始向量取任意初始向量x(0)構(gòu)成迭代序列構(gòu)成迭代序列: 由于迭代方法能由于迭代方法能避免避免系數(shù)矩陣中系數(shù)矩陣中零元的存貯與計算零元的存貯與計算，特別，特別適用于解系數(shù)矩陣階數(shù)很高而非零元極少（即適用于解系數(shù)矩陣階數(shù)很高而非零元極少（即大型稀疏大型稀疏）的線）的線性方程組。性方程組。 (1) AxbxBxf(1)( ), 0,1,2, kkxBxfk(

3、 ), kxx kxBxf若（） 則有的的解解。就就是是即即bAxx4迭代格式：迭代格式：定義：定義： (1)( ), 0,1,2, kkxBxfk迭代矩陣：迭代矩陣：B矩矩陣陣迭代過程收斂：迭代過程收斂： 若序列若序列x(k)極限存在，稱此迭代過程極限存在，稱此迭代過程收斂收斂，否，否則稱為則稱為發(fā)散發(fā)散。 迭代迭代 法計算精度可控，特別適用于求解系數(shù)為大法計算精度可控，特別適用于求解系數(shù)為大型稀疏矩陣型稀疏矩陣 /* sparse matrices */ 的方程組。的方程組。5迭代法迭代法要解決的主要問題如下要解決的主要問題如下 ： 1.1.如何構(gòu)造迭代格式？如何構(gòu)造迭代格式？ 2.2.構(gòu)

4、造的格式所產(chǎn)生的序列在什么情況下收斂？構(gòu)造的格式所產(chǎn)生的序列在什么情況下收斂？ 3.3.如果收斂，收斂的速率如何？如果收斂，收斂的速率如何？ 4.4.近似解的誤差估計。近似解的誤差估計。(1)( ),1,2,kkxBxf k迭代方程迭代方程迭代格式迭代格式方程方程*,lim,),( )()2()1()0()0(2)0(1)0(xxxxxxxxkkTn 若若可可計計算算任任給給迭代迭代初值初值的的解解是是方方程程則則bAxx *收斂收斂Ax bxBxf 如何構(gòu)造如何構(gòu)造迭代方程迭代方程6二、二、Jacobi （雅可比）迭代法（雅可比）迭代法 nnnnnnnnnnbxaxaxabxaxaxabxa

5、xaxa.22112222212111212111 nnnnnnnnnnnnbxaxaaxbxaxaaxbxaxaax11112212122211212111.1.1.10 iia建立建立迭代格式迭代格式： nknnnknnnknknnkkknnkkbxaxaaxbxaxaaxbxaxaax)(11)(11)1(2)(2)(12122)1(21)(1)(21211)1(1.1.1.1可以縮寫為：可以縮寫為：), 2 , 1(11)(11)()1(nibxaxaaxinijkjijijkjijiiki 按此格式迭代求解的按此格式迭代求解的方法稱為方法稱為雅可比迭代雅可比迭代法法,簡稱簡稱J法。法

6、。7例例1 用雅可比迭代法解線性方程組用雅可比迭代法解線性方程組 2 . 453 . 82102 . 7210321321321xxxxxxxxx解解 生成雅可比迭代格式：生成雅可比迭代格式： 84. 01 . 02 . 083. 02 . 01 . 072. 02 . 01 . 0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 迭迭代代結(jié)結(jié)果果見見下下表表取取,000T)0(xkx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15.111.0999931.1999931.299991121.0999981.19

7、99981.299997 T3 . 12 . 11 . 1*準(zhǔn)確解準(zhǔn)確解x 從上表可以看出，迭代序列收斂于從上表可以看出，迭代序列收斂于x*，若取，若取x(12)作為近似解，則誤差不超過作為近似解，則誤差不超過 10-58寫成寫成矩陣形式矩陣形式：bxULDxbxULDbAx)()(bDxULDx11)(BfJacobi 迭代陣，簡記為迭代陣，簡記為BJbDxULDxkk111)()()(，其其中中分分解解成成把把ULDAA ),(diagnnaaaD2211,0001121nnnaaaL.,0001112nnnaaaU9三、三、Gauss Seidel（高斯（高斯塞德爾）迭代法塞德爾）迭代法

8、)(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)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 寫成寫成矩陣形式矩陣形式：bDUxLxDxkkk1111)()()()(bUxxLDkk)()()(1bLDUxLDxkk111)()()()(BfGauss-Seidel 迭代陣，迭代陣，簡記為簡記為BG

9、S10nixaxabaxnijkjijijkjijiiiki, , )()()(21111111Gauss-Seidel迭代法的分量形式為：迭代法的分量形式為：例例2 分別給出以下線性方程組的分別給出以下線性方程組的Jacobi迭代格式和迭代格式和Gauss-Seidel迭代格式：迭代格式： 3211164142315321xxx解解)()()(21331232164311122413151xxxxxxxxx原方程等價于原方程等價于11) ( ) ( ) ()()()()()()()()()(kkkkkkkkkxxxxxxxxx21133112321164311122413151建立建立Jac

10、obi迭代格式如下迭代格式如下 建立建立Gauss-Seidel迭代格式如下迭代格式如下 ) ( ) ( ) ()()()()()()()()()(12111331112321164311122413151kkkkkkkkkxxxxxxxxx12例例4 用高斯用高斯-塞德爾迭代法求解例塞德爾迭代法求解例1中的方程組中的方程組 建立建立Gauss-Seidel迭代格式迭代格式 解解840202083020107202010121113311123211. . . . )()()()()()()()()(kkkkkkkkkxxxxxxxxx，仍仍取取Tx),( )(0000迭代迭代8次可得次可得T

11、x).,.,.()(319999910999818 在本例中在本例中Gauss-Seidel迭代法比迭代法比Jacobi迭代法收斂快。這個迭代法收斂快。這個結(jié)論在多數(shù)情況下成立，但高斯結(jié)論在多數(shù)情況下成立，但高斯-塞德爾的收斂更快是有條件的。塞德爾的收斂更快是有條件的。 兩種方法都存在兩種方法都存在收斂性問題收斂性問題。 有例子表明：有例子表明：Gauss-Seidel法收斂時，法收斂時，Jacobi法可能不收斂；法可能不收斂；而而Jacobi法收斂時，法收斂時， Gauss-Seidel法也可能不收斂。法也可能不收斂。132 迭代法的收斂性迭代法的收斂性的收斂條件的收斂條件fBxxkk)()

12、(1*)()(xxekk11)()()(*)()*()(kkkBexxBfBxfBx)()(0eBekk迭代法收斂的充要條件迭代法收斂的充要條件:00)()(limlimeBekkkk定理定理 .)(, )()()(110BfBxxfxkk 收收斂斂的的充充分分必必要要條條件件是是迭迭代代法法和和右右端端向向量量對對于于任任意意初初始始向向量量1)(B 一、一般迭代法的收斂性一、一般迭代法的收斂性14 上述定理只是判別迭代格式收斂的上述定理只是判別迭代格式收斂的充分條件充分條件，但若，但若 1B，則不能下結(jié)論說迭代法發(fā)散，只能用，則不能下結(jié)論說迭代法發(fā)散，只能用進(jìn)行判斷。進(jìn)行判斷。1)(B )

13、()(1kkxx由上述定理知由上述定理知B=q 越小，收斂越快。越小，收斂越快。1B 同時可獲得迭代解的事后誤差估計，當(dāng)同時可獲得迭代解的事后誤差估計，當(dāng) （即迭代（即迭代法收斂較快）時，可用如下停機(jī)準(zhǔn)則控制迭代結(jié)束：法收斂較快）時，可用如下停機(jī)準(zhǔn)則控制迭代結(jié)束：注意：注意： )()()()(max 111kikinikkxxxx一一般般用用15二、二、Jacobi迭代法和迭代法和Gauss-Seidel迭代法的收斂性迭代法的收斂性11)(ULD 11)(ULD1 1、Jacobi方法收斂的條件方法收斂的條件 充要條件：充要條件：充分條件：充分條件：11)(ULD 11ULD)(2 2、Gau

14、ss-Seidel方法收斂的條件方法收斂的條件充要條件：充要條件：充分條件：充分條件：16定理定理 （充分條件）（充分條件）若若A 為為嚴(yán)格對角占優(yōu)陣嚴(yán)格對角占優(yōu)陣 ，則解，則解 的的Jacobi 和和 Gauss - Seidel 迭代法均收斂。迭代法均收斂。bAx 3、其它判別條件、其它判別條件 17上一頁上一頁 下一頁下一頁 返回返回 18上一頁上一頁 下一頁下一頁 返回返回 2. Gauss-Seidel方法收斂的條件方法收斂的條件19 1242043163473232121xxxxxxx例例（1）列出求解該方程組的）列出求解該方程組的Jacobi迭代格式，并判迭代格式，并判別是否收斂

15、；別是否收斂；（2）列出求解該方程組的）列出求解該方程組的Gauss-Seidel迭代格式，迭代格式，并判別是否收斂；并判別是否收斂；（3）取）取x(0)=(0,0,0)T，求，求Gauss-Seidel迭代法的前兩迭代法的前兩次迭代值次迭代值x(1) , x(2) .上一頁上一頁 下一頁下一頁 返回返回 20上一頁上一頁 下一頁下一頁 返回返回 考察系數(shù)矩陣A及2D-A410143034A4101430342AD由于A及2D-A都正定，故Jacobi迭代法收斂。21上一頁上一頁 下一頁下一頁 返回返回 考察系數(shù)矩陣A410143034A由于A對稱正定，故Gauss-Seidel迭代法收斂。2

16、2上一頁上一頁 下一頁下一頁 返回返回 -2.5. 4.)()()()()()()(121303111202112503225075057504xxxxxxx -2.375. . 2.)()()()()()()(22231321221221250352250750557504xxxxxxxTTxx).,.,.( , ).,()()(37525252522421 233 超松弛迭代法超松弛迭代法換個角度看換個角度看Gauss - Seidel 方法：方法：nijkjijijkjijiiikixaxabax111111)()()(iikikiarx)1()( 其中其中ri(k+1) =nijkji

17、jijkjijixaxab)()(111余項余項相當(dāng)于在相當(dāng)于在 的基礎(chǔ)上的基礎(chǔ)上加個余項加個余項生成生成 。)(kix)1( kix下面令下面令 ，希望通過選取合適的，希望通過選取合適的 來來加速收斂，這就是加速收斂，這就是逐次超松弛迭代法，逐次超松弛迭代法，簡記簡記SOR法法 。iikikikiarxx)1()()1( 稱為稱為松弛因子松弛因子 = 1Gauss - Seidel 法法SOR法法 /* Successive Over- Relaxation methods */上一頁上一頁 下一頁下一頁 返回返回 24寫成寫成矩陣形式矩陣形式：iikikikiarxx)1()()1( )(

18、)()()()(bUxLxDxxkkkk1111 bLDxUDLDxkk 1111)()()()()( Lf松弛迭代陣松弛迭代陣定理定理 設(shè)設(shè) A 可逆，且可逆，且 aii 0，松弛法從任意松弛法從任意 出發(fā)對出發(fā)對某個某個 收斂收斂 L 1 1。)(0 x要計算要計算 ( L ） 很很 復(fù)雜復(fù)雜 上一頁上一頁 下一頁下一頁 返回返回 )()()()(inijkjijijkjijiikibxaxaax11111 )()()()(kikikixxx1 )()()(kikixx 1125定理定理 （ 必要條件）必要條件）設(shè)設(shè) A 可逆，且可逆，且 aii 0，松弛法松弛法 從任意從任意 出發(fā)收斂出發(fā)收斂 0 0 2 2 。)(0 x上一頁上一頁 下一頁下一頁 返回返回 定理定理 （ 充分條件）充分條件）若若A 對稱正定，且有對稱正定，且有 0 0 2 2，則，則松弛法從任意松弛法從任意 出發(fā)收斂出發(fā)收斂。)(0 x例例9 建立下面方程組的建立下面方程組的SOR迭代格式迭代格式243024410143034321xxx解：解： SOR迭代格式如下迭代格式如下 ).().( ).()()()()()()()()()()()()()(kkkkkkkkkkkkkxxxxxxxxxxxxx3123132311212121116250572507506750 )()()()(