数值计算方法10.ppt

1、迭代法的收敛性分析 迭代矩阵谱半径 误差估计定理 对角占优矩阵,数值分析 10,平面点列: (x1 , y1),(x2 ,y2), , (xk , yk),XkRn : X1, X2, , Xk , ,利用向量范数等价性, 对任意范数 | |,2/18,原方程: 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*),设方程组的精确解为 X*,则有,X* = B X* +

2、f ,3/18,(1),(k) = B (k-1)=B2 (k-2)=Bk (0),(2),迭代格式 X(k+1) = B X(k) + f 收敛 ！,4/18,证: 由(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)|,5/18,矩阵B 的谱,设n阶方阵B 的n个特征值为:,则称集合,为B 的谱. 记为 ch B,矩阵B的谱半径,注1: 当B是对称矩阵时, |B|2 = (B),注2: 对 Rnn 中的范数| |,有 (B

3、) | B |,特征值取模最大,6/18,定理4.1 迭代法 X(k+1) = B X(k) + f 收敛 谱半径(B) 1,证: 对任何 n 阶矩阵B都存在非奇矩阵P使 B = P 1 J P 其中, J 为B的 Jordan 标准型,其中, Ji 为Jordan块,7/18,其中,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 收敛 ,8/18,注1: AX = b X = BX + f ( I B )X = f X = ( I B )-1 f,

4、事实上 ( I - B)( I + B + B2 + + Bk ) =I Bk+1,注3: X(k) =B X(k-1) + f = B(B X(k-2) + f) + f = = Bk X(0) + ( I + B + + Bk-1)f ( I B )-1 f,9/18,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,1,10/18,DL=tril(A1) B

5、1=DL(DL-A1) max(abs(eig(B1),Ans= 2,(2) A2=2, -1, 1; 1, 1, 1; 1, 1, -2,D=diag(diag(A2) B2=D(D-A2) max(abs(eig(Bj),Ans= 1.1180,11/18,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 的Jacobi迭代法发散,而Gauss-Seidel迭代法收敛. 除非BJ是非负矩阵时,两种迭代法有联系。,

6、12/18,定理4.2 :设X*为方程组 AX=b 的解 若|B|1,则对迭代格式 X(k+1) = B X(k) + f 有,(1),(2),误差估计定理,13/18,证 由|B|1,有,|X(k+1) X(k) |= |(X* X(k) (X* X(k+1)| |(X* X(k) | |(X* X(k+1)| |(X* X(k)| |B| |(X* X(k)| = ( 1 - | B |) |(X* X(k)|,| X(k+1) X* | |B| | X(k) X* |,14/18,所以,|X(k+1)X(k)| |B | | X(k) X(k-1) |,误差估计:,15/18,定义4.1 A=(aij)nn, 如果 则称A为严格对角占优阵.,例4.1,16/18,定理4.3 若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Seidel迭代均收敛,证: 由于矩阵A严格对角占优,由A矩阵构造Jacobi