解非线性方程组的迭代法精选PPT.ppt

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

1、解非线性方程组的迭代法第1页，此课件共49页哦迭代法的构造迭代法的构造 迭代法的基本思想是用逐次逼近的方法求线性方程组的解。设有方程组 ,将其转化为等价的便于迭代的形式（这种转化总能实现，如令 ）并由此构造迭代公式 其中，称为迭代矩阵，称为迭代向量。对任意的初始向量 ，由迭代式可求得向量序列 若 ，则 就是方程组Ax=b的解.第2页，此课件共49页哦4.1 解线性方程组的三种迭代法解线性方程组的三种迭代法4.1.14.1.1雅克比（雅克比（Jacobi）迭代法（以三阶方程组为例）迭代法（以三阶方程组为例）设有方程组设有方程组：第3页，此课件共49页哦假设任选一向量X(0)作为解的初值.则方程组

2、可写为：代入式(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可逆,于是得称BJ为雅可比迭代矩阵.这种迭代格式称为雅可比迭代格式。第8

3、页，此课件共49页哦在某种条件下，按雅可比迭代所产生的向量序列的极限会存在，且等于原方程组的解。这种求解方法被称为雅可比迭代法，或简单迭代法。定义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)的极限,记为:第9页，此课件共49页哦例 用简单迭代法解下列方程组 解将方程组写成等价形式第10页，此课件共49页哦取初始值x(0)=0,按迭代公式 第11页，此课件共49页哦4.1.2 高斯赛德尔迭代法对雅可比迭代法作如下的改进:将初值代入4.1的第一个方程可得 ,用 代入第二

4、个方程得 ,用 代入第三个方程得 ,这样一直做下去,直到得到满意的解为止.之所以作这样的改进是希望更快的得到近似解.第12页，此课件共49页哦这种迭代的方法用公式写出来就是:第13页，此课件共49页哦对给定的初值,用此迭代公式求线性方程组的方法被称为高斯塞德尔迭代法。（GS）一般地,对n阶线性方程组的迭代格式改为:第14页，此课件共49页哦用矩阵表示此方法为：即：称BG为高斯塞德尔迭代矩阵第15页，此课件共49页哦例 用赛德尔迭代法解方程组 解 将原方程组写成等价形式并按(375)构造赛德尔迭代公式第16页，此课件共49页哦第17页，此课件共49页哦 在多数情况下用高斯赛德尔迭代法比雅克比迭代

5、法收敛快。但也有相反的情况，即高斯赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯赛德尔迭代法发散的情形。第20页，此课件共49页哦4.1.3 超松弛迭代法超松弛迭代法 弛迭代法是高斯赛德尔迭代法的一种改进,是解大型稀疏矩阵方程组的有效方法之一.现在研究如何求向量 首先，由高斯赛德尔迭代法求出一个值，记第21页，此课件共49页哦首先，由高斯赛德尔迭代法求出一个值，记第22页，此课件共49页哦用此公式求解线性方程组的方法称为带有松弛因子的松弛迭代法.当1时称为超松弛迭代法;(SOR法)当1时称为低松弛迭代法;当=1时就是GS迭代法.当某些方程组用高斯赛德尔迭代法不收敛时，可以用低

6、松弛方法获得收敛，第23页，此课件共49页哦将上式写成矩阵的形式，得：于是得SOR迭代的矩阵表示 第24页，此课件共49页哦4.2 迭代法的收敛条件 前面介绍了三种迭代法.从例子看到这三种迭代法都有成功的时候.但我们也可以预计,某种迭代法可能会失效.下面我们试图从理论上来探讨这一问题.三种迭代法的统一写法为:第30页，此课件共49页哦定义定义 设给定设给定Rn中的向量序列中的向量序列 ，即，即其中其中若对任何若对任何i(i=1,2,n)都有都有或者说向量序列或者说向量序列 依坐标收敛于向量，记为依坐标收敛于向量，记为则向量则向量 称为向量序列称为向量序列 的极限的极限，4.2.1 迭代法收迭代

7、法收敛敛的概念的概念第31页，此课件共49页哦证证:再由范数的等价性有再由范数的等价性有引理引理 向量序列向量序列x(m)依坐标收敛于依坐标收敛于x*的充要条件是的充要条件是向量序列依范数收敛与依坐标收敛是等价的。向量序列依范数收敛与依坐标收敛是等价的。如果满足此式，称如果满足此式，称x(m)依范依范数收敛于数收敛于x*第32页，此课件共49页哦定义定义4.2 设设x*是方程组是方程组Ax=b的解的解,对于给定的初始向量对于给定的初始向量x(0),若由某种迭代法产生的向量序列若由某种迭代法产生的向量序列x(m)有有则称该方法收敛则称该方法收敛,否则称该方法发散否则称该方法发散.第33页，此课件

8、共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 的解存在且唯一的解存在且唯一.设为设为

9、x*,即即x*=Bx*+f,进而有进而有取范数得取范数得:由于由于0q1由此例可以看到由此例可以看到:对原方程组直接写出雅可比迭代公式是不收敛对原方程组直接写出雅可比迭代公式是不收敛的的.第45页，此课件共49页哦其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛.其迭代格其迭代格式为式为:如果写出与原方程组等价的方程组如果写出与原方程组等价的方程组第46页，此课件共49页哦定理定理4.4 设方程组设方程组Ax=b的系数矩阵的系数矩阵A为实对称正定矩阵为实对称正定矩阵,且且0 2,则松驰迭代法则松驰迭代法 收敛收敛.说明：定理给出当说明：定

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