迭代矩阵谱半径

迭代矩阵谱半径.第一页，共19页。原始方程:Ax=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)=Bx(k)+f

x(k+1)–x*=B(x(k)–x*)设方程组的精确解为x*,则有x*=Bx*+f2/15第二页，共19页。(1)

(k)=B

(k-1)=B2

(k-2)=···=Bk

(0)(2)迭代格式x(k+1)=Bx(k)+f收敛！！3/15第三页，共19页。证:由

(k)=B

(k-1),得||

(k)||≤||B||||

(k-1)||

(k=1,2,3,······)所以命题若||B||<1,则迭代法x(k+1)=Bx(k)+f收敛||

(k)||≤||B||k||

(0)||

||B||<14/15第四页，共19页。矩阵A的谱设n阶方阵A的n个特征值为:则称集合为A的谱.记为chA矩阵A的谱半径注1:当A是对称矩阵时,||A||2=(A)

注2:对Rn×n

中的范数||·||,有(A)≤||A||特征值取模最大5/15第五页，共19页。定理4.1迭代法x(k+1)=Bx(k)+f收敛<=>谱半径ρ(B)<1证:对任何n阶矩阵B都存在非奇矩阵P使

B=P–1JP其中,J为B的Jordan标准型其中,Ji为Jordan块6/15第六页，共19页。其中,λi是矩阵B的特征值,由B=P–1JPBk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f收敛<=>(i=1,2,···,r)(i=1,2,···,r)谱半径

(B)<17/15第七页，共19页。Ans=1.2604e-005例线性方程组Ax=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]8/15第八页，共19页。DL=tril(A1)B1=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.11809/15第九页，共19页。DL=tril(A2)B2=DL\(DL-A2)max(abs(eig(B2)))Ans=1/2两种迭代法之间没有直接联系对矩阵A1,求A1x=b的Jacobi迭代法收敛,而Gauss-Seidel迭代法发散;对矩阵A2,求A2x=b的Jacobi迭代法发散,而Gauss-Seidel迭代法收敛.10/15第十页，共19页。定理4.2:设x*为方程组Ax=b的解若||B||<1,则对迭代格式x(k+1)=Bx(k)+f有(1)(2)误差估计定理11/15第十一页，共19页。证由||B||<1,有所以||x(k+1)–x*||≤||B||||x(k)–x*||x(k+1)–x*=(Bx(k)+f)–(Bx*+f)=B(x(k)–x*

)12/15第十二页，共19页。所以x(k+1)–x(k)=(Bx(k)–f)–(Bx(k-1)–f)=B(x(k)–x(k-1)

)||x(k+1)–x(k)||≤||B||||x(k)–x(k-1)||误差估计:13/15第十三页，共19页。定义4.1A=(aij)n×n,如果则称A为严格对角占优阵.例4.19>|-1|+|-1|10>|-1|+|-1|15>|-1|+|-1||a11|>|a12|+|a13||a22|>|a21|+|a23||a33|>|a31|+|a32|14/15第十四页，共19页。定理4.3若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Seidel迭代均收敛证:由于矩阵A严格对角占优由A矩阵构造Jacobi迭代矩阵BJ=D-1(D–A)第i行绝对值求和所以15/15第十五页，共19页。矩阵的条件数概念方程组Ax=b,右端项b有一扰动引起方程组解x的扰动设x是方程组Ax=b的解,则有化简,得由Ax=b得所以12/16第十六页，共19页。定义条件数:Cond(A)=||A–1||||A||或C(A)=||A–1||||A||当条件数很大时,方程组Ax=b是病态问题;当条件数较小时,方程组Ax=b