解非线性方程组的迭代法精选文档.ppt
解非线性方程组的迭代法本讲稿第一页，共四十九页迭代法的构造迭代法的构造 迭代法的基本思想是用逐次逼近的方法求线性方程组的解。设有方程组 ,将其转化为等价的便于迭代的形式（这种转化总能实现，如令 ）并由此构造迭代公式 其中，称为迭代矩阵，称为迭代向量。对任意的初始向量 ，由迭代式可求得向量序列 若 ，则 就是方程组Ax=b的解.本讲稿第二页，共四十九页4.1 解线性方程组的三种迭代法解线性方程组的三种迭代法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)=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的第一个方程可得 ,用 代入第二个方程得 ,用 代入第三个方程得 ,这样一直做下去,直到得到满意的解为止.之所以作这样的改进是希望更快的得到近似解.本讲稿第十二页，共四十九页这种迭代的方法用公式写出来就是:本讲稿第十三页，共四十九页对给定的初值,用此迭代公式求线性方程组的方法被称为高斯塞德尔迭代法。（GS）一般地,对n阶线性方程组的迭代格式改为:本讲稿第十四页，共四十九页用矩阵表示此方法为：即：称BG为高斯塞德尔迭代矩阵本讲稿第十五页，共四十九页例 用赛德尔迭代法解方程组 解 将原方程组写成等价形式并按(375)构造赛德尔迭代公式本讲稿第十六页，共四十九页本讲稿第十七页，共四十九页 在多数情况下用高斯赛德尔迭代法比雅克比迭代法收敛快。但也有相反的情况，即高斯赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯赛德尔迭代法发散的情形。本讲稿第二十页，共四十九页4.1.3 超松弛迭代法超松弛迭代法 弛迭代法是高斯赛德尔迭代法的一种改进,是解大型稀疏矩阵方程组的有效方法之一.现在研究如何求向量 首先，由高斯赛德尔迭代法求出一个值，记本讲稿第二十一页，共四十九页首先，由高斯赛德尔迭代法求出一个值，记本讲稿第二十二页，共四十九页用此公式求解线性方程组的方法称为带有松弛因子的松弛迭代法.当1时称为超松弛迭代法;(SOR法)当1时称为低松弛迭代法;当=1时就是GS迭代法.当某些方程组用高斯赛德尔迭代法不收敛时，可以用低松弛方法获得收敛，本讲稿第二十三页，共四十九页将上式写成矩阵的形式，得：于是得SOR迭代的矩阵表示 本讲稿第二十四页，共四十九页4.2 迭代法的收敛条件 前面介绍了三种迭代法.从例子看到这三种迭代法都有成功的时候.但我们也可以预计,某种迭代法可能会失效.下面我们试图从理论上来探讨这一问题.三种迭代法的统一写法为:本讲稿第三十页，共四十九页定义定义 设给定设给定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 迭代法收敛的判定定理迭代法收敛的判定定理定理定理4.1 设设若若则对任意的初始向量则对任意的初始向量,该迭代过程收敛于该迭代过程收敛于的唯一解的唯一解,且有估计式且有估计式本讲稿第三十四页，共四十九页证证:先证先证 若若则则E-B非奇异非奇异.用反证法用反证法:设设E-B是奇异的是奇异的,则存在非零向量则存在非零向量x,使使(E-B)x=0.即有即有x=Bx.两边取两边取范数范数,再由范数的性质得再由范数的性质得由于由于得得与与矛盾矛盾本讲稿第三十五页，共四十九页由于由于E-B是非奇异的，所以方程组是非奇异的，所以方程组(E-B)x=f 的解存在且唯一的解存在且唯一.设为设为x*,即即x*=Bx*+f,进而有进而有取范数得取范数得:由于由于0q1由此例可以看到由此例可以看到:对原方程组直接写出雅可比迭代公式是不收敛的对原方程组直接写出雅可比迭代公式是不收敛的.本讲稿第四十五页，共四十九页其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛.其迭代格其迭代格式为式为:如果写出与原方程组等价的方程组如果写出与原方程组等价的方程组本讲稿第四十六页，共四十九页定理定理4.4 设方程组设方程组Ax=b的系数矩阵的系数矩阵A为实对称正定矩阵为实对称正定矩阵,且且0 2,则松驰迭代法则松驰迭代法 收敛收敛.说明：定理给出当说明：定理给出当0 2时，松弛迭代法收敛。但是常用的是时，松弛迭代法收敛。但是常用的是1 2的情形，所以本定理发条件称为的情形，所以本定理发条件称为SOR方法的收敛条件，仅为充方法的收敛条件，仅为充分条件。分条件。本讲稿第四十七页，共四十九页例例5:讨论例讨论例2中的方程组用中的方程组用SOR方法求解的收敛性方法求解的收敛性.解解:例例2中方程组的系数矩阵为中方程组的系数矩阵为:方程组方程组首先首先A是对称矩阵是对称矩阵,再由再由知知A是对称正定矩阵是对称正定矩阵.由定理由定理4.4知知,当当0 2时时,用用SOR法求解收敛法求解收敛.本讲稿第四十八页，共四十九页目前，只有少数特殊类型的矩阵，才有确定的最佳松弛因子的目前，只有少数特殊类型的矩阵，才有确定的最佳松弛因子的理论公式。例如，当理论公式。例如，当A为对称正定的三对角矩阵时，为对称正定的三对角矩阵时，则，则SOR法的最佳松弛因子为法的最佳松弛因子为 但这在实际应用时也有一定困难但这在实际应用时也有一定困难常用的方法是，选不同的常用的方法是，选不同的 进行计算，以确定最佳进行计算，以确定最佳 的近似值，的近似值，或者，先选取一个或者，先选取一个 然后根据迭代过程收敛的快慢不然后根据迭代过程收敛的快慢不断修改断修改 ，以此逐步寻找最佳松弛因子，以此逐步寻找最佳松弛因子 。本讲稿第四十九页，共四十九页
