Jacobi迭代法与Gauss-Seidel迭代法算法比较

1、Jacobi迭代法与Gauss-Seidel迭代法算法比较目录1引言11.1 Jacobi迭代法21.2 Gauss-Seidel迭代法21.3 逐次超松弛（SOR）迭代法32算法分析33结论54附录程序5参考文献8Jacobi迭代法与Gauss-Seidel迭代法比较1引言解线性方程组的方法分为直接法和迭代法，直接法是在没有舍入误差的假设下，能在预定的运算次数内求得精确解，而迭代法是构造一定的递推格式，产生逼近精确值的序列。这两种方法各有优缺点，直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收敛性得以保证的情况下才能使用。对于高阶方程组，如一些偏微分方程数值求解

2、中出现的方程组，采用直接法计算代价比较高，迭代法则简单又实用，所以比较受工程人员青睐。迭代法求解方程组就是构造一个无限的向量序列，使它的极限是方程组的解向量。即使计算机过程是精确的，迭代法也不能通过有限次算术运算求得方程组的精确解，而只能逐步逼近它。因此迭代法存在收敛性与精度控制的问题。迭代法是常用于求解大型稀疏线性方程组(系数矩阵阶数较高且0元素较多)，特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。设n元线性微分方程组Axb(1)的系数矩阵A非奇异，右端向量b0,因而方程组有唯一的非零解向量。而对于这种线性方程组的近似解，前辈们发展研究了许多种有效的方法，有Jacobi迭代法、

3、GaussSeidel迭代法，逐次超松弛迭代法(SOR法)，这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A分解成两个矩阵N和P的差，即ANP;其中N为可逆矩阵，线性方程组(1)化为：(NP)xbNxPxb1_1xNPxNb可得到迭代方法的一般公式：x(k1)Gx(k)d(2)其中：GN-1P,dN1b,对任取一向量x(0)作为方程组的初始近似解，按递推公式产生一个向量序列x(1),x(2),，x(k),，当k足够大时，此序列就可以作为线性方程组的近似解。一阶定常迭代法收敛的充分必要条件是：迭代矩阵G的谱半径小于1,即(G)1；又因为对于任何矩阵范数恒有(G)IIGII,故又可得到收敛的一

4、个充分条件为：IIGII<1。1.1 Jacobi迭代法若D为A的对角素构成的对角矩阵，且对角线元素全不为零。可以将系数矩阵A分解为：ADLU其中，D为系数矩阵A的对角元素构成的对角阵，L为严格下三角阵，U为严格上三角阵。在迭代法一般形式中，取ND,P(LU),形成新的迭代公式x(k1)D1(LU)x(k)D1b,k0,1,.其中x任取，则Jacobi迭代的迭代公式为：(k1)-(k),xGjxdJ(3)式中：dJD1b;GjD1(LU),称Gj为Jacobi迭代矩阵.其计算公式为：n(4)(k1)1(k)xi一biaiiX,i1,2,.,naiij1如果迭代矩阵Gj的谱半径(G)1,则

5、对于任意迭代初值x(0),Jacobi迭代法收敛;如果口Gj|<1,则Jacobi迭代法收敛；如果方程组的系数矩阵是主对角线按行或按列严格占优阵，则用Jacobi迭代法求解线性方程组必收敛。1.2 Gauss-Seidel迭代法从Jacobi迭代可以看出，用x(k)计算x(k1)时，需要同时保留这两个向量。事实上如果每次获得的分量能够在计算下一个分量时及时更新的话，既节省了存储单元，又能使迭代加速，这就是Gauss-Seidel方法。对于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵A的一个分解：ADLU在迭代法一般形式中，取NDL,PU,形成新的迭代公式x

6、(k1)(DL)1Ux(k)(DL)1b,k0,1,.其中x(0)任取，则Gauss-Seidel迭代法的迭代公式为：x(k1)Ggx的f(6)上式中：f(DL)1b是其右端常数项；Gg(DL)1U为Gauss-Seidel迭代法的迭代矩阵，其计算公式为：xi(k1)1i11(k1)biauxaiij1n(k).auxu,iji11,2,3,.nk0,1,2,.(7)若GS法收敛的充分必要条件是(Gg)1；如果|Gg|<1,则GS法收敛；如果线性方程组的系数矩阵A为主对角线按行或按列严格占优阵，或者为正定矩阵，则对于任意初值x(0)用GS法求解必收敛。1.3 逐次超松弛(SOR)迭代法一

7、般而言，因Jacobi迭代收敛速度不够快，所以在工程中用的并不是太多。并且在Jacobi迭代收敛速度很慢的情况下，通常Gauss-Seidel迭代法也不会太快。可以对Gauss-Seidel迭代公式做适度修改，提高收敛速度，这就是逐次超松弛迭代法。设线性方程组的系数矩阵A满足aii0,i1,2,.n。可将系数矩阵A分解为11ADL(1)DU(8)其中实常数>0称为松弛因子。在迭代法一般形式中，取11NDL,P(1)DU)得到迭代公式x(k1)(-DL)1(1-)DU)x的(-DL)1b,k0,1,.(9)其中x(0)任取。这就是逐次超松弛迭代法，当=1时该式就是高斯法。SOR法迭代矩阵是

8、Gs(1DL)1(11)DU)整理后得到SOR迭代法的实际计算公式为：i1n(k1)aj(ki)1.(k)aj(k)bixixj(1一)xxji1,2,.,n；k0,1,.(10)j1aiiji1aiiaiiSOR方法收敛的充分必要条件是(Gs)1；如果IIGsII<1,则SOR方法收敛；SOR方法收敛的必要条件是02;如果方程组的系数矩阵A是主对角线按行或者列严格占优阵，则用01的SOR方法求解必收敛；如果方程组的系数矩阵是正定矩阵，则用02的SOR方法求解必收敛。2算法分析用雅可比迭代法求解下列方程组10XiX22X37.2x10X22X38.3XiX25x34.2例1解将方程组按雅

9、可比方法写成0.1X20.2X30.72x20.1x10.2x30.83X30.2Xi0.2X20.840取初始值XXi,X20,X30,0,0,按迭代公式00.1x2k0.2x3k0.72X2k10.iXik0.2x3k0.83x3k10.2x1k0.2x2k0.84进行迭代，其计算结果如表1所示0取初始值x00X1区,X3TT0，0，0，,按迭代公式表1k01234567kX100.720.9711.0571.08531.09511.0983kX200.831.0701.15711.18531.19511.1983kX300.841.1501.24821.28281.29411.2980用

10、高斯一一塞德尔迭代法求解例1.x1k10.1x2k0.2x3k0.72x2k10.仅0.2x3k0.83x3k10.2x1k10.2x2k10.84进行迭代，其计算结果如下表2表2k01234567kX100.721.043081.093131.099131.099891.099991.1kX200.9021.167191.195721.199471.199931.199991.2kX301.16441.282051.297771.299721.299961.31.33结论使用Gauss-Seidel迭代法迭代法，7次就可以求出方程的解，收敛速度要比Jacobi迭代法收敛快(达到同样的精度所需

11、迭代次数少)；但是这个结论，在一定条件下才是对的，甚至有这样的方程组，雅可比方法收敛，而高斯一塞德尔迭代法却是发散的.4附录程序/*求解线性方程组-Gauss-Seidel迭代法*/#include<iostream>#include<cmath>usingnamespacestd;/*二维数组动态分配模板*/template<classT>T*Allocation2D(intm,intn)T*a;a=newT*m;for(inti=0;i<m;i+)ai=newTn;returna;/*一维数组动态分配模板*/template<classT&g

12、t;T*Allocation1D(intn)T*a;a=newTn;returna;/*求矩阵的一范数*/floatmatrix_category(float*x,intn)一floattemp=0;for(inti=0;i<n;i+)temp=temp+fabs(xi);returntemp;intmain()constintMAX=1000;/最大迭代次数inti,j,k;/循环变量intn;/矩阵阶数float*a;/增广矩阵float*x_0;/初始向量float*x_k;/迭代向量floatprecision;/精度cout<<"输入精度e:"c

13、in>>precision;/*动态生成增广矩阵*/cout<<endl<<"输入系数矩阵的阶数，N："cin>>n;a=Allocation2D<float>(n,n+1);/*输入增广矩阵的各值*/cout<<endl<<"输入增广矩阵的各值：n"for(i=0;i<n;i+)for(j=0;j<n+1;j+)cin>>aij;/*生成并初始化初始向量*/x_0=Allocation1D<float>(n);cout<<

14、endl<<"输入初始向量：n"for(i=0;i<n;i+)cin>>x_0i;/*生成迭代向量*/x_k=Allocation1D<float>(n);floattemp;/*迭代过程*/for(k=0;k<MAX;k+)for(i=0;i<n;i+)temp=0;for(j=0;j<i;j+)temp=temp+aij*x_kj;x_ki=ain-temp;temp=0;for(j=i+1;j<n;j+)temp=temp+aij*x_0j;x_ki=(x_ki-temp)/aii;/*求两解向量的差的范数*/for(i=0;i<n;i+)x_Oi=x_ki-x_Oi;if(matrix_category(x_0,n)<precision)-"break;)else(for(i=0;i<n;i+)(x_0i=x_ki;)/*输出过程*/if(MAX=k)cout<<"迭代不收敛n")cout<<"迭代次数为："«k«en