1、 前面介绍解线性方程组直接法是解低阶稠密方程组有效方法。不过，在工程技术中常产生大型稀疏矩阵方程组，比如由一些偏微分方程数值解所产生线性方程组Ax=b，A阶数很大 ，但零元素较多，迭代法是能够充分利用系数矩阵稀疏性特点有效算法。第四章第四章 解线性方程组迭代法解线性方程组迭代法 1/49迭代法结构迭代法结构 迭代法基本思想是用逐次迫近方法求线性方程组解。设有方程组 ,将其转化为等价便于迭代形式（这种转化总能实现，如令 ）并由此结构迭代公式 其中，称为迭代矩阵，称为迭代向量。对任意初始向量 ，由迭代式可求得向量序列 若 ，则 就是方程组Ax=b解.2/494.1 解线性方程组三种迭代法解线性方程
2、组三种迭代法4.1.14.1.1雅克比（雅克比（Jacobi）迭代法（以三阶方程组为例）迭代法（以三阶方程组为例）设有方程组设有方程组：3/49假设任选一向量X(0)作为解初值.则方程组可写为：代入式(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
3、(m+1)=b+(L+U)X(m).若则D可逆,于是得称BJ为雅可比迭代矩阵.这种迭代格式称为雅可比迭代格式。8/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/494.1.2 高斯赛德尔迭代法对雅可比迭代法作以下改进:将初值代
4、入4.1第一个方程可得 ,用 代入第二个方程得 ,用 代入第三个方程得 ,这么一直做下去,直到得到满意解为止.之所以作这么改进是希望更加快得到近似解.12/49这种迭代方法用公式写出来就是:13/49对给定初值,用此迭代公式求线性方程组方法被称为高斯塞德尔迭代法。（GS）普通地,对n阶线性方程组迭代格式改为:14/49用矩阵表示此方法为：即：称BG为高斯塞德尔迭代矩阵15/49例 用赛德尔迭代法解方程组 解 将原方程组写成等价形式并按(375)结构赛德尔迭代公式16/4917/49 在多数情况下用高斯赛德尔迭代法比雅克比迭代法收敛快。但也有相反情况，即高斯赛德尔迭代法比雅克比迭代法收敛慢，甚至
5、还有雅克比迭代法收敛，高斯赛德尔迭代法发散情形。20/494.1.3 超松弛迭代法超松弛迭代法 弛迭代法是高斯赛德尔迭代法一个改进,是解大型稀疏矩阵方程组有效方法之一.现在研究怎样求向量 首先，由高斯赛德尔迭代法求出一个值，记21/49首先，由高斯赛德尔迭代法求出一个值，记22/49用此公式求解线性方程组方法称为带有松弛因子松弛迭代法.当1时称为超松弛迭代法;(SOR法)当1时称为低松弛迭代法;当=1时就是GS迭代法.当一些方程组用高斯赛德尔迭代法不收敛时，能够用低松弛方法取得收敛，23/49将上式写成矩阵形式，得：于是得SOR迭代矩阵表示 24/494.2 迭代法收敛条件 前面介绍了三种迭代
6、法.从例子看到这三种迭代法都有成功时候.但我们也能够预计,某种迭代法可能会失效.下面我们试图从理论上来探讨这一问题.三种迭代法统一写法为:30/49定义定义 设给定设给定Rn中向量序列中向量序列 ，即，即其中其中若对任何若对任何i(i=1,2,n)都有都有或者说向量序列或者说向量序列 依坐标收敛于向量，记为依坐标收敛于向量，记为则向量则向量 称为向量序列称为向量序列 极限极限，4.2.1 迭代法收迭代法收敛概念概念31/49证证:再由范数等价性有再由范数等价性有引理引理 向量序列向量序列x(m)依坐标收敛于依坐标收敛于x*充要条件是充要条件是向量序列依范数收敛与依坐标收敛是等价。向量序列依范数
7、收敛与依坐标收敛是等价。假如满足此式，称假如满足此式，称x(m)依范数收敛于依范数收敛于x*32/49定义定义4.2 设设x*是方程组是方程组Ax=b解解,对于给定初始向量对于给定初始向量x(0),若由某种迭代法产生向量序列若由某种迭代法产生向量序列x(m)有有则称该方法收敛则称该方法收敛,不然称该方法发散不然称该方法发散.33/494.2.2 迭代法收敛判定定理迭代法收敛判定定理定理定理4.1 设设若若则对任意初始向量则对任意初始向量,该迭代过程收敛于该迭代过程收敛于唯一解唯一解,且有预计式且有预计式34/49证证:先证先证 若若则则E-B非奇异非奇异.用反证法用反证法:设设E-B是奇异是奇
8、异,则存在非零向量则存在非零向量x,使使(E-B)x=0.即有即有x=Bx.两两边取范数边取范数,再由范数性质得再由范数性质得因为因为得得与与矛盾矛盾35/49因为因为E-B是非奇异，所以方程组是非奇异，所以方程组(E-B)x=f 解存在且唯一解存在且唯一.设为设为x*,即即x*=Bx*+f,进而有进而有取范数得取范数得:因为因为0q1由此例能够看到由此例能够看到:对原方程组直接写出雅可比迭代公式是对原方程组直接写出雅可比迭代公式是不收敛不收敛.45/49其系数矩阵是严格对角占优所以用雅可比迭代法求解收敛其系数矩阵是严格对角占优所以用雅可比迭代法求解收敛.其其迭代格式为迭代格式为:假如写出与原
9、方程组等价方程组假如写出与原方程组等价方程组46/49定理定理4.4 设方程组设方程组Ax=b系数矩阵系数矩阵A为实对称正定矩阵为实对称正定矩阵,且且0 2,则松驰迭代法则松驰迭代法 收敛收敛.说明：定理给出当说明：定理给出当0 2时，松弛迭代法收敛。不过惯用是时，松弛迭代法收敛。不过惯用是1 2情形，所以本定剪发条件称为情形，所以本定剪发条件称为SOR方法收敛条件，方法收敛条件，仅为充分条件。仅为充分条件。47/49例例5:讨论例讨论例2中方程组用中方程组用SOR方法求解收敛性方法求解收敛性.解解:例例2中方程组系数矩阵为中方程组系数矩阵为:方程组方程组首先首先A是对称矩阵是对称矩阵,再由再
10、由知知A是对称正定矩阵是对称正定矩阵.由定理由定理4.4知知,当当0 2时时,用用SOR法求解收法求解收敛敛.48/49当前，只有少数特殊类型矩阵，才有确定最正确松弛因当前，只有少数特殊类型矩阵，才有确定最正确松弛因子理论公式。比如，当子理论公式。比如，当A为对称正定三对角矩阵时，为对称正定三对角矩阵时，则，则SOR法最正确松弛因子为法最正确松弛因子为 但这在实际应用时也有一定困难但这在实际应用时也有一定困难惯用方法是，选不一样惯用方法是，选不一样 进行计算，以确定最正确进行计算，以确定最正确 近似值，近似值，或者，先选取一个或者，先选取一个 然后依据迭代过程收敛快慢然后依据迭代过程收敛快慢不停修改不停修改 ，以此逐步寻找最正确松弛因子，以此逐步寻找最正确松弛因子 。49/49
