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

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

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

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

當(dāng)系數(shù)矩陣主元aii=1(I=1,2,..,n)時(shí)將式中系數(shù)矩陣分解為（70）則可（56）式的等價(jià)方程組（71）它的迭代公式為當(dāng)進(jìn)行了k次迭代得到xk后，xk一般地與真解x間仍存在差異。如何改進(jìn)xk得到下一次迭代的結(jié)果xk＋1，可以引入xk的剩余向量rk（73）此時(shí)，迭代公式（72）可表示為（74）由此可見應(yīng)用迭代法得到逐次改進(jìn)的解xk＋1，實(shí)質(zhì)上是用k次迭代后的剩余向量rk來改進(jìn)解的第k次近似rk。因此可以引進(jìn)一個(gè)加速迭代的模式來改進(jìn)迭代法。令（75）其中ω稱為松弛因子。式（75）是迭代公式（74）的一個(gè)改進(jìn)，可以選擇松弛因子ω加速迭代過程的收斂。式（75）的分量形式為（76）若對(duì)上述改進(jìn)的迭代公式，按高斯－賽德爾迭代法盡量利用最新迭代得到的分量的原則，又可得到新的迭代公式（77）當(dāng)線性方程組的系數(shù)矩陣A具有非零主元（aii≠0,i=1,2,3,…n）的特點(diǎn)時(shí)，可以得到主元為1的方程組形式（78）此時(shí)迭代公式（77）可改寫為（79）迭代公式（79）式稱為松弛因子迭代法。當(dāng)=1，（79）式就是高斯-賽德爾迭代法；當(dāng)ω<1時(shí)（79）式稱為低松弛法；當(dāng)ω＞1時(shí)（79）式稱為超松弛法，即SOR方法。由于加速迭代收斂一般選取ω＞1，因此（79）式一般稱為超松弛迭代法（SOR方法）。可以證明如果線性方程組的系數(shù)矩陣A為對(duì)稱正定矩陣。ω的選取0＜ω＜2時(shí)，則解方程組的SOR方法一定收斂。由于有限單元法的求解方程其系數(shù)矩陣具有對(duì)稱、正定的特點(diǎn)，因此SOR方法是迭代求解的一種常見方法。用超松弛迭代法求解時(shí)，應(yīng)選擇超松弛因子，適當(dāng)?shù)某沙谝蜃訉?huì)加快收斂速度。超松弛因子一般可取1.2左右。超松弛代法和高斯-賽德爾迭代要優(yōu)于雅可比迭代。而由于選擇了超松弛因子ω,一般超松弛迭代效率要高于高斯－賽德爾迭代。超松弛因子無法事先確定最優(yōu)值，可在迭代過程中根據(jù)收斂速度進(jìn)行調(diào)整。用超松弛迭代法求解思路明確，編程簡(jiǎn)單，存儲(chǔ)迭代解xk只需一個(gè)數(shù)組。但需注意超松弛因子的選擇。在用迭代法求解有限元方程時(shí)，仍需按系數(shù)矩陣(剛度矩陣)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式，與直接解法中的高斯消去法和三角分解法所討論的相似，考慮系數(shù)矩陣特點(diǎn)，修改(79)式中元素的下標(biāo)及迭代涉及的元素。如采用雅可比迭代或高斯-賽德爾迭代時(shí)，也應(yīng)作此修正。讀者可以進(jìn)行修改并驗(yàn)證。附程序#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<<"***********************說明：方程最多個(gè)數(shù)為**************************"<<endl;cout<<"**********************************************************************"<<endl;//*********************************數(shù)據(jù)的輸入********************************bb:cout<<"輸入的方程元數(shù)"<<endl;cin>>n;cout<<"請(qǐng)輸入方程系數(shù)矩陣:"<<"\n";for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>A[i][j];cout<<"請(qǐng)輸入右邊向量:"<<"\n";for(i=0;i<n;i++)cin>>b[i];//*******************************判斷是否對(duì)角占優(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<<"該方程不對(duì)角占優(yōu)，迭代不收斂"<<endl;cout<<"是否繼續(xù)？是（），否（）"<<endl;cin>>hh;if(hh!=1)gotobb;elseexit(1);}}//********************************計(jì)算出迭代矩陣*************************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<<"計(jì)算出迭代矩陣為："<<endl;for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<x[i][j]<<"";cout<<b[i]<<"";cout<<endl;}//****************************迭代方法的選擇*****************************cout<<"請(qǐng)你選擇迭代方法！"<<endl;cout<<endl;cout<<endl;cout<<"選用雅可比迭代法，請(qǐng)輸入（）！"<<endl;cout<<endl;cout<<endl;cout<<"選用塞德爾迭代法，請(qǐng)輸入（）！"<<endl;cout<<endl;cout<<endl;cout<<"選用逐次超松弛法，請(qǐng)輸入（）！"<<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);//***********