方程组迭代法省公共课一等奖全国赛课获奖课件.pptx

三种基本迭代法三种基本迭代法2.4.2 雅克比（雅克比（Jacobi）迭代法）迭代法 （以三阶方程（以三阶方程 组为例）组为例）第1页假设则方程组可写为：第2页任选一初值向量：称为雅可比称为雅可比(Jacobi)迭代迭代第3页对于n阶方程组则雅可比雅可比迭代公式为:第4页n n阶方程阶方程 Jacobi 迭代格式迭代格式:第5页若用矩阵来表示雅可比迭代,则以下:令A=D-L-U,其中第6页A x=b,(D L U)x=bDx=(L+U)x+b迭代 Dx(m+1)=(L+U)x(m)+b,若则D可逆,于是得称 为雅可比迭代矩阵为雅可比迭代矩阵.则有：则有：第7页对雅可比迭代法作以下改进:将初值代入4.1第一个方程可得 ,用 代入第二个方程得 ,用 代入第三个方程得 ,这么一直做下去,直到得到满意解为止.第8页这种迭代称为 高斯高斯赛德尔赛德尔(Gauss-Seidel)迭代法（G-S）第9页n n阶方程阶方程G-SG-S迭代格式迭代格式:第10页用矩阵表示：即：称 为高斯高斯-赛德尔迭代矩阵赛德尔迭代矩阵n阶方程G-S迭代格式:第11页例1（p75）：分别用Jacob及G-S迭代法解以下线性方程组。初值均取(0，0，0)T解解:用matlab解,程序以下第12页%用雅可比法解P91例1a=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;endk,x%用G-S法解P91例1a=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;endk,x第13页从计算结果能够看到:假如两种迭代法都收敛,那么Jacob迭代法慢于G-S迭代法.这个结论含有普通意义.第14页4.1.3 超松弛迭代法超松弛迭代法假设 是第m次迭代,是用G-S法得到第m+1次迭代,那么第m+1次迭代取为:第15页用D左乘之,得:所以称称SOR迭代阵迭代阵第16页写成份量式计算公式为写成份量式计算公式为:此方法称为带有松弛因子松弛迭代法松弛迭代法.当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;endk,x第19页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;end1.雅可比迭代法通用程序雅可比迭代法通用程序第20页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第21页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第22页前面介绍了三种惯用迭代法.它们可能收敛，也可能发散。普通迭代格式：普通迭代格式：下面从理论上探讨普通迭代收敛性.B称为迭代阵称为迭代阵第23页2.4.2 迭代法收敛概念定义4.2 设x*是方程组Ax=b解,对于给定初始向量x(0),若由某种迭代法产生向量序列x(n)有则称该方法收敛,不然称该方法发散.第24页引理1证:再由范数等价性有第25页 迭代法收敛判定定理迭代法收敛判定定理 定理1 设若则对任意初始向量，该迭代过程收敛于唯一解且有预计式：第26页先证 若则E-B非奇异.用反证法:设E-B是奇异,则存在非零向量X,使(E-B)X=0.即有X=BX.两边取范数,再由范数性质得因为得与矛盾第27页因为E-B是非奇异，所以方程组(E-B)X=f 解存在且唯一.设为X*,即X*=BX*+f,进而有取范数得:第28页因为0q1,所以所以迭代过程收敛.又：第29页于是有即(1)式成立.再因为所以有第30页写出Jacobi迭代及G-S迭代，并求其解.例例.解：解：1.Jacobi迭代格式为:第31页雅可比迭代矩阵雅可比迭代矩阵:所以雅可比迭代是收敛所以雅可比迭代是收敛.行范数行范数：第32页2.G-S2.G-S迭代格式为迭代格式为:第33页G-S迭代矩阵迭代矩阵行范数行范数：所以所以G-S迭代也是收敛迭代也是收敛.第34页取初始向量用用G-SG-S迭代格式计算结果迭代格式计算结果：此方程准确解为：第35页定义3 假如方阵A满足则称A按行严格对角占优.(类似地可定义按列严格对角占优)例子例子:按行严格对角占优。第36页定理2 若Ax=b系数矩阵A按行(列)严格对角占优,则Jacobi迭代及G-S迭代都收敛.先证雅可比迭代收敛.因为:所以由定理4.1,Ax=b存在唯一解x*.且用雅可比迭代法求解收敛.可证G-S迭代法收敛(略)证实：证实：第37页以上两个定理都只是收敛充分条件.定理定理4.3 对于任意初始向量，由迭代产生向量序列收敛定理定理4.3 对于任意初始向量，由迭代第38页写出一定收敛Jacobi迭代格式。从而例4解解第39页由BJ特征多项式得特征值为：1=2，2=-2可见:对原方程组直接写出Jacobi迭代是发散.所以迭代阵谱半径第40页其系数矩阵是严格对角占优,所以用雅可比迭代法求解收敛.其迭代格式为:假如交换方程次序，得：第41页定理4 设方程组Ax=b系数矩阵A为实对称正定矩阵,且02,则松驰迭代法收敛.第42页例4.7(p90):讨论例2(p95)中方程组用 SOR方法求解收敛性.解解:例2中方程组系数矩阵为:对称正定？对称正定？第43页首先A是对称矩阵,再由A是对称正定矩阵.由定理4.4知,当02时,用SOR法求解收敛.第44页写出Jacobi迭代及G-S迭代，并判断散性.解：解：1.Jacobi迭代格式为:第45页雅可比迭代矩阵雅可比迭代矩阵:所以雅可比迭代是收敛所以雅可比迭代是收敛.求出B三个特征值迭代阵谱半径第46页2.G-S2.G-S迭代格式为迭代格式为:第47页G-S迭代矩阵迭代矩阵所以所以G-S迭代发散迭代发散.求出B三个特征值迭代阵谱半径第48页P88第49页第50页第51页三种详细迭代格式：Jacobi、G-S、SOR它们迭代矩阵四个收敛定理：收敛收敛3、A严格对角占优 Jacobi、G-S收敛4、A对称正定 G-S、SOR收敛1、2、第52页