迭代矩阵谱半径.ppt

数值分析10,迭代法的收敛性Convergenceofiterativemethod迭代矩阵谱半径Spectralradius对角占优矩阵diagonallydominantmatrix,原始方程: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*),2/15,(1),(k)=B(k-1)=B2(k-2)=Bk(0),3/15,证:由(k)=B(k-1),得|(k)|B|(k-1)|(k=1,2,3,),所以,命题若|B|1,则迭代法x(k+1)=Bx(k)+f收敛,|(k)|B|k|(0)|,4/15,矩阵A的谱,设n阶方阵A的n个特征值为:,则称集合,为A的谱.记为chA,矩阵A的谱半径,注1:当A是对称矩阵时,|A|2=(A),注2:对Rnn中的范数|,有(A)|A|,特征值取模最大,5/15,定理4.1迭代法x(k+1)=Bx(k)+f收敛谱半径(B)1,证:对任何n阶矩阵B都存在非奇矩阵P使B=P1JP其中,J为B的Jordan标准型,其中,Ji为Jordan块,6/15,其中,i是矩阵B的特征值,由B=P1JP,Bk=(P1JP)(P1JP)(P1JP)=P1JkP,迭代法x(k+1)=Bx(k)+f收敛,7/15,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,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.1180,9/15,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,定理4.2:设x*为方程组Ax=b的解若|B|1,则对迭代格式x(k+1)=Bx(k)+f有,(1),(2),误差估计定理,11/15,证由|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)|,所以,12/15,所以,误差估计:,13/15,定义4.1A=(aij)nn,如果则称A为严格对角占优阵.,例4.1,14/15,定理4.3若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Seidel迭代均收敛,证:由于矩阵A严格对角占优,由A矩阵构造Jacobi迭代矩阵BJ=D-1(DA)第i行绝对值求和,所以,15/15,矩阵的条件数概念,方程组Ax=b,右端项b有一扰动引起方程组解x的扰动,设x是方程组Ax=b的解,则有,所以,12/16,定义条件数:Cond(A)=|A1|A|或C(A)=|A1|A|,当条件数很大时,方程组Ax=b是病态问题;当条件数较小时,方程组Ax=b是良态问题,13/16,类似,设方程组Ax=b,矩阵A有一扰动时,将引起方程组解x的扰动,设x是方程组Ax=b的解,则有,化简,得,取范数,14/16,Afamousexampleofabadlyconditionedmatrix,15/16,ans=-2.400027.0000-64.800042.0000ans=524.05681.5514e+0044.7661e+0051.4951e+0074