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

1、标准实用Jacobi 迭代法与 Gauss-Seidel 迭代法算法比较目录1 引言 11.1 Jacobi 迭代法2.1.2 Gauss-Seidel迭代法 2.1.3 逐次超松弛（SOR ）迭代法 3.2 算法分析 4.3 结论 54 附录程序 6.参考文献 1.0.文案大全Jacobi 迭代法与Gauss-Seidel迭代法比较1引言解线性方程组的方法分为直接法和迭代法，直接法是在没有舍入误差的假设下，能在预定的运算次数内求得精确解，而迭代法是构造一定的递推格式，产生逼近精确值的序列。 这两种方法各有优缺点， 直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收

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

3、对于这种线性方程组的近似解，前辈们发展研究了许多种有效的方法，有Jacobi迭代法、Gauss Seidel迭代法，逐次超松弛迭代法（SOR法），这几种迭代方法均属一阶线性定常迭代法，即若系 数矩阵A分解成两个矩阵 N和P的差，即A N P ;其中N为可逆矩阵，线性方程组（1） 化为：（NP)xbNxPxbx N1PxN可得到迭代方法的一般公式:(k 1)(k)x Gx d(2)其中：G N-1P , d N 1b，对任取一向量x(0)作为方程组的初始近似解，按递推公式产生一个向量序列x，x(2)，x(k),，当k足够大时，此序列就可以作为线性方程组的 近似解。(G)1 ;又因为对于任何矩阵范

4、数恒有(G) IIG 故又可得到收敛的一个充分条件为:IIG|< 1。一阶定常迭代法收敛的充分必要条件是：迭代矩阵G的谱半径小于1，即1.1 Jacobi迭代法A分解若D为A的对角素构成的对角矩阵，且对角线元素全不为零。可以将系数矩阵 为:其中，D为系数矩阵A的对角元素构成的对角阵，L为严格下三角阵，U为严格上三角阵。在迭代法一般形式中，取 N D , P (L U)，形成新的迭代公式x(k 1)1(k)1D (L U)x D b , k 0,1,.其中x(0)任取，则Jacobi迭代的迭代公式为:x(k 1) Gj x(k) dJ1式中：dJD b ；GJ1(LU ),称Gj为Jaco

5、bi迭代矩阵.其计算公式为：如果迭代矩阵xi(k 1)aiin(k)biaiixj, i 1,2,., nj 1(4)Gj的谱半径(G)1，则对于任意迭代初值x(0) , Jacobi迭代法收敛;如果IIGjI<1，则Jacobi迭代法收敛；如果方程组的系数矩阵是主对角线按行或按列严格占 优阵，则用Jacobi迭代法求解线性方程组必收敛。1.2 Gauss-Seidel 迭代法从Jacobi迭代可以看出，用x(k)计算x(k 1)时，需要同时保留这两个向量。事实上如果每次获得的分量能够在计算下一个分量时及时更新的话，既节省了存储单元，又能使迭代加速，这就是Gauss-Seidel方法。对

6、于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵 A的一个分解：A D L U在迭代法一般形式中，取N D L , P U，形成新的迭代公式x(k 1)(D L) 1Ux(k)(D L) 1b, k 0,1,.其中x任取，则Gauss-Seidel迭代法的迭代公式为：x"* °GGx")f(6)1 1上式中：f (D L) 1b是其右端常数项；Gg (D L) 1U为Gauss-Seidel迭代法 的迭代矩阵，其计算公式为：i 1 n(k 1)li(k 1)(k)ccxi 一 biajXjaux， i 1,2,3,.n k 0,1,2

7、,.(7)aiij 1j i 1若GS法收敛的充分必要条件是(Gg) 1 ;如果II Gg |<1,则GS法收敛；如果线性方程组的系数矩阵 A为主对角线按行或按列严格占优阵，或者为正定矩阵，则对于任意初 值x(0)用GS法求解必收敛。1.3逐次超松弛(SOR)迭代法一般而言，因 Jacobi迭代收敛速度不够快，所以在工程中用的并不是太多。并且在Jacobi迭代收敛速度很慢的情况下，通常Gauss-Seidel 迭代法也不会太快。可以对Gauss-Seidel迭代公式做适度修改，提高收敛速度，这就是逐次超松弛迭代法。设线性方程组的系数矩阵A满足aii 0, i 1,2,.n。可将系数矩阵

8、A分解为1 1A D L (1 )D U(8)其中实常数 >0称为松弛因子。在迭代法一般形式中，取1 1N D L , P (1 )D U)得到迭代公式x(k o(丄 d L) 1(1 )D U)x(k)(丄 D L) 1b , k 0,1,.(9)其中x(0)任取。这就是逐次超松弛迭代法，当 =1时该式就是高斯法。SOR法迭代矩阵是Gs(D L) 1(1 )D U )整理后得到SOR迭代法的实际计算公式为：(k 1)i 1小 aj(k i)Xij 1 aiiaij肆j i iaiibiaiii 1,2,., n ； k 0,1,. (10)SOR方法收敛的充分必要条件是（Gs） 1 ;

9、如果I|Gs<1 ,则SOR方法收敛；SOR方法收敛的必要条件是 02;如果方程组的系数矩阵 A是主对角线按行或者列严格占优阵，则用01的SOR方法求解必收敛；如果方程组的系数矩阵是正定矩阵，则用02的SOR方法求解必收敛。2算法分析例1 用雅可比迭代法求解下列方程组10 x1X22X37.2x110x2 2x38.3X1x2 5x34.2解将方程组按雅可比方法写成X10. 1x20.2x30.72X0.1x10.2X30.83X30.2x10.2x20.84000 0 'TT取初始值XX1,X2,X30,0,0,按迭代公式kX110.1x2k0.2x3k0.72kX10.1x1

10、k0.2x3k0.83kX310.2x1k0.2x2k0.84进行迭代，其计算结果如表1所示。表1k01234567kX100.720.9711.0571.08531.09511.0983kX200.831.0701.15711.18531.19511.1983kX300.841.1501.2481.28281.29411.29802例2用高斯塞德尔迭代法求解例1.0 0 0 0 T解 取初始值XX1 ，X2 ，x3k 1X10.1x2k0.2x3k0.72k 1X20.1x1k10.2x3k0.83k 1X30.2x1k10.2x2k 10.84进行迭代，其计算结果如下表2表2k012345

11、67kX100.721.04301.09311.09911.09981.09991.183399kX200.9021.16711.19571.19941.19991.19991.292739kX301.1641.28201.29771.29971.29991.31.3457263结论使用Gauss-Seidel迭代法迭代法，7次就可以求出方程的解，收敛速度要比Jacobi，甚迭代法收敛快（达到同样的精度所需迭代次数少）；但是这个结论，在一定条件下才是对的至有这样的方程组，雅可比方法收敛，而高斯一塞德尔迭代法却是发散的4附录程序/*求解线性方程组-Gauss-Seidel 迭代法*/#in el

12、ude <iostream>#in elude <cmath> using n amespaee std;/*二维数组动态分配模板*/template <elass T>T* Alloeatio n2D(i nt m, i nt n)T *a;a = new T*m;for (int i=0; i<m; i+)ai = new Tn; return a;/* 一维数组动态分配模板*/template <elass T>T* Alloeation1D(int n)T *a;a = new Tn;return a;/*求矩阵的一范数*/floa

13、t matrix_eategory(float* x, i nt n) float temp = 0;for(int i=0; i<n; i+)temp = temp + fabs(xi); return temp;int main()const int MAX = 1000;/ 最大迭代次数int i,j,k;/ 循环变量int n;/ 矩阵阶数float* a;/ 增广矩阵float* x_0;/ 初始向量float* x_k;/ 迭代向量float precision;/ 精度cout<<" 输入精度 e:"cin>>precision;

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

15、 输入初始向量 :n" for(i=0; i<n; i+)cin>>x_0i;/* 生成迭代向量 */ x_k = Allocation1D<float>(n);float temp;/* 迭代过程 */ 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_0i = x_ki - x_0i; if(matrix_category(x_0,n) < precision) break;elsefor(i=0; i<n; i+)x_Oi = x_ki;/*输出过程*/if(MAX = k)cout<<" 迭代不收敛n"cout<<"迭代次数为："<<k<<e ndl;