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

Jacobi迭代法与Gauss-Seidel迭代法算法比较目录1引言..............................................................................................................................................11.1Jacobi迭代法....................................................................................................................21.2Gauss-Seidel迭代法..........................................................................................................21.3逐次超松弛（SOR）迭代法............................................................................................32算法分析........................................................................................................................................33结论..............................................................................................................................................54附录程序.......................................................................................................................................5参考文献...........................................................................................................................................8第1页共7页Jacobi迭代法与Gauss-Seidel迭代法比较1引言解线性方程组的方法分为直接法和迭代法，直接法是在没有舍入误差的假设下，能在预定的运算次数内求得精确解，而迭代法是构造一定的递推格式，产生逼近精确值的序列。这两种方法各有优缺点，直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收敛性得以保证的情况下才能使用。对于高阶方程组，如一些偏微分方程数值求解中出现的方程组，采用直接法计算代价比较高，迭代法则简单又实用，所以比较受工程人员青睐。迭代法求解方程组就是构造一个无限的向量序列，使它的极限是方程组的解向量。即使计算机过程是精确的，迭代法也不能通过有限次算术运算求得方程组的精确解，而只能逐步逼近它。因此迭代法存在收敛性与精度控制的问题。迭代法是常用于求解大型稀疏线性方程组（系数矩阵阶数较高且0元素较多），特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。设n元线性微分方程组bAx(1)的系数矩阵A非奇异，右端向量0b,因而方程组有唯一的非零解向量。而对于这种线性方程组的近似解，前辈们发展研究了许多种有效的方法，有Jacobi迭代法、Gauss—Seidel迭代法，逐次超松弛迭代法（SOR法），这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A分解成两个矩阵N和P的差，即PNA；其中N为可逆矩阵，线性方程组(1)化为：bxPN)（bPxNxbNPxNx11可得到迭代方法的一般公式：dGxxkk))1(（（2）其中：PNG1-，bNd1，对任取一向量)0(x作为方程组的初始近似解，按递推公式产生一个向量序列)1(x，)2(x，...，）kx(，...，当k足够大时，此序列就可以作为线性方程组的近似解。一阶定常迭代法收敛的充分必要条件是:迭代矩阵G的谱半径小于1，即1）（G；又因为对于任何矩阵范数恒有）（G‖G‖，故又可得到收敛的一个充分条件为：‖G‖1。第2页共7页1.1Jacobi迭代法若D为A的对角素构成的对角矩阵，且对角线元素全不为零。可以将系数矩阵A分解为：ULDA其中，D为系数矩阵A的对角元素构成的对角阵，L为严格下三角阵，U为严格上三角阵。在迭代法一般形式中，取DN，)(ULP，形成新的迭代公式bDxULDxkk1)(1)1()(，,...1,0k其中)0(x任取，则Jacobi迭代的迭代公式为：JkJkdxGx)()1((3)式中:bDdJ1;)(1ULDGJ,称JG为Jacobi迭代矩阵.其计算公式为:)(1)1(1kjnijjiiiiikixabax，ni,...,2,1（4）如果迭代矩阵JG的谱半径1）（G，则对于任意迭代初值)0(x，Jacobi迭代法收敛；如果‖GJ‖1，则Jacobi迭代法收敛；如果方程组的系数矩阵是主对角线按行或按列严格占优阵，则用Jacobi迭代法求解线性方程组必收敛。1.2Gauss-Seidel迭代法从Jacobi迭代可以看出，用)(kx计算)1(kx时，需要同时保留这两个向量。事实上如果每次获得的分量能够在计算下一个分量时及时更新的话，既节省了存储单元，又能使迭代加速，这就是Gauss-Seidel方法。对于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵A的一个分解：ULDA(5)在迭代法一般形式中，取LDN，UP，形成新的迭代公式bLDUxLDxkk1)(1)1()()(，,...1,0k其中)0(x任取，则Gauss-Seidel迭代法的迭代公式为:fxGxkGk)()1（（6）上式中:bLDf1)(是其右端常数项；ULDGG1)(为Gauss-Seidel迭代法的迭代矩阵，其计算公式为：111)()1()1(1ijnijkjijkjijiiikixaxabax，ni,...3,2,1,...2,1,0k（7）若GS法收敛的充分必要条件是1)GG（；如果‖GG‖1,则GS法收敛；如果线性方程组的系数矩阵A为主对角线按行或按列严格占优阵，或者为正定矩阵，则对于任意初值)0(x用GS法求解必收敛。第3页共7页1.3逐次超松弛（SOR）迭代法一般而言，因Jacobi迭代收敛速度不够快，所以在工程中用的并不是太多。并且在Jacobi迭代收敛速度很慢的情况下，通常Gauss-Seidel迭代法也不会太快。可以对Gauss-Seidel迭代公式做适度修改，提高收敛速度，这就是逐次超松弛迭代法。设线性方程组的系数矩阵A满足0iia，ni,...2,1。可将系数矩阵A分解为UDLDA)11(1(8)其中实常数0称为松弛因子。在迭代法一般形式中，取LDN1,))11((UDP得到迭代公式bLDxUDLDxkk1)(1)1()1())11(()1(，,...1,0k（9）其中)0(x任取。这就是逐次超松弛迭代法，当=1时该式就是高斯法。SOR法迭代矩阵是))11(()1(1UDLDGS整理后得到SOR迭代法的实际计算公式为：111)()()1()1()11(ijnijiiikjiiijkikjiiijkiabxaaxxaaxni,...,2,1；,...1,0k（10）SOR方法收敛的充分必要条件是1）（sG；如果‖GS‖1，则SOR方法收敛；SOR方法收敛的必要条件是20；如果方程组的系数矩阵A是主对角线按行或者列严格占优阵，则用10的SOR方法求解必收敛；如果方程组的系数矩阵是正定矩阵，则用20的SOR方法求解必收敛。2算法分析例1用雅可比迭代法求解下列方程组2453821027210321321321.xxx.xxx.xxx解将方程组按雅可比方法写成第4页共7页840202083020107202010213312321.x.x.x.x.x.x.x.x.x取初始值TT,,,x,x,xx0000302010按迭代公式840202083020107202010211331123211.x.x.x.x.x.x.x.x.xkkkkkkkkk进行迭代，其计算结果如表1所示。表1k01234567kx100.720.9711.0571.08531.09511.0983…kx200.831.0701.15711.18531.19511.1983…kx300.841.1501.24821.28281.29411.2980…例2用高斯——塞德尔迭代法求解例1.解取初始值TT,,,x,x,xx0000302010，按迭代公式840202083020107202010121113311123211.x.x.x.x.x.x.x.x.xkkkkkkkkk进行迭代，其计算结果如下表2表2k01234567kx100.721.043081.093131.099131.099891.099991.1kx200.9021.167191.195721.199471.199931.199991.2kx301.16441.282051.297771.299721.299961.31.3第5页共7页3结论使用Gauss-Seidel迭代法迭代法，7次就可以求出方程的解，收敛速度要比Jacobi迭代法收敛快(达到同样的精度所需迭代次数少)；但是这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯—塞德尔迭代法却是发散的.4附录程序/*求解线性方程组--Gauss-Seidel迭代法*/#includeiostream#includecmathusingnamespacestd;/*二维数组动态分配模板*/templateclassTT**Allocation2D(intm,intn){T**a;a=newT*[m];for(inti=0;im;i++){a[i]=newT[n];}returna;}/*一维数组动态分配模板*/templateclassTT*Allocation1D(intn){T*a;a=newT[n];returna;}/*求矩阵的一范数*/floatmatrix_category(float*x,intn){floattemp=0;for(inti=0;in;i++){temp=temp+fabs(x[i]);}returntemp;}intmain(){constintMAX=1000;//最大迭代次数inti,j,k;//循环变量intn;//矩阵阶数第6页共7页float**a;//增广矩阵float*x_0;//初始向量float*x_k;//迭代向量floatprecision;//精度cout输入精