数值分析 第3章 解线性方程组的迭代方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,迭代法研究的主要问题,1,）迭代格式的构造；,2,）迭代的收敛性分析；,3,）收敛速度分析；,4,）,复杂性分析；（计算工作量）,5,）初始值选择。,3.5,大型方程组的迭代方法,定义,:,设,x,k,是,R,n,上的向量序列，,又设,x,*,（,x,1,*,，,x,2,*,，,x,n,*,),是,R,n,上的向量,.,则称向量,x,*,是向量序列,x,k,的极限,，,若一个向量序列有极限,称这个向量序列是,收敛的,.,向量序列的极限,如果,向量序列,x,k,收敛于向量,x,*,的充分必要,定理,1,（,i,=1,2,n,）,条件是,矩阵序列的极限,定义,:,设,A,k,是,上的矩阵序列,.,若存在矩阵,则称矩阵,A,是矩阵序列,A,k,的极限，记为,若一个矩阵序列有极限,称这个矩阵序列是,收敛的,.,使得,矩阵序列,A,k,收敛于矩阵,A,的充分必要,定理,2,（,i,j,=1,2,n,）,条件是,这里,证：,依次取,x,为 ，其中,则,所以,定理,3,的充要条件是对任何,x,R,n,，有,设矩阵,定理,4,，则 的,充要条件是,(,A,),0,记,x,T,L,T,x,=a,则有,x,T,L,T,x,=,x,T,(,D,L,),x,x,T,Ax,=,x,T,(,D,L L,T,),x=p a a=p,2,a,0,所以,所以,迭代矩阵,B,G-S,的谱,半径,(,B,G-S,)1,从而当方程组,Ax=b,的,系数矩阵,A,是实,对称正定矩阵时,G-S,迭代法收敛,Remark:,G-S,迭代法的计算过程比,Jacobi,迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。,G-S,迭代不一定比,Jacobi,迭代收敛快。,Jacobi,迭代和,G-S,迭代的收敛范围并不一致，即,Jacobi,迭代收敛，,G-S,迭代不一定收敛，反之亦然。,前面的定理,1,、定理,2,对于,Jacobi,迭代和,G-S,迭代都适用。,(,i,=1,2,n,;,k=,1,2,3,),四 超松驰,(SOR),迭代法,G-S,迭代格式,定理,7.,若,A,是对称正定矩阵,则当,0,2,时,SOR,迭代法解方程组,A x=b,是收敛的,定理,8.,若,A,是严格对角占优矩阵,则当,0,0,计算,r,(,k,-1),=,b Ax,(0),若,|,r,0,|,结束,;,否则,p,(1,),r,(,k,-1),k,1,转第二步,;,共轭梯度算法：,第二步,:,计算,t,k,=,(,p,(,k,),r,(,k,-1),),/,(,A p,(,k,),p,(,k,),),x,(,k,),=,x,(,k-,1),+,t,k,p,(,k,),;,第三步,:,如果,k=n,则结束,;,否则,计算,r,(,k,-1),=,b Ax,(,k,),;,转第四步,;,第四步,:,如果,|,r,(,k,-1),|,则,结束,;,否则,计算,:,b,kj,=,(,A,p,(,j,),r,(,k,),)/(,A,p,(,j,),p,(,j,),),(,j=,1,k,),p,(,k+,1,),=,r,(,k,-1),(,b,k,1,p,(1,),+,b,kk,p,(,k,),),k,k+,1,转第二步。,