数值分析迭代法的收敛性分析幻灯片.ppt
数值分析迭代法的收敛性分析第1页，共18页，编辑于2022年，星期六平面点列平面点列:(x1,y1),(x2,y2),(xk,yk),XkRn:X1,X2,Xk,利用向量范数等价性利用向量范数等价性,对任意范数对任意范数|2/18第2页，共18页，编辑于2022年，星期六原方程原方程: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/18第3页，共18页，编辑于2022年，星期六(1)(k)=B (k-1)=B2 (k-2)=Bk (0)(2)迭代格式迭代格式 X(k+1)=B X(k)+f 收敛收敛 ！4/18第4页，共18页，编辑于2022年，星期六证证:由由(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第5页，共18页，编辑于2022年，星期六矩阵矩阵B 的谱的谱设设n阶方阵阶方阵B 的的n个特征值为个特征值为:则称集合则称集合为为B 的谱的谱.记为记为 ch B矩阵矩阵B的谱半径的谱半径注注1:当当B是对称矩阵时是对称矩阵时,|B|2=(B)注注2:对对 Rnn 中的范数中的范数|,有有 (B)|B|特征值取模最大6/18第6页，共18页，编辑于2022年，星期六定理定理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第7页，共18页，编辑于2022年，星期六其中其中,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)18/18第8页，共18页，编辑于2022年，星期六注注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/18第9页，共18页，编辑于2022年，星期六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,110/18第10页，共18页，编辑于2022年，星期六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.118011/18第11页，共18页，编辑于2022年，星期六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是非负矩阵时是非负矩阵时,两种迭代法有联系两种迭代法有联系。12/18第12页，共18页，编辑于2022年，星期六定理定理4.2:设设X*为方程组为方程组 AX=b 的解的解若若|B|1,则对迭代格式则对迭代格式 X(k+1)=B X(k)+f 有有(1)(2)误差估计定理误差估计定理13/18第13页，共18页，编辑于2022年，星期六证证 由由|B|-1|+|-1|10|-1|+|-1|15|-1|+|-1|a11|a12|+|a13|a22|a21|+|a23|a33|a31|+|a32|16/18第16页，共18页，编辑于2022年，星期六定理定理4.3 若若Ax=b的系数矩阵的系数矩阵A是严格对角占优矩阵是严格对角占优矩阵,则则Jacobi迭代和迭代和Seidel迭代均收敛迭代均收敛证证:由于矩阵由于矩阵A严格对角占优严格对角占优由由A矩阵构造矩阵构造Jacobi迭代矩阵迭代矩阵BJ=D-1(D A)第第 i 行绝对值求和行绝对值求和所以所以17/18第17页，共18页，编辑于2022年，星期六简单迭代法简单迭代法迭代矩阵迭代矩阵:设矩阵设矩阵A对称正定对称正定,则特征值则特征值 ,由于由于B是是A的多项式的多项式,故故 B 的特征值为的特征值为 当不等式当不等式成立时成立时简单迭代法收敛简单迭代法收敛.18/18第18页，共18页，编辑于2022年，星期六
