(精品)解非线性方程组的迭代法.ppt

《(精品)解非线性方程组的迭代法.ppt》由会员分享，可在线阅读，更多相关《(精品)解非线性方程组的迭代法.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 前面介绍的解线性方程组的直接法是解低阶稠密方程组的有效方法。但是，在工程技术中常产生大型稀疏矩阵方程组，例如由某些偏微分方程数值解所产生的线性方程组Ax=b，A的阶数很大 ，但零元素较多，迭代法是能够充分利用系数矩阵稀疏性特点的有效算法。第四章第四章 解线性方程组的迭代法解线性方程组的迭代法 迭代法的构造迭代法的构造 迭代法的基本思想是用逐次逼近的方法求线性方程组的解。设有方程组 ,将其转化为等价的便于迭代的形式（这种转化总能实现，如令 ）并由此构造迭代公式 其中，称为迭代矩阵，称为迭代向量。对任意的初始向量 ，由迭代式可求得向量序列 若 ，则 就是方程组Ax=b的解.4.1 解线性方程组的

2、三种迭代法解线性方程组的三种迭代法4.1.14.1.1雅克比（雅克比（Jacobi）迭代法（以三阶方程组为例）迭代法（以三阶方程组为例）设有方程组设有方程组：假设任选一向量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

3、)=b+(L+U)X(m).若则D可逆,于是得称BJ为雅可比迭代矩阵.这种迭代格式称为雅可比迭代格式。在某种条件下，按雅可比迭代所产生的向量序列的极限会存在，且等于原方程组的解。这种求解方法被称为雅可比迭代法，或简单迭代法。定义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)构造赛德尔迭代公式 在多数情况下用高斯赛德尔迭代法比雅克比迭代法收敛快。但也有相反的情况，即高斯赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯赛德尔迭代法发散的情形。4.1.3 超松弛迭代法超松

5、弛迭代法 弛迭代法是高斯赛德尔迭代法的一种改进,是解大型稀疏矩阵方程组的有效方法之一.现在研究如何求向量 首先，由高斯赛德尔迭代法求出一个值，记首先，由高斯赛德尔迭代法求出一个值，记用此公式求解线性方程组的方法称为带有松弛因子的松弛迭代法.当1时称为超松弛迭代法;(SOR法)当1时称为低松弛迭代法;当=1时就是GS迭代法.当某些方程组用高斯赛德尔迭代法不收敛时，可以用低松弛方法获得收敛，将上式写成矩阵的形式，得：于是得SOR迭代的矩阵表示 4.2 迭代法的收敛条件 前面介绍了三种迭代法.从例子看到这三种迭代法都有成功的时候.但我们也可以预计,某种迭代法可能会失效.下面我们试图从理论上来探讨这一

6、问题.三种迭代法的统一写法为:定义定义 设给定设给定Rn中的向量序列中的向量序列 ，即，即其中其中若对任何若对任何i(i=1,2,n)都有都有或者说向量序列或者说向量序列 依坐标收敛于向量，记为依坐标收敛于向量，记为则向量则向量 称为向量序列称为向量序列 的极限的极限，4.2.1 迭代法收迭代法收敛敛的概念的概念证证:再由范数的等价性有再由范数的等价性有引理引理 向量序列向量序列x(m)依坐标收敛于依坐标收敛于x*的充要条件是的充要条件是向量序列依范数收敛与依坐标收敛是等价的。向量序列依范数收敛与依坐标收敛是等价的。如果满足此式，称如果满足此式，称x(m)依范数收敛于依范数收敛于x*定义定义4

7、.2 设设x*是方程组是方程组Ax=b的解的解,对于给定的初始向对于给定的初始向量量x(0),若由某种迭代法产生的向量序列若由某种迭代法产生的向量序列x(m)有有则称该方法收敛则称该方法收敛,否则称该方法发散否则称该方法发散.4.2.2 迭代法收敛的判定定理迭代法收敛的判定定理定理定理4.1 设设若若则对任意的初始向量则对任意的初始向量,该迭代过程收敛于该迭代过程收敛于的唯一解的唯一解,且有估计式且有估计式证证:先证先证 若若则则E-B非奇异非奇异.用反证法用反证法:设设E-B是奇异的是奇异的,则存在非零向量则存在非零向量x,使使(E-B)x=0.即有即有x=Bx.两边取范数两边取范数,再由范

8、数的性质得再由范数的性质得由于由于得得与与矛盾矛盾由于由于E-B是非奇异的，所以方程组是非奇异的，所以方程组(E-B)x=f 的解存在且唯一的解存在且唯一.设为设为x*,即即x*=Bx*+f,进而有进而有取范数得取范数得:由于由于0q1由此例可以看到由此例可以看到:对原方程组直接写出雅可比迭代公式是对原方程组直接写出雅可比迭代公式是不收敛的不收敛的.其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛.其迭代格式为其迭代格式为:如果写出与原方程组等价的方程组如果写出与原方程组等价的方程组定理定理4.4 设方程组设方程组Ax=b的系数矩阵的系数

9、矩阵A为实对称正定矩阵为实对称正定矩阵,且且0 2,则松驰迭代法则松驰迭代法 收敛收敛.说明：定理给出当说明：定理给出当0 2时，松弛迭代法收敛。但是常用的是时，松弛迭代法收敛。但是常用的是1 2的情形，所以本定理发条件称为的情形，所以本定理发条件称为SOR方法的收敛条方法的收敛条件，仅为充分条件。件，仅为充分条件。例例5:讨论例讨论例2中的方程组用中的方程组用SOR方法求解的收敛性方法求解的收敛性.解解:例例2中方程组的系数矩阵为中方程组的系数矩阵为:方程组方程组首先首先A是对称矩阵是对称矩阵,再由再由知知A是对称正定矩阵是对称正定矩阵.由定理由定理4.4知知,当当0 2时时,用用SOR法求解收法求解收敛敛.目前，只有少数特殊类型的矩阵，才有确定的最佳松弛目前，只有少数特殊类型的矩阵，才有确定的最佳松弛因子的理论公式。例如，当因子的理论公式。例如，当A为对称正定的三对角矩阵为对称正定的三对角矩阵时，时，则，则SOR法的最佳松弛因子为法的最佳松弛因子为 但这在实际应用时也有一定困难但这在实际应用时也有一定困难常用的方法是，选不同的常用的方法是，选不同的 进行计算，以确定最佳进行计算，以确定最佳 的近似值，的近似值，或者，先选取一个或者，先选取一个 然后根据迭代过程收敛的快慢不然后根据迭代过程收敛的快慢不断修改断修改 ，以此逐步寻找最佳松弛因子，以此逐步寻找最佳松弛因子 。