e基本的矩陣迭代法

1、.1第三章線性方程組的迭代解法 基本的矩陣分裂迭代法基本的矩陣分裂迭代法.2本講內(nèi)容本講內(nèi)容l Jacobi 迭代算法迭代算法l Gauss-Seidel 迭代算法迭代算法l SOR 迭代算法迭代算法l 收斂性分析收斂性分析n 矩陣分裂迭代法的典型代表矩陣分裂迭代法的典型代表.3Jacobi 迭代迭代考慮線性方程組考慮線性方程組Ax = b其中其中 A=(aij)n n 非奇異，且對(duì)角線元素全不為非奇異，且對(duì)角線元素全不為 0。1122diag(,)nnDaaa 211,10 0,0nn naLaa l 將將 A 分裂成分裂成 A = D - L- U， 其中其中1211,000nnnaaUa

2、 .4Jacobi 迭代迭代(1)1( )1()kkxDLU xD b k = 0, 1, 2, 令令 M = D，N = L + U，可得，可得 雅可比雅可比 (Jacobi) 迭代方法迭代方法 Jacobi 迭代迭代l 迭代矩陣記為：迭代矩陣記為：1()JDLU l 分量形式：分量形式：1(1)11inkiiijjijjiijj ixba xa xa i = 1, 2, , n， k = 0, 1, 2, .5.6Gauss-Seidel 迭代迭代l 在計(jì)算在計(jì)算 時(shí)，如果用時(shí)，如果用 代替代替 ，則可能會(huì)得到更好的收斂效果。則可能會(huì)得到更好的收斂效果。(1)kix (1)(1)11,kk

3、ixx( )( )11,kkixx (1)( )( )( )11122133111(1)( )( )( )22211233222(1)( )( )( )1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa (1)( )( )( )11122133111(1)(1)( )( )22211233222(1)(1)(1)(1)1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa .7Gauss-Seidel 迭代迭代 (1)1(1

4、)( )kkkxDbLxUx 寫成矩陣形式寫成矩陣形式:此迭代方法稱為此迭代方法稱為 高斯高斯-塞德爾塞德爾 (Gauss-Seidel) 迭代法迭代法k = 0, 1, 2, 11(1)( )kkxDLUxDLb 可得可得1GDLUl 迭代矩陣記為：迭代矩陣記為：.8SOR 迭代迭代l 為了得到更好的收斂效果，可在修正項(xiàng)前乘以一個(gè)為了得到更好的收斂效果，可在修正項(xiàng)前乘以一個(gè) 松弛因子松弛因子 ，于是可得迭代格式，于是可得迭代格式在在 G-S 迭代中迭代中 (1)(1)(1)( )( )11,11,11,kkkkkiiii iii iii nniixba xaxaxa xa 1(1)( )1(

5、 )inkkiijjijjiijj ikiba xa xax (1)1(1)()1()inkkiijjijjiijkiij ikba xaaxxx .9SOR 迭代迭代 (1)( )1(1)( )( )kkkkkxxDbLxUxDx 11(1)( )(1)kkxDLDU xDLb 寫成矩陣形式寫成矩陣形式:可得可得 SOR (Successive Over-Relaxation) 迭代方法迭代方法 1(1)LDLDU l 迭代矩陣記為：迭代矩陣記為：l SOR 的優(yōu)點(diǎn)的優(yōu)點(diǎn)：通過選取合適的：通過選取合適的 ，可獲得更快的收斂速度，可獲得更快的收斂速度l SOR 的缺點(diǎn)的缺點(diǎn)：最優(yōu)參數(shù)最優(yōu)參數(shù)

6、的的選取比較困難選取比較困難.10Jacobi、G-S、SORq Jacobi 迭代迭代(1)1( )1()kkxDLU xD b 1(1)( )( )11inkkkiiijjijjiijj ixba xa xa q SOR 迭代迭代 11(1)( )(1)kkxDLDU xDLb 1(1)( )(1)( )1inkkkkiiiijjijjiijj ixxba xa xa 11, (1)MDLNDUq G-S 迭代迭代 11(1)( )kkxDLUxDLb 1(1)(1)( )11inkkkiiijjijjiijj ixba xa xa , MDLNU, MDNLU.11舉例舉例例例：分別用分

7、別用 Jacobi、G-S、SOR 迭代解線性方程組迭代解線性方程組123210113180125xxx 取初始向量取初始向量 x(0) = ( 0, 0, 0 )，迭代過程中小數(shù)點(diǎn)后保留，迭代過程中小數(shù)點(diǎn)后保留 4 位。位。解：解：Jacobi 迭代：迭代： (1)( )12(1)( )( )213(1)( )32128352kkkkkkkxxxxxxx 迭代可得：迭代可得： x(1) = ( 0.5000, 2.6667, -2.5000 )Tx(21) = ( 2.0000, 3.0000, -1.0000 )T2*31x .12舉例舉例G-S 迭代：迭代： (1)( )12(1)(1)

8、( )213(1)(1)32128352kkkkkkkxxxxxxx x(1) = ( 0.5000, 2.8333, -1.0833 )Tx(9) = ( 2.0000, 3.0000, -1.0000 )T迭代可得：迭代可得： .13舉例舉例SOR 迭代：迭代： (1)( )( )( )1112(1)( )(1)( )( )22123(1)( )(1)( )3323122833522kkkkkkkkkkkkkxxxxxxxxxxxxx 取取 = 1.1，迭代可得，迭代可得x(1) = ( 0.5500, 3.1350, -1.0257 )Tx(7) = ( 2.0000, 3.0000,

9、-1.0000 )T如何確定如何確定 SOR 迭代中的最優(yōu)松弛因子是一件迭代中的最優(yōu)松弛因子是一件很困難很困難的事的事.14.15收斂性分析收斂性分析(1)( )kkxBxf 定理定理：對(duì)任意初始向量對(duì)任意初始向量 x(0)，上述迭代格式收斂的充要條件是，上述迭代格式收斂的充要條件是( )1B 定理定理：若存在算子范數(shù)若存在算子范數(shù) | |，使得，使得 |B| 1，對(duì)任意的初始向量，對(duì)任意的初始向量 x(0)，上述迭代格式收斂。，上述迭代格式收斂。.16l Jacobi 迭代收斂的迭代收斂的充要充要條件條件 (J)1l G-S 迭代收斂的迭代收斂的充要充要條件條件 (G)1l SOR 迭代收斂

10、的迭代收斂的充要充要條件條件 (L )1收斂性收斂性(A)A收斂性定理收斂性定理l Jacobi 迭代收斂的迭代收斂的充分充分條件條件 |J| 1l G-S 迭代收斂的迭代收斂的充分充分條件條件 |G| 1l SOR 迭代收斂的迭代收斂的充分充分條件條件 |L | 1譜半徑1(A)maxii n .17.18收斂性分析收斂性分析(1)( )kkxBxf B = M-1N定理定理：若存在算子范數(shù)若存在算子范數(shù) | |，使得，使得 |B| = q 1，則，則證明：證明：P112( )(0)kkxxqxx 迭代法收斂迭代法收斂 ( )( )(1)1kkkqxxxxq ( )(1)(0)1kkqxxx

11、xq .19系數(shù)矩陣法系數(shù)矩陣法-對(duì)角占優(yōu)矩陣對(duì)角占優(yōu)矩陣且且至少有一個(gè)至少有一個(gè)不等式嚴(yán)格成立，則稱不等式嚴(yán)格成立，則稱 A 為為 弱對(duì)角占優(yōu)弱對(duì)角占優(yōu)；若若所有不等式所有不等式都嚴(yán)格成立，則稱都嚴(yán)格成立，則稱 A 為為 嚴(yán)格對(duì)角占優(yōu)嚴(yán)格對(duì)角占優(yōu)。( i = 1, 2, . , n )定義定義：設(shè)設(shè) A Rn n，若，若1, |niiijjj iaa .20Jacobi、G-S 收斂性收斂性引理引理3-2：若若 A 嚴(yán)格對(duì)角占優(yōu)嚴(yán)格對(duì)角占優(yōu)，則，則 A 非奇異非奇異定理定理3-25：若若 A 嚴(yán)格對(duì)角占優(yōu)嚴(yán)格對(duì)角占優(yōu)，則，則 Jacobi 迭代和迭代和 G-S 迭代均迭代均收斂收斂 定理定理

12、：若若 A 對(duì)稱，且對(duì)角線元素均大于對(duì)稱，且對(duì)角線元素均大于 0，則，則Jacobi 迭代收斂的充要條件是迭代收斂的充要條件是 A 與與 2D-A 均正定；均正定；(1) G-S 迭代收斂的充要條件是迭代收斂的充要條件是 A 正定。正定。.21SOR 收斂性收斂性定理定理：若若 SOR 迭代收斂，則迭代收斂，則 0 2。l SOR 收斂的必要條件收斂的必要條件定理定理：若若 A 對(duì)稱正定，且對(duì)稱正定，且 0 2，則則 SOR 迭代收斂。迭代收斂。l SOR 收斂的充分條件收斂的充分條件定理定理：若若 A 嚴(yán)格對(duì)角占優(yōu)，且嚴(yán)格對(duì)角占優(yōu)，且 0 1，則則 SOR 迭代收迭代收斂。斂。.22舉例舉例

13、例例：設(shè)設(shè) ，給出，給出 Jacobi 和和 G-S 收斂的充要條件收斂的充要條件 111aaAaaaa 解：解：A 對(duì)稱，且對(duì)角線元素均大于對(duì)稱，且對(duì)角線元素均大于 0，故，故 (1) Jacobi 收斂的充要條件是收斂的充要條件是 A 和和 2D-A 均正定均正定(2) G-S 收斂的充要條件是收斂的充要條件是 A 正定正定A 正定正定2212310,10,(1) (12 )0DDaDaa 0.51a 2D-A 正定正定2212310,10,(1) (12 )0DDaDaa 0.50.5aJacobi 收斂的充要條件是：收斂的充要條件是：-0.5a0.5G-S 收斂的充要條件是：收斂的充要條件是：-0.5a1.23舉例舉例解法二：解法二：Jac