1、Jacobi迭代法與Gauss-Seidel迭代法算法比較目錄1引言11.1 Jacobi迭代法21.2 Gauss-Seidel迭代法21.3 逐次超松弛（SOR）迭代法32算法分析33結(jié)論54附錄程序5參考文獻(xiàn)8Jacobi迭代法與Gauss-Seidel迭代法比較1引言解線性方程組的方法分為直接法和迭代法，直接法是在沒有舍入誤差的假設(shè)下，能在預(yù)定的運(yùn)算次數(shù)內(nèi)求得精確解，而迭代法是構(gòu)造一定的遞推格式，產(chǎn)生逼近精確值的序列。這兩種方法各有優(yōu)缺點(diǎn)，直接法普遍適用，但要求計(jì)算機(jī)有較大的存儲(chǔ)量，迭代法要求的存儲(chǔ)量較小，但必須在收斂性得以保證的情況下才能使用。對于高階方程組，如一些偏微分方程數(shù)值求解

2、中出現(xiàn)的方程組，采用直接法計(jì)算代價(jià)比較高，迭代法則簡單又實(shí)用，所以比較受工程人員青睞。迭代法求解方程組就是構(gòu)造一個(gè)無限的向量序列，使它的極限是方程組的解向量。即使計(jì)算機(jī)過程是精確的，迭代法也不能通過有限次算術(shù)運(yùn)算求得方程組的精確解，而只能逐步逼近它。因此迭代法存在收斂性與精度控制的問題。迭代法是常用于求解大型稀疏線性方程組(系數(shù)矩陣階數(shù)較高且0元素較多)，特別是某些偏微分方程離散化后得到的大型稀疏方程組的重要方法。設(shè)n元線性微分方程組Axb(1)的系數(shù)矩陣A非奇異，右端向量b0,因而方程組有唯一的非零解向量。而對于這種線性方程組的近似解，前輩們發(fā)展研究了許多種有效的方法，有Jacobi迭代法、

3、GaussSeidel迭代法，逐次超松弛迭代法(SOR法)，這幾種迭代方法均屬一階線性定常迭代法，即若系數(shù)矩陣A分解成兩個(gè)矩陣N和P的差，即ANP;其中N為可逆矩陣，線性方程組(1)化為：(NP)xbNxPxb1_1xNPxNb可得到迭代方法的一般公式：x(k1)Gx(k)d(2)其中：GN-1P,dN1b,對任取一向量x(0)作為方程組的初始近似解，按遞推公式產(chǎn)生一個(gè)向量序列x(1),x(2),，x(k),，當(dāng)k足夠大時(shí)，此序列就可以作為線性方程組的近似解。一階定常迭代法收斂的充分必要條件是：迭代矩陣G的譜半徑小于1,即(G)1；又因?yàn)閷τ谌魏尉仃嚪稊?shù)恒有(G)IIGII,故又可得到收斂的一

4、個(gè)充分條件為：IIGII<1。1.1 Jacobi迭代法若D為A的對角素構(gòu)成的對角矩陣，且對角線元素全不為零?？梢詫⑾禂?shù)矩陣A分解為：ADLU其中，D為系數(shù)矩陣A的對角元素構(gòu)成的對角陣，L為嚴(yán)格下三角陣，U為嚴(yán)格上三角陣。在迭代法一般形式中，取ND,P(LU),形成新的迭代公式x(k1)D1(LU)x(k)D1b,k0,1,.其中x任取，則Jacobi迭代的迭代公式為：(k1)-(k),xGjxdJ(3)式中：dJD1b;GjD1(LU),稱Gj為Jacobi迭代矩陣.其計(jì)算公式為：n(4)(k1)1(k)xi一biaiiX,i1,2,.,naiij1如果迭代矩陣Gj的譜半徑(G)1,則

5、對于任意迭代初值x(0),Jacobi迭代法收斂;如果口Gj|<1,則Jacobi迭代法收斂；如果方程組的系數(shù)矩陣是主對角線按行或按列嚴(yán)格占優(yōu)陣，則用Jacobi迭代法求解線性方程組必收斂。1.2 Gauss-Seidel迭代法從Jacobi迭代可以看出，用x(k)計(jì)算x(k1)時(shí)，需要同時(shí)保留這兩個(gè)向量。事實(shí)上如果每次獲得的分量能夠在計(jì)算下一個(gè)分量時(shí)及時(shí)更新的話，既節(jié)省了存儲(chǔ)單元，又能使迭代加速，這就是Gauss-Seidel方法。對于非奇異方程組，若D為A的對角素構(gòu)成的對角矩陣，且對角線元素全不為零；系數(shù)矩陣A的一個(gè)分解：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是其右端常數(shù)項(xiàng)；Gg(DL)1U為Gauss-Seidel迭代法的迭代矩陣，其計(jì)算公式為：xi(k1)1i11(k1)biauxaiij1n(k).auxu,iji11,2,3,.nk0,1,2,.(7)若GS法收斂的充分必要條件是(Gg)1；如果|Gg|<1,則GS法收斂；如果線性方程組的系數(shù)矩陣A為主對角線按行或按列嚴(yán)格占優(yōu)陣，或者為正定矩陣，則對于任意初值x(0)用GS法求解必收斂。1.3 逐次超松弛(SOR)迭代法一

7、般而言，因Jacobi迭代收斂速度不夠快，所以在工程中用的并不是太多。并且在Jacobi迭代收斂速度很慢的情況下，通常Gauss-Seidel迭代法也不會(huì)太快。可以對Gauss-Seidel迭代公式做適度修改，提高收斂速度，這就是逐次超松弛迭代法。設(shè)線性方程組的系數(shù)矩陣A滿足aii0,i1,2,.n?？蓪⑾禂?shù)矩陣A分解為11ADL(1)DU(8)其中實(shí)常數(shù)>0稱為松弛因子。在迭代法一般形式中，取11NDL,P(1)DU)得到迭代公式x(k1)(-DL)1(1-)DU)x的(-DL)1b,k0,1,.(9)其中x(0)任取。這就是逐次超松弛迭代法，當(dāng)=1時(shí)該式就是高斯法。SOR法迭代矩陣是

8、Gs(1DL)1(11)DU)整理后得到SOR迭代法的實(shí)際計(jì)算公式為：i1n(k1)aj(ki)1.(k)aj(k)bixixj(1一)xxji1,2,.,n；k0,1,.(10)j1aiiji1aiiaiiSOR方法收斂的充分必要條件是(Gs)1；如果IIGsII<1,則SOR方法收斂；SOR方法收斂的必要條件是02;如果方程組的系數(shù)矩陣A是主對角線按行或者列嚴(yán)格占優(yōu)陣，則用01的SOR方法求解必收斂；如果方程組的系數(shù)矩陣是正定矩陣，則用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進(jìn)行迭代，其計(jì)算結(jié)果如表1所示0取初始值x00X1區(qū),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進(jìn)行迭代，其計(jì)算結(jié)果如下表2表2k01234567kX100.721.043081.093131.099131.099891.099991.1kX200.9021.167191.195721.199471.199931.199991.2kX301.16441.282051.297771.299721.299961.31.33結(jié)論使用Gauss-Seidel迭代法迭代法，7次就可以求出方程的解，收斂速度要比Jacobi迭代法收斂快(達(dá)到同樣的精度所需

11、迭代次數(shù)少)；但是這個(gè)結(jié)論，在一定條件下才是對的，甚至有這樣的方程組，雅可比方法收斂，而高斯一塞德爾迭代法卻是發(fā)散的.4附錄程序/*求解線性方程組-Gauss-Seidel迭代法*/#include<iostream>#include<cmath>usingnamespacestd;/*二維數(shù)組動(dòng)態(tài)分配模板*/template<classT>T*Allocation2D(intm,intn)T*a;a=newT*m;for(inti=0;i<m;i+)ai=newTn;returna;/*一維數(shù)組動(dòng)態(tài)分配模板*/template<classT&g

12、t;T*Allocation1D(intn)T*a;a=newTn;returna;/*求矩陣的一范數(shù)*/floatmatrix_category(float*x,intn)一floattemp=0;for(inti=0;i<n;i+)temp=temp+fabs(xi);returntemp;intmain()constintMAX=1000;/最大迭代次數(shù)inti,j,k;/循環(huán)變量intn;/矩陣階數(shù)float*a;/增廣矩陣float*x_0;/初始向量float*x_k;/迭代向量floatprecision;/精度cout<<"輸入精度e:"c

13、in>>precision;/*動(dòng)態(tài)生成增廣矩陣*/cout<<endl<<"輸入系數(shù)矩陣的階數(shù)，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;/*求兩解向量的差的范數(shù)*/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<<"迭代次數(shù)為："«k«en