《解非线性方程组的迭代法.ppt》由会员分享，可在线阅读，更多相关《解非线性方程组的迭代法.ppt（49页珍藏版）》请在三一办公上搜索。
1、前面介绍的解线性方程组的直接法是解低阶稠密方程组的有效方法。但是，在工程技术中常产生大型稀疏矩阵方程组，例如由某些偏微分方程数值解所产生的线性方程组Ax=b，A的阶数很大，但零元素较多，迭代法是能够充分利用系数矩阵稀疏性特点的有效算法。,第四章 解线性方程组的迭代法,迭代法的构造,迭代法的基本思想是用逐次逼近的方法求线性方程组的解。设有方程组,将其转化为等价的便于迭代的形式（这种转化总能实现，如令）并由此构造迭代公式,其中，称为迭代矩阵，称为迭代向量。对任意的初始向量，由迭代式可求得向量序列 若，则 就是方程组Ax=b的解.,4.1 解线性方程组的三种迭代法4.1.1雅克比（Jacobi）迭代
2、法（以三阶方程组为例）设有方程组：,假设,任选一向量X(0)作为解的初值.,则方程组可写为：,代入式(4.1)中得方程组的一次近似.,把X(1)再代入到(4.1)中得方程组的二次近似.,重复这一过程,假设得到了m次近似X(m)。代入到(4.1)中可得m+1次近似X(m+1)。,称此迭代公式为原方程组的雅可比迭代公式.,对于n阶方程组,则雅可比迭代公式为:,若用矩阵来记录雅可比矩阵,可作如下的推导:,令A=D-L-U,其中,则有AX=DX-LX-UX=b.即DX=b+(L+U)X,从而有DX(m+1)=b+(L+U)X(m).若则D可逆,于是得,称BJ为雅可比迭代矩阵.这种迭代格式称为雅可比迭代
3、格式。,在某种条件下，按雅可比迭代所产生的向量序列的极限会存在，且等于原方程组的解。这种求解方法被称为雅可比迭代法，或简单迭代法。,定义4.1 如果向量序列X(m)=(x1(m),x2(m),xn(m)有 xi(m)xi*（i=1,2,3,n）(m)则称向量X*=(x1*,x2*,xn*)为向量序列X(m)的极限,记为:,例 用简单迭代法解下列方程组,解将方程组写成等价形式,取初始值x(0)=0,按迭代公式,4.1.2 高斯赛德尔迭代法,对雅可比迭代法作如下的改进:将初值代入4.1的第一个方程可得,用 代入第二个方程得,用 代入第三个方程得,这样一直做下去,直到得到满意的解为止.之所以作这样的
4、改进是希望更快的得到近似解.,这种迭代的方法用公式写出来就是:,对给定的初值,用此迭代公式求线性方程组的方法被称为高斯塞德尔迭代法。（GS）,一般地,对n阶线性方程组的迭代格式改为:,用矩阵表示此方法为：,即：,称BG为高斯塞德尔迭代矩阵,例 用赛德尔迭代法解方程组,解 将原方程组写成等价形式并按(375)构造赛德尔迭代公式,例1：分别用两种迭代法求下列线性方程组。初值均取(0，0，0)T,解:用matlab解,程序如下,%用雅可比法解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)
5、;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;en
6、dk,x,在多数情况下用高斯赛德尔迭代法比雅克比迭代法收敛快。但也有相反的情况，即高斯赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯赛德尔迭代法发散的情形。,4.1.3 超松弛迭代法,弛迭代法是高斯赛德尔迭代法的一种改进,是解大型稀疏矩阵方程组的有效方法之一.现在研究如何求向量 首先，由高斯赛德尔迭代法求出一个值，记,首先，由高斯赛德尔迭代法求出一个值，记,用此公式求解线性方程组的方法称为带有松弛因子的松弛迭代法.当1时称为超松弛迭代法;(SOR法)当1时称为低松弛迭代法;当=1时就是GS迭代法.当某些方程组用高斯赛德尔迭代法不收敛时，可以用低松弛方法获得收敛，,将上式写成矩
7、阵的形式，得：于是得SOR迭代的矩阵表示,例 用SOR法求解方程,%用SOR法解P96例2a=4,-2,-4;-2,17,10;-4,10,9;D=-(a-triu(a)-tril(a);L=-(tril(a)-D);U=-(triu(a)-D);xo=0;0;0;bo=10;3;-7;omiga=1.46;ep=0.000001;dx=1;k=0;,while dxep 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,Matlab的关于三种迭
8、代法的通用程序,%雅可比法解方程的通用程序%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)N(2)xo=X;else xo=Xend,D=-(a-triu(a)-tril(a);L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;while dxep k=k+1;x=D(L+U)*xo+Dbo;dx=norm(x-xo);xo=x;end,1.雅可比迭代法的通用程序,2.高斯_塞德尔迭代法的通用程序,%G_S法解方程组的通用程
9、序%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)N(2)xo=X;else xo=Xend,D=-(a-triu(a)-tril(a);L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;while dxep k=k+1;x=(D-L)U*xo+(D-L)bo;dx=norm(x-xo);xo=x;end,3.SOR法解线性方程组的通用程序,%SOR法解方程组的通用程序%A为线性方程组,X为初值%omiga为松弛因子func
10、tion x,k=ya3(A,X,omiga)n=length(A);a=A(:,1:n-1);bo=A(:,n);N=size(X);if N(1)N(2)xo=X;else xo=Xend,D=-(a-triu(a)-tril(a);L=-(tril(a)-D);U=-(triu(a)-D);ep=0.0001;dx=1;k=0;while dxep 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,4.2 迭代法的收敛条件,前面介绍了三种迭代法.从例子看到这三种迭代
11、法都有成功的时候.但我们也可以预计,某种迭代法可能会失效.下面我们试图从理论上来探讨这一问题.三种迭代法的统一写法为:,定义 设给定Rn中的向量序列，即,其中,若对任何i(i=1,2,n)都有,或者说向量序列 依坐标收敛于向量，记为,4.2.1 迭代法收敛的概念,证:,再由范数的等价性有,引理 向量序列x(m)依坐标收敛于x*的充要条件是,向量序列依范数收敛与依坐标收敛是等价的。,如果满足此式，称x(m)依范数收敛于x*,定义4.2 设x*是方程组Ax=b的解,对于给定的初始向量x(0),若由某种迭代法产生的向量序列x(m)有,则称该方法收敛,否则称该方法发散.,4.2.2 迭代法收敛的判定定
12、理,定理4.1 设,若,则对任意的初始向量,该迭代过程收敛于,的唯一解,且有估计式,证:先证 若,则E-B非奇异.,用反证法:设E-B是奇异的,则存在非零向量x,使(E-B)x=0.即有x=Bx.两边取范数,再由范数的性质得,由于,得,由于E-B是非奇异的，所以方程组(E-B)x=f 的解存在且唯一.设为x*,即x*=Bx*+f,进而有,取范数得:,由于0q1,所以,所以迭代过程收敛.又,于是有,即(1)式成立.,再由于,所以有,即(2)式成立.(2)式提示我们可以利用,来控制误差,例 写出用雅可比迭代法和G-S迭代法解线性方程组收敛的迭代格式。,解：对A分解,于是,由此得,所以用雅可比迭代法
13、和G-S迭代法求解方程组都收敛。分别为：,定义4.3 如果方阵A满足,则称A按行严格对角占优.(类似地可定义按列严格对角占优),注意:,是对角占优,不是严格对角占优.,定理4.2 若方程组Ax=b的系数矩阵按行(列)严格对角占优,则雅可比迭代法收敛,G-S迭代法也收敛.,证:先证雅可比迭代法收敛.因为:,所以由定理4.1,Ax=b存在唯一解x*.且用雅可比迭代法求解收敛.,可证G-S迭代法收敛(略),以上两个定理都是收敛的充分条件.下面给出一个充分必要条件：,定理4.3 对于任意的初始向量,由,产生的向量序列,收敛的充分必要条件是,例：写出用雅可比迭代法求解方程组一定收敛的迭代格式。,解：对A
14、进行分解,从而,由BJ的特征多项式,得特征值为：1=2，2=-2。所以(BJ)=21由此例可以看到:对原方程组直接写出雅可比迭代公式是不收敛的.,其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛.其迭代格式为:,如果写出与原方程组等价的方程组,定理4.4 设方程组Ax=b的系数矩阵A为实对称正定矩阵,且02,则松驰迭代法 收敛.,说明：定理给出当02时，松弛迭代法收敛。但是常用的是12的情形，所以本定理发条件称为SOR方法的收敛条件，仅为充分条件。,例5:讨论例2中的方程组用SOR方法求解的收敛性.解:例2中方程组的系数矩阵为:方程组,首先A是对称矩阵,再由,知A是对称正定矩阵.由定理4.4知,当02时,用SOR法求解收敛.,目前，只有少数特殊类型的矩阵，才有确定的最佳松弛因子的理论公式。例如，当A为对称正定的三对角矩阵时，则SOR法的最佳松弛因子为 但这在实际应用时也有一定困难,常用的方法是，选不同的 进行计算，以确定最佳 的近似值，或者，先选取一个 然后根据迭代过程收敛的快慢不断修改，以此逐步寻找最佳松弛因子。,
