迭代矩陣譜半徑經(jīng)典實用

1、迭代矩陣譜半徑數(shù)值分析數(shù)值分析1010迭代法的收斂性迭代法的收斂性convergence of iterative method迭代矩陣譜半徑迭代矩陣譜半徑spectral radius對角占優(yōu)矩陣對角占優(yōu)矩陣diagonally dominant matrix 迭代矩陣譜半徑原始方程原始方程: 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* + f2/15迭代矩陣譜半徑0lim0lim)( kkkbk (1) (k) = b (k-1)=b2 (k-2)=bk (0)1|0lim)( bkk (2)0lim*)( xxkk*)(limxxkk 迭代格式迭代格式 x(k+1) = b x(k) + f 收斂收斂 ！3/15迭代矩陣譜半徑證證: 由由 (k) = b (k-1),得得 | (k)| | b| | (k-1)| ( k = 1, 2, 3, )0lim)( kk 所以所以命題命題 若若|b|1,則迭代法則迭代法 x(k+1) =b x(k) +f 收斂收斂| (k

3、)| | b|k | (0)| 0|lim|lim)0()( kkkkb| b| 14/15迭代矩陣譜半徑矩陣矩陣a的譜的譜設(shè)設(shè)n階方陣階方陣a的的n個特征值為個特征值為: n ,21則稱集合則稱集合,21n 為為a的譜的譜. 記為記為 ch a矩陣矩陣a的譜半徑的譜半徑|max)(1knka 注注1: 當當a是對稱矩陣時是對稱矩陣時, |a|2 = (a) 注注2: 對對 rnn 中的范數(shù)中的范數(shù)| |,有有 (a) | a |特征值取模最大特征值取模最大5/15迭代矩陣譜半徑定理定理4.1 迭代法迭代法 x(k+1) = b x(k) + f 收斂收斂 譜半徑譜半徑(b) 1證證: 對任何

4、對任何 n 階矩陣階矩陣b都存在非奇矩陣都存在非奇矩陣p使使 b = p 1 j p其中其中, j 為為b的的 jordan 標準型標準型nnrjjjj 21iinniiij 11其中其中, ji 為為jordan塊塊6/15迭代矩陣譜半徑其中其中,i 是矩陣是矩陣b的特征值的特征值, 由由 b = p 1 j pb 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 kkb0lim kkj0lim kik (i = 1, 2, r)1| i (i = 1, 2, r)1|max1 i

5、ri 譜半徑譜半徑 (b) 17/15迭代矩陣譜半徑ans= 1.2604e-0051)( jb 例例 線性方程組線性方程組 a x = b, 分別取系數(shù)矩陣為分別取系數(shù)矩陣為 1221112211a 2111111122a試分析試分析jacobi 迭代法和迭代法和 seidel 迭代法的斂散性迭代法的斂散性d=diag(diag(a1);b1=d(d-a1);max(abs(eig(b1) 022101220jb(1)a1=1,2,-2;1,1,1;2,2,18/15迭代矩陣譜半徑 200320220sbdl=tril(a1)b1=dl(dl-a1)max(abs(eig(b1)ans= 2

6、2)( sb (2) a2=2, -1, 1; 1, 1, 1; 1, 1, -2 02/12/11012/12/10jbd=diag(diag(a2)b2=d(d-a2)max(abs(eig(bj)1180. 1)( jb ans= 1.11809/15迭代矩陣譜半徑 2/1002/12/102/12/10sbdl=tril(a2)b2=dl(dl-a2)max(abs(eig(b2)ans= 1/22/1)( sb 兩種迭代法之間沒有直接聯(lián)系兩種迭代法之間沒有直接聯(lián)系對矩陣對矩陣a1,求求a1 x = b 的的jacobi迭代法收斂迭代法收斂,而而gauss-seidel迭代法發(fā)散迭代法

7、發(fā)散;對矩陣對矩陣a2,求求a2 x = b 的的jacobi迭代法發(fā)散迭代法發(fā)散,而而gauss-seidel迭代法收斂迭代法收斂.10/15迭代矩陣譜半徑定理定理4.2 :設(shè)設(shè)x*為方程組為方程組 ax=b 的解的解若若|b|1,則對迭代格式則對迭代格式 x(k+1) = b x(k) + f 有有|1|*|)0()1()(xxbbxxkk |1|*|)1()()( kkkxxbbxx(1)(2)誤差估計定理誤差估計定理11/15迭代矩陣譜半徑證證 由由|b| |-1| + |-1|10 |-1| + |-1|15 |-1| + |-1|a11| |a12| + |a13|a22| |a2

8、1| + |a23|a33| |a31| + |a32|14/15迭代矩陣譜半徑定理定理4.3 若若ax=b的系數(shù)矩陣的系數(shù)矩陣a是嚴格對角占優(yōu)是嚴格對角占優(yōu)矩陣矩陣,則則jacobi迭代和迭代和seidel迭代均收斂迭代均收斂證證: 由于矩陣由于矩陣a嚴格對角占優(yōu)嚴格對角占優(yōu)由由a矩陣構(gòu)造矩陣構(gòu)造jacobi迭代矩陣迭代矩陣bj = d-1(d a) 第第i行絕對值求和行絕對值求和 nijjijiiaa1|1所以所以1 |1max|11 nijjijiinijaab1|11 nijjijiiaa nijjijiiaa1|15/15迭代矩陣譜半徑矩陣的矩陣的條件數(shù)條件數(shù)概念概念 方程組方程組

9、ax = b, 右端項右端項 b 有一擾動有一擾動引起方程組解引起方程組解 x 的擾動的擾動bx設(shè)設(shè) x 是方程組是方程組 ax = b 的解的解,則有則有bbxxa )(化簡化簡,得得bxa bax 1 |1bax 由由 ax = b 得得 |xab |1bax 所以所以|)|(|1bbaaxx 12/16迭代矩陣譜半徑定義條件數(shù)定義條件數(shù): cond(a) = |a1 | |a| 或或 c(a) = |a1 | |a|當條件數(shù)很大時當條件數(shù)很大時,方程組方程組 ax = b是病態(tài)問題是病態(tài)問題;當條件數(shù)較小時當條件數(shù)較小時,方程組方程組 ax = b是良態(tài)問題是良態(tài)問題|)(|1|)(|1

10、1111 aaiaaaai iaaiaai 111)( 注注:11111)()( aaiaaiaai |11|)(|111aaaai 13/16迭代矩陣譜半徑類似類似,設(shè)方程組設(shè)方程組 ax = b,矩陣矩陣a 有一擾動有一擾動 時時,將引起方程組解將引起方程組解x的擾動的擾動ax設(shè)設(shè) x 是方程組是方程組 ax = b 的解的解,則有則有bxxaa )( 化簡化簡,得得axxaa )(axaaaix 111)( 取范數(shù)取范數(shù)|)(|111xaaaaix |1|11aaaaaaxx 14/16迭代矩陣譜半徑 7/16/15/14/16/15/14/13/15/14/13/12/14/13/12/11a階數(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.8108a famous example of a badly conditioned matrix15/16迭代矩陣譜半徑 ans= -2.4000 27.0000 -64.8000 42.0000 ans = 524.0568 1.5514e+004 4.7661e+005 1.4951e