迭代矩阵谱半径经典实用

1、迭代矩阵谱半径数值分析数值分析1010迭代法的收敛性迭代法的收敛性convergence of iterative method迭代矩阵谱半径迭代矩阵谱半径spectral radius对角占优矩阵对角占优矩阵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*) 设方程组的精确

2、解为设方程组的精确解为 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的谱的谱设设n阶方阵阶方阵a的的n个特征值为个特征值为: n ,21则称集合则称集合,21n 为为a的谱的谱. 记为记为 ch a矩阵矩阵a的谱半径的谱半径|max)(1knka 注注1: 当当a是对称矩阵时是对称矩阵时, |a|2 = (a) 注注2: 对对 rnn 中的范数中的范数| |,有有 (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, 分别取系数矩阵为分别取系数矩阵为 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 两种迭代法之间没有直接联系两种迭代法之间没有直接联系对矩阵对矩阵a1,求求a1 x = b 的的jacobi迭代法收敛迭代法收敛,而而gauss-seidel迭代法发散迭代法

7、发散;对矩阵对矩阵a2,求求a2 x = b 的的jacobi迭代法发散迭代法发散,而而gauss-seidel迭代法收敛迭代法收敛.10/15迭代矩阵谱半径定理定理4.2 :设设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的系数矩阵的系数矩阵a是严格对角占优是严格对角占优矩阵矩阵,则则jacobi迭代和迭代和seidel迭代均收敛迭代均收敛证证: 由于矩阵由于矩阵a严格对角占优严格对角占优由由a矩阵构造矩阵构造jacobi迭代矩阵迭代矩阵bj = d-1(d a) 第第i行绝对值求和行绝对值求和 nijjijiiaa1|1所以所以1 |1max|11 nijjijiinijaab1|11 nijjijiiaa nijjijiiaa1|15/15迭代矩阵谱半径矩阵的矩阵的条件数条件数概念概念 方程组方程组

9、ax = b, 右端项右端项 b 有一扰动有一扰动引起方程组解引起方程组解 x 的扰动的扰动bx设设 x 是方程组是方程组 ax = b 的解的解,则有则有bbxxa )(化简化简,得得bxa bax 1 |1bax 由由 ax = b 得得 |xab |1bax 所以所以|)|(|1bbaaxx 12/16迭代矩阵谱半径定义条件数定义条件数: cond(a) = |a1 | |a| 或或 c(a) = |a1 | |a|当条件数很大时当条件数很大时,方程组方程组 ax = b是病态问题是病态问题;当条件数较小时当条件数较小时,方程组方程组 ax = b是良态问题是良态问题|)(|1|)(|1

10、1111 aaiaaaai iaaiaai 111)( 注注:11111)()( aaiaaiaai |11|)(|111aaaai 13/16迭代矩阵谱半径类似类似,设方程组设方程组 ax = b,矩阵矩阵a 有一扰动有一扰动 时时,将引起方程组解将引起方程组解x的扰动的扰动ax设设 x 是方程组是方程组 ax = b 的解的解,则有则有bxxaa )( 化简化简,得得axxaa )(axaaaix 111)( 取范数取范数|)(|111xaaaaix |1|11aaaaaaxx 14/16迭代矩阵谱半径 7/16/15/14/16/15/14/13/15/14/13/12/14/13/12/11a阶数阶数 4 5 6 条件数条件数 19.4105 2.9107 9.8108条件数条件数2 1.5104 4.7105 1.4107条件数条件数 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