1、 前面介绍的解线性方程组的直接法是解低阶稠密方程组的有效方法。但是，在工程技术中常产生大型稀疏矩阵方程组，例如由某些偏微分方程数值解所产生的线性方程组Ax=b，A的阶数很大 ，但零元素较多，迭代法是能够充分利用系数矩阵稀疏性特点的有效算法。4(10)n 迭代法的构造迭代法的构造 迭代法的基本思想是用逐次逼近的方法求线性方程组的解。设有方程组 ,将其转化为等价的便于迭代的形式（这种转化总能实现，如令 ）并由此构造迭代公式bAx fBxxbfAIB,fBxxkk)()1(其中，称为迭代矩阵，称为迭代向量。对任意的初始向量 ，由迭代式可求得向量序列 若 ，则 就是方程组Ax=b的解.Bf)0(x0)
2、(kx*)(limxxkk*x4.1 解线性方程组的三种迭代法解线性方程组的三种迭代法4.1.14.1.1雅克比（雅克比（Jacobi）迭代法（以三阶方程组为例）迭代法（以三阶方程组为例）设有方程组设有方程组：11 1122133121 1222233231 13223333a xa xa xba xa xa xba xa xa xb假设任选一向量X(0)作为解的初值.0 i=1,2,3iia 则方程组可写为：11122133112221 1233223331 1322331(-a)1(-a )(4.1)1(-a )xbxa xaxbxa xaxbxa xa(0)(0)(0)(0)123(,)
3、Xxxx代入式(4.1)中得方程组的一次近似.(1)(1)(1)(1)123(,)Xxxx把X(1)再代入到(4.1)中得方程组的二次近似.(2)(2)(2)(2)123(,)Xxxx重复这一过程,假设得到了m次近似X(m)。代入到(4.1)中可得m+1次近似X(m+1)。(1)()()1112213311(1)()()2221123322(1)()()33311322331(-a)1(-a )1(-a )mmmmmmmmmxbxa xaxbxa xaxbxa xa称此迭代公式为原方程组的雅可比迭代公式.对于n阶方程组ij1ii,A=(a),()a0 i=1,2,nn njnAxbbb设则雅可
4、比迭代公式为:(0)(0)(0)(0)121(1)()()11(,)1()1,2,.0,1,2,.Tninmmmiiijjijjjj iiixxxxxba xa xainm 若用矩阵来记录雅可比矩阵,可作如下的推导:令A=D-L-U,其中112122313212,1121312321000 -L=,000-U=00 nnn nnnnnnnaaaaaDaaaaaaaaaa则有AX=DX-LX-UX=b.即DX=b+(L+U)X从而有DX(m+1)=b+(L+U)X(m).若则D可逆,于是得0(i=1,2,n)iia(1)1()1()J11()=B(),mmmJJJxDLU xD bxfBDLUf
5、D b称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)的极限,记为:()*limmmXX例 用简单迭代法解下列方程组 1231231231027.21028.354.2xxxxxxxxx解将方程组写成等价形式1232133120.10.20.720.10.20.830.20.20.84xxx
6、xxxxxx取初始值x(0)=0,按迭代公式(1)()()122(1)()()213(1)()()3120.10.20.720.10.20.830.20.20.84kkkkkkkkkxxxxxxxxx4.1.2 高斯赛德尔迭代法对雅可比迭代法作如下的改进:将初值代入4.1的第一个方程可得 ,用 代入第二个方程得 ,用 代入第三个方程得 ,这样一直做下去,直到得到满意的解为止.之所以作这样的改进是希望更快的得到近似解.(0)(0)(0)(0)123(,)Xxxx(0)1x(1)(0)(0)123(,)xxx(1)2x(1)(1)(0)123(,)xxx(1)3x这种迭代的方法用公式写出来就是:(
7、1)()()1112213311(1)(1)()2221 123322(1)(1)(1)3331 1322331()1()1()mmmmmmmmmxba xa xaxba xa xaxba xa xa对给定的初值,用此迭代公式求线性方程组的方法被称为高斯塞德尔迭代法。（GS）1(1)(1)()111()1,2,;0,1,2,.(4.8)inmmmiiijjijjjj iiixba xa xain m 一般地,对n阶线性方程组的迭代格式改为:用矩阵表示此方法为：(1)(1)()mmmDXbLXUX即：(1)1()1()G()()=BmmmGXDLUXDLbXf称BG为高斯塞德尔迭代矩阵例 用赛德
8、尔迭代法解方程组 1231231231027.21028.354.2xxxxxxxxx解 将原方程组写成等价形式并按(375)构造赛德尔迭代公式(1)()()123(1)(1)()213(1)(1)(1)3120.10.20.720.10.20.830.20.20.84kkkkkkkkkxxxxxxxxx例1：分别用两种迭代法求下列线性方程组。初值均取(0，0，0)T解:用matlab解,程序如下123911718071098xxx%用雅可比法解P91例1a=9,-1,-1;-1,8,0;-1,0,9;D=-(a-triu(a)-tril(a);L=-(tril(a)-b);U=-(triu(
9、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+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=
10、x;endk,x 在多数情况下用高斯赛德尔迭代法比雅克比迭代法收敛快。但也有相反的情况，即高斯赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯赛德尔迭代法发散的情形。4.1.3 超松弛迭代法超松弛迭代法 弛迭代法是高斯赛德尔迭代法的一种改进,是解大型稀疏矩阵方程组的有效方法之一.现在研究如何求向量 首先，由高斯赛德尔迭代法求出一个值，记个分量的前次迭代向量，及第次迭代向量设已知第11)1()(iXkXkkk，)1,.,2,1()1(ijxkj。个分量的第)1()1(kikxiX)(1)(1)1(11)1(kjnijijkjijijiiikixaxabax),.,2,1(ni 首
11、先，由高斯赛德尔迭代法求出一个值，记)(1)(1)1(11)1(kjnijijkjijijiiikixaxabax),.,2,1(ni，即均，得进行加权平与个分量次迭代向量的第再将第)1()1()(kikikixxxik(1)()(1)()(1)()(1)()kkkkkkiiiiiixxxxxx1111()()()()(inkkkkiiiijjijjjj iiixxba xa xa ）),.,2,1(ni)()1(1)()1(11)()1(nijkjijkjijijiiikikixaxabaxx或.迭代公式于是得SOR用此公式求解线性方程组的方法称为带有松弛因子的松弛迭代法.当1时称为超松弛迭
12、代法;(SOR法)当ep 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,xMatlab的关于三种迭代法的通用程序%雅可比法解方程的通用程序%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)ep k=k+1;x=D(L+U)*xo+Dbo;dx=norm(x-xo);xo=x;end1.雅可比迭代法的通用程序2.高斯_塞德尔迭代
13、法的通用程序%G_S法解方程组的通用程序%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)ep k=k+1;x=(D-L)U*xo+(D-L)bo;dx=norm(x-xo);xo=x;end3.SOR法解线性方程组的通用程序%SOR法解方程组的通用程序%A为线性方程组,X为初值%omiga为松弛因子function x,k=ya3(A,X,omiga)n=length(A);a=A(:,1:n-1);bo=A(:,n);N=size(X);if N(1)ep k=k+1;
14、x=(D-omiga*L)(omiga*U+(1-omiga)*D)*xo+(D-omiga*L)bo*omiga;dx=norm(x-xo);xo=x;end4.2 迭代法的收敛条件 前面介绍了三种迭代法.从例子看到这三种迭代法都有成功的时候.但我们也可以预计,某种迭代法可能会失效.下面我们试图从理论上来探讨这一问题.三种迭代法的统一写法为:(1)()mmxBxf定义定义 设给定设给定Rn中的向量序列中的向量序列 ，即，即()mx(0)(1)(),mxxx其中其中 ()()()()12,Tmmmmnxxxx 若对任何若对任何i(i=1,2,n)都有都有()*limmiimxx ()*limm
15、mxx 或者说向量序列或者说向量序列 依坐标收敛于向量，记为依坐标收敛于向量，记为()mx则向量则向量*1(,)Tnxxx()mx称为向量序列称为向量序列 的极限的极限，4.2.1 迭代法收敛的概念迭代法收敛的概念证证:()*()*m()*()*1limlim()0(1,2,)lim max0lim0mmiimmmiimmi nxxxxinxxxx 由再由范数的等价性有再由范数的等价性有()*()*limlim0mmmmxxxx引理引理 向量序列向量序列x(m)依坐标收敛于依坐标收敛于x*的充要条件是的充要条件是()*lim0mkxx 向量序列依范数收敛与依坐标收敛是等价的。向量序列依范数收敛
16、与依坐标收敛是等价的。如果满足此式，称如果满足此式，称x(m)依范数收敛于依范数收敛于x*定义定义4.2 设设x*是方程组是方程组Ax=b的解的解,对于给定的初始向对于给定的初始向量量x(0),若由某种迭代法产生的向量序列若由某种迭代法产生的向量序列x(m)有有()*limmmxx则称该方法收敛则称该方法收敛,否则称该方法发散否则称该方法发散.4.2.2 迭代法收敛的判定定理迭代法收敛的判定定理定理定理4.1 设设(1)(),mmxBxf若若1pBq则对任意的初始向量则对任意的初始向量(0)x,该迭代过程收敛于该迭代过程收敛于xBxf的唯一解的唯一解*x,且有估计式且有估计式*()(1)()*
17、()(1)(0)1(1)1(2)1mmmppmmppxxxxqqxxxxq证证:先证先证 若若1,pB则则E-B非奇异非奇异.用反证法用反证法:设设E-B是奇异的是奇异的,则存在非零向量则存在非零向量x,使使(E-B)x=0.即有即有x=Bx.两边取范数两边取范数,再由范数的性质得再由范数的性质得ppppxBxBx由于由于0,px得得1pB与与1pB矛盾矛盾由于由于E-B是非奇异的，所以方程组是非奇异的，所以方程组(E-B)x=f 的解存在且唯一的解存在且唯一.设为设为x*,即即x*=Bx*+f,进而有进而有*(1)*()()mmxxB xx取范数得取范数得:*(1)*()*()2*(1)*(
18、0)mmpppmmppmpxxBxxq xxqxxqxx由于由于0q1由此例可以看到由此例可以看到:对原方程组直接写出雅可比迭代公式是对原方程组直接写出雅可比迭代公式是不收敛的不收敛的.2242JEB其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛其系数矩阵是严格对角占优的所以用雅可比迭代法求解收敛.其迭代格式为其迭代格式为:121211221122xxxx(0)(0)12(1)()12(1)()21x0,0,11221122mmmmxxxxx 如果写出与原方程组等价的方程组如果写出与原方程组等价的方程组定理定理4.4 设方程组设方程组Ax=b的系数矩阵的系数矩阵A为实对称正定矩阵为实对称
19、正定矩阵,且且0 2,则松驰迭代法则松驰迭代法 收敛收敛.说明：定理给出当说明：定理给出当0 2时，松弛迭代法收敛。但是常用的时，松弛迭代法收敛。但是常用的是是1 2的情形，所以本定理发条件称为的情形，所以本定理发条件称为SOR方法的收敛方法的收敛条件，仅为充分条件。条件，仅为充分条件。例例5:讨论例讨论例2中的方程组用中的方程组用SOR方法求解的收敛性方法求解的收敛性.解解:例例2中方程组的系数矩阵为中方程组的系数矩阵为:方程组方程组424217104109首先首先A是对称矩阵是对称矩阵,再由再由12det()4;det()64;det()2AAA知知A是对称正定矩阵是对称正定矩阵.由定理由
20、定理4.4知知,当当0 2时时,用用SOR法求解收法求解收敛敛.目前，只有少数特殊类型的矩阵，才有确定的最佳松弛目前，只有少数特殊类型的矩阵，才有确定的最佳松弛因子的理论公式。例如，当因子的理论公式。例如，当A为对称正定的三对角矩为对称正定的三对角矩阵时，阵时，则，则SOR法的最佳松弛因子为法的最佳松弛因子为 但这在实际应用时也有一定困难但这在实际应用时也有一定困难，迭代法的收敛速度最快的值，使如何选取SOR1)(JB若,1122b常用的方法是，选不同的常用的方法是，选不同的 进行计算，以确定最佳进行计算，以确定最佳 的近似的近似值，或者，先选取一个值，或者，先选取一个 然后根据迭代过程收敛然后根据迭代过程收敛的快慢不断修改的快慢不断修改 ，以此逐步寻找最佳松弛因子，以此逐步寻找最佳松弛因子 。，)20(b
