资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,前面介绍解线性方程组直接法是解低阶稠,密方程组有效方法。不过，在工程技术中常产生,大型稀疏矩阵方程组，比如由一些偏微分方程数值,解所产生线性方程组,Ax,=,b,，,A,阶数很大 ，,但零元素较多，迭代法是能够充分利用系数矩阵稀,疏性特点有效算法。,第四章 解线性方程组迭代法,1/49,迭代法结构,迭代法基本思想是用逐次迫近方法求线性方程组解。,设有方程组,将其转化为等价便于迭代形式,（这种转化总能实现，如令 ）并由此结构迭代公式,其中，称为迭代矩阵，称为迭代向量。对任意初始向量 ，由迭代式可求得向量序列,若 ，则 就是方程组,Ax=b,解,.,2/49,4.1,解线性方程组三种迭代法,4.1.1,雅克比（,Jacobi,）迭代法（以三阶方程组为例）,设有方程组,：,3/49,假设,任选一向量,X,(0),作为解初值,.,则方程组可写为：,代入式,(4.1),中得方程组一次近似,.,4/49,把,X,(1),再代入到,(4.1),中得方程组二次近似,.,重复这一过程,假设得到了,m,次近似,X,(m),。代入到,(4.1),中可得,m+1,次近似,X,(m+1),。,称此迭代公式为原方程组雅可比迭代公式,.,5/49,对于,n,阶方程组,则雅可比迭代公式为,:,6/49,若用矩阵来统计雅可比矩阵,可作以下推导,:,令,A=D-L-U,其中,7/49,则有,AX=DX-LX-UX=b,.,即,DX=b+,(,L+U,),X,从而有,DX,(,m+,1),=b+,(,L+U,),X,(,m,),.,若,则,D,可逆,于是得,称,B,J,为,雅可比迭代矩阵,.,这种迭代格式称为,雅可比迭代格式,。,8/49,在,某种条件下,，按雅可比迭代所产生向量序列极限会存在，且等于原方程组解。这种求解方法被称为雅可比迭代法，或简单迭代法。,定义,4.1,假如向量序列,X,(,m,),=(,x,1,(,m,),x,2,(,m,),x,n,(,m,),有,x,i,(,m,),x,i,*,（,i,=1,2,3,n,）,(,m,),则称向量,X,*,=(,x,1,*,x,2,*,x,n,*,),为向量序列,X,(,m,),极限,记为,:,9/49,例 用简单迭代法解以下方程组,解将方程组写成等价形式,10/49,取初始值,x,(0),=0,按迭代公式,11/49,4.1.2,高斯,赛德尔迭代法,对雅可比迭代法作以下改进,:,将初值,代入,4.1,第一个方程可得,用 代入第二个方程得,用 代入第三个方程得,这么一直做下去,直到得到满意解为止,.,之所以作这么改进是希望更加快得到近似解,.,12/49,这种迭代方法用公式写出来就是,:,13/49,对给定初值,用此迭代公式求线性方程组方法被称为高斯,塞德尔迭代法。（,GS,）,普通地,对,n,阶线性方程组迭代格式改为,:,14/49,用矩阵表示此方法为：,即：,称,B,G,为高斯,塞德尔迭代矩阵,15/49,例 用赛德尔迭代法解方程组,解 将原方程组写成等价形式并按,(375),结构赛德尔迭代公式,16/49,17/49,例,1,：分别用两种迭代法求以下线性方程组。初值均取,(0,，,0,，,0),T,解,:,用,matlab,解,程序以下,18/49,%,用雅可比法解,P91,例,1,a=9,-1,-1;-1,8,0;-1,0,9;,D=-(a-triu(a)-tril(a);,L=-(tril(a)-b);,U=-(triu(a)-b);,xo=0;0;0;bo=7;7;8;,ep=0.0001;dx=1;k=0;,while dxep,k=k+1;,x=D(L+U)*xo+Dbo;,dx=abs(norm(x)-norm(xo);,xo=x;,end,k,x,%,用,G_S,法解,P91,例,1,a=9,-1,-1;-1,8,0;-1,0,9;,D=-(a-triu(a)-tril(a);,L=-(tril(a)-b);,U=-(triu(a)-b);,xo=0;0;0;bo=7;7;8;,ep=0.0001;dx=1;k=0;,while dxep,k=k+1;,x=(D-L)U*xo+(D-L)bo;,dx=abs(norm(x)-norm(xo);,xo=x;,end,k,x,19/49,在多数情况下用高斯,赛德尔迭代法比雅克比迭代法收敛快。但也有相反情况，即高斯,赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯,赛德尔迭代法发散情形。,20/49,4.1.3,超松弛迭代法,弛迭代法是高斯,赛德尔迭代法一个改进,是解大型稀疏矩阵方程组有效方法之一,.,现在研究怎样求向量,首先，由高斯,赛德尔迭代法求出一个值，记,21/49,首先，由高斯,赛德尔迭代法求出一个值，记,22/49,用此公式求解线性方程组方法称为,带有松弛因子,松弛迭代法,.,当,1,时称为,超松弛迭代法,;(SOR,法,),当,ep,k=k+1;,x=(D-omiga*L)(omiga*U+(1-omiga)*D)*xo+(D-omiga*L)bo*omiga;,dx=abs(norm(x)-norm(xo);,xo=x;,end,k,x,26/49,Matlab,关于三种迭代法通用程序,%,雅可比法解方程通用程序,%A,为线性方程组,X,为初值,function x,k=ya2(A,X),n=length(A);,a=A(:,1:n-1);,bo=A(:,n);N=size(X);,if N(1)ep,k=k+1;,x=D(L+U)*xo+Dbo;,dx=norm(x-xo);,xo=x;,end,1.,雅可比迭代法通用程序,27/49,2.,高斯,_,塞德尔迭代法通用程序,%G_S,法解方程组通用程序,%A,为线性方程组,X,为初值,function x,k=ya4(A,X),n=length(A);,a=A(:,1:n-1);,bo=A(:,n);N=size(X);,if N(1)ep,k=k+1;,x=(D-L)U*xo+(D-L)bo;,dx=norm(x-xo);,xo=x;,end,28/49,3.SOR,法解线性方程组通用程序,%SOR,法解方程组通用程序,%A,为线性方程组,X,为初值,%omiga,为松弛因子,function x,k=ya3(A,X,omiga),n=length(A);,a=A(:,1:n-1);bo=A(:,n);N=size(X);,if N(1)ep,k=k+1;,x=(D-omiga*L)(omiga*U+(1-omiga)*D)*xo+(D-omiga*L)bo*omiga;,dx=norm(x-xo);,xo=x;,end,29/49,4.2,迭代法收敛条件,前面介绍了三种迭代法,.,从例子看到这三种迭代法都有成功时候,.,但我们也能够预计,某种迭代法可能会失效,.,下面我们试图从理论上来探讨这一问题,.,三种迭代法统一写法为,:,30/49,定义 设给定,R,n,中向量序列,，即,其中,若对任何,i,(,i,=1,2,n,),都有,或者说向量序列,依坐标收敛于向量，记为,则向量,称为向量序列,极限,，,4.2.1,迭代法收敛概念,31/49,证,:,再由范数等价性有,引理 向量序列,x,(,m,),依坐标收敛于,x,*,充要条件是,向量序列依范数收敛与依坐标收敛是等价。,假如满足此式，称,x,(,m,),依范数收敛于,x,*,32/49,定义,4.2,设,x,*,是方程组,Ax,=,b,解,对于给定初始向量,x,(0),若由某种迭代法产生向量序列,x,(,m,),有,则称该方法收敛,不然称该方法发散,.,33/49,4.2.2,迭代法收敛判定定理,定理,4.1,设,若,则对任意初始向量,该迭代过程收敛于,唯一解,且有预计式,34/49,证,:,先证 若,则,E-B,非奇异,.,用反证法,:,设,E-B,是奇异,则存在非零向量,x,使,(E-B),x,=0.,即有,x=Bx,.,两边取范数,再由范数性质得,因为,得,与,矛盾,35/49,因为,E-B,是非奇异，所以方程组,(,E-B,),x,=,f,解存在且唯一,.,设为,x,*,即,x*=Bx*+f,进而有,取范数得,:,因为,0,q,1,由此例能够看到,:,对原方程组直接写出雅可比迭代公式是不收敛,.,45/49,其系数矩阵是严格对角占优所以用雅可比迭代法求解收敛,.,其迭代格式为,:,假如写出与原方程组等价方程组,46/49,定理,4.4,设方程组,Ax=b,系数矩阵,A,为实对称正定矩阵,且,0,2,则松驰迭代法 收敛,.,说明：定理给出当,0,2,时，松弛迭代法收敛。不过惯用是,1,2,情形，所以本定剪发条件称为,SOR,方法收敛条件，仅为充分条件。,47/49,例,5:,讨论例,2,中方程组用,SOR,方法求解收敛性,.,解,:,例,2,中方程组系数矩阵为,:,方程组,首先,A,是对称矩阵,再由,知,A,是对称正定矩阵,.,由定理,4.4,知,当,0,2,时,用,SOR,法求解收敛,.,48/49,当前，只有少数特殊类型矩阵，才有确定最正确松弛因子理论公式。比如，当,A,为对称正定三对角矩阵时，则,SOR,法最正确松弛因子为,但这在实际应用时也有一定困难,惯用方法是，选不一样 进行计算，以确定最正确 近似值，或者，先选取一个 然后依据迭代过程收敛快慢不停修改 ，以此逐步寻找最正确松弛因子 。,49/49,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
