数值分析10迭代法的收敛性分析.ppt

《数值分析10迭代法的收敛性分析.ppt》由会员分享，可在线阅读，更多相关《数值分析10迭代法的收敛性分析.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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*+f 3/

2、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)|B|15/18矩阵矩阵B 的谱的谱设设n阶方阵阶方阵B 的的n个特征值为个特征值为:则称则称集合集合为为B 的谱的谱.记为记为 ch B矩阵矩阵B的谱半径的谱半径注注1:当当B是对称矩阵时是对称矩阵时,|B|2=(B)注注2:对对 Rnn 中的范数中的范数|,

3、有有 (B)|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 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)1

4、8/18注注1:AX=b X=BX+f (I B)X=f X=(I B)-1 f 注注2:若若 则则(I-B)-1=I+B+B2+Bk+事实上事实上 (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/18Ans=1.2604e-005例例 线性方程组线性方程组 A X=b,分别取系数矩阵为分别取系数矩阵为试试分析分析Jacobi 迭代法迭代法和和 Seidel 迭代法的敛散性迭代法的敛散性D=diag(diag(A1);B1=D(D-A1);max(abs(e

5、ig(B1)(1)A1=1,2,-2;1,1,1;2,2,110/18DL=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.118011/18DL=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迭代法发散迭代法发

6、散,而而Gauss-Seidel迭代法收敛迭代法收敛.除非除非BJ是非负矩阵时是非负矩阵时,两种迭代法有联系两种迭代法有联系。12/18定理定理4.2:设设X*为方程组为方程组 AX=b 的解的解若若|B|1,则对迭代格式则对迭代格式 X(k+1)=B X(k)+f 有有(1)(2)误差估计定理误差估计定理13/18证证 由由|B|-1|+|-1|10|-1|+|-1|15|-1|+|-1|a11|a12|+|a13|a22|a21|+|a23|a33|a31|+|a32|16/18定理定理4.3 若若Ax=b的系数矩阵的系数矩阵A是严格对角占优是严格对角占优矩阵矩阵,则则Jacobi迭代和迭代和Seidel迭代均收敛迭代均收敛证证:由于矩阵由于矩阵A严格对角占优严格对角占优由由A矩阵构造矩阵构造Jacobi迭代矩阵迭代矩阵BJ=D-1(D A)第第 i 行绝对值求和行绝对值求和所以所以17/18简单迭代法简单迭代法迭代迭代矩阵矩阵:设设矩阵矩阵A对称正定对称正定,则特征值则特征值 ,由于由于B是是A的多项式的多项式,故故 B 的特征值为的特征值为 当当不等式不等式成立时成立时简单迭代法收敛简单迭代法收敛.18/18