迭代矩陣譜半徑[基礎(chǔ)教育]

1、數(shù)值分析數(shù)值分析1010 迭代法的收斂性迭代法的收斂性 Convergence of iterative method 迭代矩陣譜半徑迭代矩陣譜半徑 Spectral radius 對角占優(yōu)矩陣對角占優(yōu)矩陣 diagonally dominant matrix 1一類課 原始方程原始方程: A x = b 記記 (k) = x(k) x* ( k = 0, 1, 2, 3, ) 則有則有 (k+1) = B (k) (k) = B (k-1) ( k = 1, 2, 3, ) 迭代格式迭代格式: x(k+1) = B x(k) + f x(k+1) x*= B(x(k) x*) 設(shè)方程組的精確

2、解為設(shè)方程組的精確解為 x*,則有則有 x* = B x* + f 2/15 2一類課 0lim0lim )( k kk B k (1) (k) = B (k-1)=B2 (k-2)=Bk (0) 1|0lim )( B k k (2) 0lim *)( xx k k *)( limxx k k 迭代格式迭代格式 x(k+1) = B x(k) + f 收斂收斂 ！ 3/15 3一類課 證證: 由由 (k) = B (k-1),得得 | (k)| | B| | (k-1)| ( k = 1, 2, 3, ) 0lim )( k k 所以所以 命題命題 若若|B|1,則迭代法則迭代法 x(k+1

3、) =B x(k) +f 收斂收斂 | (k)| | B|k | (0)| 0|lim|lim )0()( k k k k B | B| 1 4/15 4一類課 矩陣矩陣A的譜的譜 設(shè)設(shè)n階方陣階方陣A的的n個特征值為個特征值為: n , 21 則稱集合則稱集合, 21n 為為A的譜的譜. 記為記為 ch A 矩陣矩陣A的譜半徑的譜半徑 |max)( 1 k nk A 注注1: 當(dāng)當(dāng)A是對稱矩陣時是對稱矩陣時, |A|2 = (A) 注注2: 對對 Rn n 中的范數(shù) 中的范數(shù)| |,有有 (A) | A | 特征值取模最大特征值取模最大 5/15 5一類課 定理定理4.1 迭代法迭代法 x(

4、k+1) = B x(k) + f 收斂收斂 譜半徑譜半徑(B) 1 證證: 對任何對任何 n 階矩陣階矩陣B都存在非奇矩陣都存在非奇矩陣P使使 B = P 1 J P 其中其中, J 為為B的的 Jordan 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 nn r J J J J 2 1 ii nn i i i J 1 1 其中其中, Ji 為為Jordan塊塊 6/15 6一類課 其中其中,i 是矩陣是矩陣B的特征值的特征值, 由由 B = P 1 J P B k = (P 1 J P) (P 1 J P) (P 1 J P)= P 1 J k P 迭代法迭代法 x(k+1) = B x(k) + f 收斂收斂 0lim

5、 k k B 0lim k k J 0lim k i k (i = 1, 2, r) 1| i (i = 1, 2, r) 1|max 1 i ri 譜半徑譜半徑 (B) 1 7/15 7一類課 Ans= 1.2604e-005 1)( J B 例例 線性方程組線性方程組 A x = b, 分別取系數(shù)矩陣為分別取系數(shù)矩陣為 122 111 221 1 A 211 111 112 2 A 試分析試分析Jacobi 迭代法和迭代法和 Seidel 迭代法的斂散性迭代法的斂散性 D=diag(diag(A1); B1=D(D-A1); max(abs(eig(B1) 022 101 220 J B(

6、1) A1=1,2,-2;1,1,1;2,2,1 8/15 8一類課 200 320 220 S B DL=tril(A1) B1=DL(DL-A1) max(abs(eig(B1) Ans= 2 2)( S B (2) A2=2, -1, 1; 1, 1, 1; 1, 1, -2 02/12/1 101 2/12/10 J B D=diag(diag(A2) B2=D(D-A2) max(abs(eig(Bj) 1180. 1)( J B Ans= 1.1180 9/15 9一類課 2/100 2/12/10 2/12/10 S B DL=tril(A2) B2=DL(DL-A2) max(

7、abs(eig(B2) Ans= 1/2 2/1)( S B 兩種迭代法之間沒有直接聯(lián)系兩種迭代法之間沒有直接聯(lián)系 對矩陣對矩陣A1,求求A1 x = b 的的Jacobi迭代法收斂迭代法收斂, 而而Gauss-Seidel迭代法發(fā)散迭代法發(fā)散; 對矩陣對矩陣A2,求求A2 x = b 的的Jacobi迭代法發(fā)散迭代法發(fā)散, 而而Gauss-Seidel迭代法收斂迭代法收斂. 10/15 10一類課 定理定理4.2 :設(shè)設(shè)x*為方程組為方程組 Ax=b 的解的解 若若|B|1,則對迭代格式則對迭代格式 x(k+1) = B x(k) + f 有有 | |1 | |*| )0()1()( xx

8、B B xx k k | |1 | |*| )1()()( kkk xx B B xx(1) (2) 誤差估計(jì)定理誤差估計(jì)定理 11/15 11一類課 證證 由由|B| |-1| + |-1| 10 |-1| + |-1| 15 |-1| + |-1| |a11| |a12| + |a13| |a22| |a21| + |a23| |a33| |a31| + |a32| 14/15 14一類課 定理定理4.3 若若Ax=b的系數(shù)矩陣的系數(shù)矩陣A是嚴(yán)格對角占優(yōu)是嚴(yán)格對角占優(yōu) 矩陣矩陣,則則Jacobi迭代和迭代和Seidel迭代均收斂迭代均收斂 證證: 由于矩陣由于矩陣A嚴(yán)格對角占優(yōu)嚴(yán)格對角占優(yōu)

9、 由由A矩陣構(gòu)造矩陣構(gòu)造Jacobi迭代矩陣迭代矩陣BJ = D-1(D A) 第第i行絕對值求和行絕對值求和 n ij j ij ii a a 1 | | 1 所以所以1 | | 1 max| 1 1 n ij j ij ii ni J a a B 1| | 1 1 n ij j ij ii a a n ij j ijii aa 1 | 15/15 15一類課 矩陣的矩陣的條件數(shù)條件數(shù)概念概念 方程組方程組 Ax = b, 右端項(xiàng)右端項(xiàng) b 有一擾動有一擾動 引起方程組解引起方程組解 x 的擾動的擾動 b x 設(shè)設(shè) x 是方程組是方程組 Ax = b 的解的解,則有則有 bbxxA )( 化

10、簡化簡,得得bxA bAx 1 | 1 bAx 由由 Ax = b 得得 |xAb | | | 1 b A x 所以所以 | | |)|(| | | 1 b b AA x x 12/16 16一類課 定義條件數(shù)定義條件數(shù): Cond(A) = |A1 | |A| 或或 C(A) = |A1 | |A| 當(dāng)條件數(shù)很大時當(dāng)條件數(shù)很大時,方程組方程組 Ax = b是病態(tài)問題是病態(tài)問題; 當(dāng)條件數(shù)較小時當(dāng)條件數(shù)較小時,方程組方程組 Ax = b是良態(tài)問題是良態(tài)問題 |)(|1|)(| 11111 AAIAAAAI IAAIAAI 111 )( 注注: 11111 )()( AAIAAIAAI |1 1

11、 |)(| 1 11 AA AAI 13/16 17一類課 類似類似,設(shè)方程組設(shè)方程組 Ax = b,矩陣矩陣A 有一擾動有一擾動 時時, 將引起方程組解將引起方程組解x的擾動的擾動 A x 設(shè)設(shè) x 是方程組是方程組 Ax = b 的解的解,則有則有 bxxAA )( 化簡化簡,得得AxxAA )( AxAAAIx 111 )( 取范數(shù)取范數(shù) |)(| 111 xAAAAIx | | |1 | | | 1 1 A A AA AA x x 14/16 18一類課 7/16/15/14/1 6/15/14/13/1 5/14/13/12/1 4/13/12/11 A 階數(shù)階數(shù) 4 5 6 條件數(shù)條件數(shù) 19.4105 2.9107 9.8108 條件數(shù)條件數(shù)2 1.5104 4.7105 1.4107 條件數(shù)條件數(shù) 9.4105 2.9107 9.8108 A famous example of a badly conditioned matrix 15/16 19一類課 ans= -2.4000 27.0