迭代矩阵谱半径PPT课件

1、2021/3/91数值分析数值分析1010迭代法的收敛性迭代法的收敛性Convergence of iterative method迭代矩阵谱半径迭代矩阵谱半径Spectral radius对角占优矩阵对角占优矩阵diagonally dominant matrix 2021/3/92原始方程原始方程: 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/152021/3/930lim0lim)( 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/152021/3/94证证: 由由 (k) = B (k-1),得得 | (k)| | B| | (k-1)| ( k = 1, 2, 3, )0lim)( kk 所以所以命题命题 若若|B|1,则迭代法则迭代法 x(k+1) =B x(k) +f

3、收敛收敛| (k)| | B|k | (0)| 0|lim|lim)0()( kkkkB| B| 14/152021/3/95矩阵矩阵A的谱的谱设设n阶方阵阶方阵A的的n个特征值为个特征值为: n ,21则称集合则称集合,21n 为为A的谱的谱. 记为记为 ch A矩阵矩阵A的谱半径的谱半径|max)(1knkA 注注1: 当当A是对称矩阵时是对称矩阵时, |A|2 = (A) 注注2: 对对 Rnn 中的范数中的范数| |,有有 (A) | A |特征值取模最大特征值取模最大5/152021/3/96定理定理4.1 迭代法迭代法 x(k+1) = B x(k) + f 收敛收敛 谱半径谱半径

4、(B) 1证证: 对任何对任何 n 阶矩阵阶矩阵B都存在非奇矩阵都存在非奇矩阵P使使 B = P 1 J P其中其中, J 为为B的的 Jordan 标准型标准型nnrJJJJ 21iinniiiJ 11其中其中, Ji 为为Jordan块块6/152021/3/97其中其中,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,

5、 2, r)1|max1 iri 谱半径谱半径 (B) 17/152021/3/98Ans= 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/152021/3/99 200320220SBDL=tril(A1)B1=DL(DL-A1)max

6、(abs(eig(B1)Ans= 22)( 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/152021/3/910 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迭代法收敛迭代法收敛,而

7、而Gauss-Seidel迭代法发散迭代法发散;对矩阵对矩阵A2,求求A2 x = b 的的Jacobi迭代法发散迭代法发散,而而Gauss-Seidel迭代法收敛迭代法收敛.10/152021/3/911定理定理4.2 :设设x*为方程组为方程组 Ax=b 的解的解若若|B|1,则对迭代格式则对迭代格式 x(k+1) = B x(k) + f 有有|1|*|)0()1()(xxBBxxkk |1|*|)1()()( kkkxxBBxx(1)(2)误差估计定理误差估计定理11/152021/3/912证证 由由|B| |-1| + |-1|10 |-1| + |-1|15 |-1| + |-1

8、|a11| |a12| + |a13|a22| |a21| + |a23|a33| |a31| + |a32|14/152021/3/915定理定理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/152

9、021/3/916矩阵的矩阵的条件数条件数概念概念 方程组方程组 Ax = b, 右端项右端项 b 有一扰动有一扰动引起方程组解引起方程组解 x 的扰动的扰动bx设设 x 是方程组是方程组 Ax = b 的解的解,则有则有bbxxA )(化简化简,得得bxA bAx 1 |1bAx 由由 Ax = b 得得 |xAb |1bAx 所以所以|)|(|1bbAAxx 12/162021/3/917定义条件数定义条件数: Cond(A) = |A1 | |A| 或或 C(A) = |A1 | |A|当条件数很大时当条件数很大时,方程组方程组 Ax = b是病态问题是病态问题;当条件数较小时当条件数较

10、小时,方程组方程组 Ax = b是良态问题是良态问题|)(|1|)(|11111 AAIAAAAI IAAIAAI 111)( 注注:11111)()( AAIAAIAAI |11|)(|111AAAAI 13/162021/3/918类似类似,设方程组设方程组 Ax = b,矩阵矩阵A 有一扰动有一扰动 时时,将引起方程组解将引起方程组解x的扰动的扰动Ax设设 x 是方程组是方程组 Ax = b 的解的解,则有则有bxxAA )( 化简化简,得得AxxAA )(AxAAAIx 111)( 取范数取范数|)(|111xAAAAIx |1|11AAAAAAxx 14/162021/3/919 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/162021/3/920 ans= -2.4000 27.0000 -64.8000 42.0000 ans = 524.0568 1.