《迭代矩阵谱半径【基础教育】》由会员分享，可在线阅读，更多相关《迭代矩阵谱半径【基础教育】（20页珍藏版）》请在金锄头文库上搜索。
1、数值分析数值分析1010迭代法的收敛性迭代法的收敛性Convergence of iterative method迭代矩阵谱半径迭代矩阵谱半径Spectral radius对角占优矩阵对角占优矩阵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*) 设方程组的精确解为设方程组的精确解
2、为 x*,则有则有x* = B x* + f2/152一类课(1) (k) = B (k-1)=B2 (k-2)=Bk (0)(2)迭代格式迭代格式 x(k+1) = B x(k) + f 收敛收敛 ！3/153一类课证证: 由由 (k) = B (k-1),得得 | (k)| | B| | (k-1)| ( k = 1, 2, 3, )所以所以命题命题 若若|B|1,则迭代法则迭代法 x(k+1) =B x(k) +f 收敛收敛| (k)| | B|k | (0)| | B| 14/154一类课矩阵矩阵A的谱的谱设设n阶方阵阶方阵A的的n个特征值为个特征值为: 则称集合则称集合为为A的谱的谱
3、. 记为记为 ch A矩阵矩阵A的谱半径的谱半径注注1: 当当A是对称矩阵时是对称矩阵时, |A|2 = (A) 注注2: 对对 Rnn 中的范数中的范数| |,有有 (A) | A |特征值取模最大特征值取模最大5/155一类课定理定理4.1 迭代法迭代法 x(k+1) = B x(k) + f 收敛收敛 谱半径谱半径(B) 1证证: 对任何对任何 n 阶矩阵阶矩阵B都存在非奇矩阵都存在非奇矩阵P使使 B = P 1 J P其中其中, J 为为B的的 Jordan 标准型标准型其中其中, Ji 为为Jordan块块6/156一类课其中其中,i 是矩阵是矩阵B的特征值的特征值, 由由 B =
4、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 收敛收敛 (i = 1, 2, r)(i = 1, 2, r)谱半径谱半径 (B) 17/157一类课Ans= 1.2604e-005例例 线性方程组线性方程组 A x = b, 分别取系数矩阵为分别取系数矩阵为试分析试分析Jacobi 迭代法和迭代法和 Seidel 迭代法的敛散性迭代法的敛散性D=diag(diag(A1);B1=D(D-A1);max(abs(eig(B1)(1)A1=1,2,-2;1,1,1;2,2,18/158
5、一类课DL=tril(A1)B1=DL(DL-A1)max(abs(eig(B1)Ans= 2(2) A2=2, -1, 1; 1, 1, 1; 1, 1, -2D=diag(diag(A2)B2=D(D-A2)max(abs(eig(Bj)Ans= 1.11809/159一类课DL=tril(A2)B2=DL(DL-A2)max(abs(eig(B2)Ans= 1/2两种迭代法之间没有直接联系两种迭代法之间没有直接联系对矩阵对矩阵A1,求求A1 x = b 的的Jacobi迭代法收敛迭代法收敛,而而Gauss-Seidel迭代法发散迭代法发散;对矩阵对矩阵A2,求求A2 x = b 的的Ja
6、cobi迭代法发散迭代法发散,而而Gauss-Seidel迭代法收敛迭代法收敛.10/1510一类课定理定理4.2 :设设x*为方程组为方程组 Ax=b 的解的解若若|B|1,则对迭代格式则对迭代格式 x(k+1) = B x(k) + f 有有(1)(2)误差估计定理误差估计定理11/1511一类课证证 由由|B| |-1| + |-1|10 |-1| + |-1|15 |-1| + |-1|a11| |a12| + |a13|a22| |a21| + |a23|a33| |a31| + |a32|14/1514一类课定理定理4.3 若若Ax=b的系数矩阵的系数矩阵A是严格对角占优是严格对角
7、占优矩阵矩阵,则则Jacobi迭代和迭代和Seidel迭代均收敛迭代均收敛证证: 由于矩阵由于矩阵A严格对角占优严格对角占优由由A矩阵构造矩阵构造Jacobi迭代矩阵迭代矩阵BJ = D-1(D A) 第第i行绝对值求和行绝对值求和所以所以15/1515一类课矩阵的矩阵的条件数条件数概念概念 方程组方程组 Ax = b, 右端项右端项 b 有一扰动有一扰动引起方程组解引起方程组解 x 的扰动的扰动设设 x 是方程组是方程组 Ax = b 的解的解,则有则有化简化简,得得由由 Ax = b 得得 所以所以12/1616一类课定义条件数定义条件数: Cond(A) = |A1 | |A| 或或 C
8、(A) = |A1 | |A|当条件数很大时当条件数很大时,方程组方程组 Ax = b是病态问题是病态问题;当条件数较小时当条件数较小时,方程组方程组 Ax = b是良态问题是良态问题注注:13/1617一类课类似类似,设方程组设方程组 Ax = b,矩阵矩阵A 有一扰动有一扰动 时时,将引起方程组解将引起方程组解x的扰动的扰动设设 x 是方程组是方程组 Ax = b 的解的解,则有则有化简化简,得得取范数取范数14/1618一类课阶数阶数 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/1619一类课 ans= -2.4000 27.0000 -64.8000 42.0000 ans = 524.0568 1.5514e+004 4.7661e+005 1.4951e+007 4.7537e+008 1.5258e+010A=hilb(4);b=1 2 1.41 2;b1=1 2 1.42 2;Ab-Ab1for k=3:8 H=hilb(k); cond(H)end20一类课
