雅可比迭代法和高斯超松弛迭代

雅可比迭代法和高斯-賽德爾迭代法以及超松弛迭代對于給定的方程用下式逐步代入求近似解的方法稱為迭代法。如xk(當)的極限存在，此極限即方程組的真正解，此迭代法收斂，否則稱迭代法收斂。1、雅可比（Jacobi）迭代法設(shè)有方程組Ax=b

(56)其展開形式為(57)系數(shù)矩陣A為非奇異陣，且(i=1-n)A可分解為A＝D＋A0（58）其中：改寫線性方程組（57)式，將第i個方程（i=1~n）表示為xi的表達式：（59）改寫后的（57）式的矩陣表達式為：（60）其中很容易看出（56）式和（60）式間系數(shù)矩陣A與及自由項列陣b與之間存在如下關(guān)系（61）用迭代法解（60）式，其迭代公式為（62）初始向量為x0。此法稱雅可比迭代法，稱為雅可比迭代法的迭代矩陣。k為迭代次數(shù)。雅可比迭代法的分量形式為（63）雅可比迭代法分量形式（63）式也可改寫為（64）（64）式更方便于編程求解。雅可比迭代法公式簡單，迭代思路明確。每迭代一次只需計算n個方程的向量乘法，程序編制時需設(shè)二個數(shù)組分別存放xk和xk+1便可實現(xiàn)此迭代求解。2、高斯－賽德爾（Gauss-seidel）迭代法由雅可比迭代法可知，在計算xk+1的過程中，采用的都是上一迭代步的結(jié)果xk?？疾炱溆嬎氵^程，顯然在計算新分量xik+1時，已經(jīng)計算得到了新的分量，。有理由認為新計算出來的分量可能比上次迭代得到的分量有所改善。希望充分利用新計算出來的分量以提高迭代解法的效率，這就是高斯－賽德爾迭代法（簡稱G－S迭代法）對（64）式進行改變可以得到G－S迭代法的分量形式（65）G－S迭代法的分量形式亦可表示為（66）

(65)式也可寫成矩陣形式。方程組的系數(shù)A在（58）式基礎(chǔ)上還可進一步分解，若將A0繼續(xù)分解為一個下三角陣A0L和一個上三角陣A0U，則系數(shù)矩陣的分解則可表達為（67）其中：（68）（65）式可寫成矩陣形式按向量的迭代次數(shù)歸并可得若（D＋）的逆存在，則有高斯－賽德爾迭代的矩陣形式可表達為（69）高斯－賽德爾迭代法每步迭代的計算量與雅可比迭代相當，但在計算機進行計算時，只需存放x一個數(shù)組。用迭代法求解時要注意迭代法的收斂性①。無論是用雅可比迭代法或高斯-賽德爾迭代法都存在解的收斂問題，甚至有的線性方程組，用雅可比迭代法解是收斂的，而用高斯-賽德爾迭代法解卻是發(fā)散的。反之亦然。當線性方程組(56)中的系數(shù)矩陣A(n階矩陣)為嚴格對角優(yōu)勢矩陣，即A的每一行對角元素的絕對值都嚴格大于同行其它元素之和:則可證明上述二種迭代法收斂。定理如果線性方程組的系數(shù)矩陣A為嚴格對角優(yōu)勢矩陣，則對求解線性方程組Ax=b的雅可比迭代法和高斯-賽德爾迭代法均收斂。有限單元法的求解方程Ka=P中，系數(shù)矩陣K具有主元占優(yōu)的特點，但卻不能保證是嚴格對角優(yōu)勢矩陣，因此采用雅可比迭代法時要注意解的收斂問題。高斯-賽德爾迭代法的收斂性要求在下一節(jié)超松弛迭代法時一并討論。2、逐次超松弛迭代法逐次超松弛迭代法(SuccessiveOverRelaxationMerhod,簡稱SOR法)是高斯-賽德爾迭代法的一種加速收斂的方法。是大型稀疏矩陣線性方程組的有效解法之一。首先用另一種變換形式討論一下迭代過程。對于(56)式的線性方程組Ax=b

當系數(shù)矩陣主元aii=1(I=1,2,..,n)時將式中系數(shù)矩陣分解為（70）則可（56）式的等價方程組（71）它的迭代公式為當進行了k次迭代得到xk后，xk一般地與真解x間仍存在差異。如何改進xk得到下一次迭代的結(jié)果xk＋1，可以引入xk的剩余向量rk（73）此時，迭代公式（72）可表示為（74）由此可見應(yīng)用迭代法得到逐次改進的解xk＋1，實質(zhì)上是用k次迭代后的剩余向量rk來改進解的第k次近似rk。因此可以引進一個加速迭代的模式來改進迭代法。令（75）其中ω稱為松弛因子。式（75）是迭代公式（74）的一個改進，可以選擇松弛因子ω加速迭代過程的收斂。式（75）的分量形式為（76）若對上述改進的迭代公式，按高斯－賽德爾迭代法盡量利用最新迭代得到的分量的原則，又可得到新的迭代公式（77）當線性方程組的系數(shù)矩陣A具有非零主元（aii≠0,i=1,2,3,…n）的特點時，可以得到主元為1的方程組形式（78）此時迭代公式（77）可改寫為（79）迭代公式（79）式稱為松弛因子迭代法。當=1，（79）式就是高斯-賽德爾迭代法；當ω<1時（79）式稱為低松弛法；當ω＞1時（79）式稱為超松弛法，即SOR方法。由于加速迭代收斂一般選取ω＞1，因此（79）式一般稱為超松弛迭代法（SOR方法）?？梢宰C明如果線性方程組的系數(shù)矩陣A為對稱正定矩陣。ω的選取0＜ω＜2時，則解方程組的SOR方法一定收斂。由于有限單元法的求解方程其系數(shù)矩陣具有對稱、正定的特點，因此SOR方法是迭代求解的一種常見方法。用超松弛迭代法求解時，應(yīng)選擇超松弛因子，適當?shù)某沙谝蜃訉涌焓諗克俣取３沙谝蜃右话憧扇?.2左右。超松弛代法和高斯-賽德爾迭代要優(yōu)于雅可比迭代。而由于選擇了超松弛因子ω,一般超松弛迭代效率要高于高斯－賽德爾迭代。超松弛因子無法事先確定最優(yōu)值，可在迭代過程中根據(jù)收斂速度進行調(diào)整。用超松弛迭代法求解思路明確，編程簡單，存儲迭代解xk只需一個數(shù)組。但需注意超松弛因子的選擇。在用迭代法求解有限元方程時，仍需按系數(shù)矩陣(剛度矩陣)在計算機內(nèi)的存儲方式，與直接解法中的高斯消去法和三角分解法所討論的相似，考慮系數(shù)矩陣特點，修改(79)式中元素的下標及迭代涉及的元素。如采用雅可比迭代或高斯-賽德爾迭代時，也應(yīng)作此修正。讀者可以進行修改并驗證。附程序#include<iostream>#include<math.h>#include<iomanip>usingnamespacestd;#definekk50//定義最大方程元數(shù)#defineexp1e-5//定義結(jié)束門限值intn,ll,hh,i,j;doubleA[kk][kk],x[kk][kk],b[kk],y[kk],a[kk],z[kk],m,nn,d,e=1,w;voidmain(){cout<<"**********************************************************************"<<endl;cout<<"***本程序可以用雅可比迭代法,塞德爾迭代法,逐次超松弛法求解線性方程組***"<<endl;cout<<"***************************制作人：李小龍*****************************"<<endl;cout<<"***********************說明：方程最多個數(shù)為**************************"<<endl;cout<<"**********************************************************************"<<endl;//*********************************數(shù)據(jù)的輸入********************************bb:cout<<"輸入的方程元數(shù)"<<endl;cin>>n;cout<<"請輸入方程系數(shù)矩陣:"<<"\n";for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>A[i][j];cout<<"請輸入右邊向量:"<<"\n";for(i=0;i<n;i++)cin>>b[i];//*******************************判斷是否對角占優(yōu)*************************for(i=0;i<n;i++){for(j=0;j<n;j++){nn=0;if(i==j){d=fabs(A[i][i]);}elsenn=nn+fabs(A[i][j]);}if(nn>d){cout<<"該方程不對角占優(yōu)，迭代不收斂"<<endl;cout<<"是否繼續(xù)？是（），否（）"<<endl;cin>>hh;if(hh!=1)gotobb;elseexit(1);}}//********************************計算出迭代矩陣*************************for(i=0;i<n;i++){b[i]=b[i]/A[i][i];for(j=0;j<n;j++){if(i==j){x[i][i]=0;}else{x[i][j]=-A[i][j]/A[i][i];}}}//*******************************輸出迭代矩陣*****************************cout<<"計算出迭代矩陣為："<<endl;for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<x[i][j]<<"";cout<<b[i]<<"";cout<<endl;}//****************************迭代方法的選擇*****************************cout<<"請你選擇迭代方法！"<<endl;cout<<endl;cout<<endl;cout<<"選用雅可比迭代法，請輸入（）！"<<endl;cout<<endl;cout<<endl;cout<<"選用塞德爾迭代法，請輸入（）！"<<endl;cout<<endl;cout<<endl;cout<<"選用逐次超松弛法，請輸入（）！"<<endl;cout<<endl;cout<<endl;cin>>ll;//*****************************賦迭代初值***********************************for(i=0;i<n;i++){y[i]=1;z[i]=1;}intf=1;switch(ll){case1:gotocc;break;case2:gotoaa;break;case3:gotodd;}//***************************雅可比迭代法************************************cc:while(e>exp){for(i=0;i<n;i++){z[i]=y[i];nn=0;for(j=0;j<n;j++){nn=nn+x[i][j]*z[j];y[i]=nn+b[i];}e=fabs(z[i]-y[i]);if(i==0){cout<<"第"<<f++<<"次迭代";}cout<<setw(8)<<setprecision(8)<<y[i]<<"";}cout<<endl;}cout<<endl;cout<<endl;cout<<"最后結(jié)果為："<<endl;cout<<endl;for(i=0;i<n;i++){cout<<"X"<<"["<<i<<"]"<<"="<<y[i];cout<<endl;}exit(1);//***********************************塞德爾迭代法********************************aa:while(e>exp){for(i=0;i<n;i++){z[i]=y[i];nn=0;for(j=0;j<n;j++){nn=nn+x[i][j]*y[j];y[i]=nn+b[i];}e=fabs(z[i]-y[i]);if(i==0){cout<<"第"<<f++<<"次迭代";}cout<<setw(8)<<setprecision(8)<<y[i]<<"";}cout<<endl;}cout<<endl;cout<<endl;cout<<"最后結(jié)果為："<<endl;cout<<endl;for(i=0;i<n;i++){cout<<"X"<<"["<<i<<"]"<<"="<<y[i];cout<<endl;}exit(1);//***********