第二章解線性方程組的迭代法

第二章解線性方程組的迭代法第1頁，共39頁，2023年，2月20日，星期三對(duì)方程組做等價(jià)變換從某一初值x(0)出發(fā)，我們可以構(gòu)造序列若同時(shí)：所以，序列收斂與初值的選取無關(guān)如令A(yù)=D-L-U，于是x=D-1(L+U)x+D-1b,第2頁，共39頁，2023年，2月20日，星期三定義5.1：設(shè)G為n階方陣，若Gk0，則稱G為收斂矩陣定理：即矩陣G為收斂矩陣，當(dāng)且僅當(dāng)G的譜半徑<1由知，若有某種范數(shù)則，迭代收斂第3頁，共39頁，2023年，2月20日，星期三迭代法的收斂性定理：迭代法X(m+1)=GX(m)+g收斂的充分必要條件是迭代矩陣G為收斂矩陣，即G的譜半徑(G)<1。定理：

迭代法X(m+1)=GX(m)+g的迭代矩陣G的某種范數(shù)||G||＝q<1,那么：1）對(duì)任意初值X(0)及g右端向量，迭代格式收斂于X*;2)||X(m)-X*||qm

||X(1)–X(0)||/(1-q);3)||X(m)-X*||q

||X(m)–

X(m-1)||/(

1-q).第4頁，共39頁，2023年，2月20日，星期三Jacobi迭代第5頁，共39頁，2023年，2月20日，星期三格式很簡單：第6頁，共39頁，2023年，2月20日，星期三1、輸入系數(shù)矩陣A和向量b，和誤差控制eps2、x1={0,0,…..,0},x2={1,1,…..,1}//賦初值3、while(||A*x2-b||>eps){x1=x2;for(i=0;i<=n;i++){x2[i]=0;for(j=0;j<i;j++){x2[i]+=A[i][j]*x1[j]}for(j=i+1;j<n;j++){x2[i]+=A[i][j]*x1[j]}x2[i]=-(x2[i]-b[i])/A[i][i]}}4、輸出解x2Jacobi迭代算法第7頁，共39頁，2023年，2月20日，星期三

迭代矩陣記Jacobi迭代法的收斂性第8頁，共39頁，2023年，2月20日，星期三易知，Jacobi迭代有第9頁，共39頁，2023年，2月20日，星期三練習(xí)討論用雅可比(Jacobi)迭代法求解下列線性方程組的收斂性。若收斂，求其解；若發(fā)散，作適當(dāng)變換使其收斂并求解。第10頁，共39頁，2023年，2月20日，星期三G的譜半徑(G)=4.0197>1.Jacobi迭代不收斂。迭代矩陣為G的特征值為：1=4.02408,2=-2.012043.10115i,1=4.02408；2,3=3.69668第11頁，共39頁，2023年，2月20日，星期三將方程組變形，化為：第12頁，共39頁，2023年，2月20日，星期三G的譜半徑(G)=0.308507<1.Jacobi迭代收斂。此時(shí)迭代矩陣為G的特征值分別為：0.308507,-0.154254+0.18304i,-0.154254-0.18304i第13頁，共39頁，2023年，2月20日，星期三收斂條件迭代格式收斂的充要條件是G的譜半徑<1。對(duì)于Jacobi迭代，我們有一些保證收斂的充分條件定理：若線性方程組AX=b的系數(shù)矩陣A滿足下列條件之一，則Jacobi迭代收斂。①A為行對(duì)角占優(yōu)陣②A為列對(duì)角占優(yōu)陣③A滿足④若A對(duì)稱正定陣，且2D-A也為對(duì)稱正定陣，則Jacobi迭代收斂。第14頁，共39頁，2023年，2月20日，星期三證明：②A為列對(duì)角占優(yōu)陣，則AT為行對(duì)角占優(yōu)陣，有＃證畢第15頁，共39頁，2023年，2月20日，星期三在Jacobi迭代中，使用最新計(jì)算出的分量值Gauss－Seidel迭代第16頁，共39頁，2023年，2月20日，星期三1、輸入系數(shù)矩陣A和向量b，和誤差控制eps2、x2={1,1,…..,1}//賦初值3、while(||A*x2-b||>eps){for(i=0;i<n;i++){for(j=0;j<i;j++){x2[i]+=A[i][j]*x2[j]}for(j=i+1;j<n;j++){x2[i]+=A[i][j]*x2[j]}x2[i]=-(x2[i]-b[i])/A[i][i]}}4、輸出解x2Gauss-Siedel迭代算法第17頁，共39頁，2023年，2月20日，星期三

迭代矩陣是否是原來的方程的解？A=(D-L)-UGauss-Siedel迭代法的收斂性第18頁，共39頁，2023年，2月20日，星期三收斂條件迭代格式X=GX+g對(duì)任意的初值X0和向量g，收斂的充要條件是G的譜半徑

(G)<1。下面我們看一些充分條件：定理：若線性方程組AX=b的系數(shù)矩陣A，②若A對(duì)稱正定陣，則Gauss-Seidel迭代收斂；③若A對(duì)稱正定陣，且2D-A也為對(duì)稱正定陣，則Jacobi迭代收斂。①若A為行或列強(qiáng)對(duì)角占優(yōu)陣，則Jacobi和Gauss-Seidel迭代都收斂；第19頁，共39頁，2023年，2月20日，星期三證明：設(shè)G的特征多項(xiàng)式為，則為對(duì)角占優(yōu)陣，則時(shí)為對(duì)角占優(yōu)陣即即＃證畢注：二種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)，Gauss-Seidel法也可能不收斂。第20頁，共39頁，2023年，2月20日，星期三練習(xí)：判定用Jacobi和Gauss-Seidel迭代解方程組：AX=b時(shí)的收斂情況，其中第21頁，共39頁，2023年，2月20日，星期三1、Jacobi迭代特征值為2、Gauss－Seidel迭代G的譜半徑(G)=1.118>1.Jacobi迭代不收斂。G的譜半徑(G)=0.5<1.Gauss-Seidel迭代收斂。第22頁，共39頁，2023年，2月20日，星期三分別用Jacobi，Gauss-Seidel迭代法解方程組AX=b，其中例題第23頁，共39頁，2023年，2月20日，星期三1、預(yù)處理2、格式：Jacobi迭代：Gauss-Seidel迭代：取初值矩陣A按行嚴(yán)格對(duì)角占優(yōu)，都收斂第24頁，共39頁，2023年，2月20日，星期三m=1x1=0.777778x2=0.875000x3=0.888889error=0.888889m=2x1=0.973765x2=0.972222x3=0.975309error=0.195988m=3x1=0.994170x2=0.996721x3=0.997085error=0.024498m=4x1=0.999312x2=0.999271x3=0.999352error=0.005142m=5x1=0.999847x2=0.999914x3=0.999924error=0.000643m=6x1=0.999982x2=0.999981x3=0.999983error=0.000135m=7x1=0.999996x2=0.999998x3=0.999998error=0.000017m=8x1=1.00000x2=1.00000x3=1.00000error=0.000004Jacobi迭代3、結(jié)果第25頁，共39頁，2023年，2月20日，星期三m=1x1=0.777778x2=0.972222x3=0.975309error=0.975309m=2x1=0.994170x2=0.999271x3=0.999352error=0.216392m=3x1=0.999847x2=0.999981x3=0.999983error=0.005677m=4x1=0.999996x2=1.00000x3=1.00000error=0.000149m=5x1=1.00000x2=1.000000x3=1.000000error=0.000004Gauss-Seidel迭代第26頁，共39頁，2023年，2月20日，星期三練習(xí)用雅可比(Jacobi)迭代法和高斯－賽德爾(Gauss-Seidel)迭代法求解線性方程組：第27頁，共39頁，2023年，2月20日，星期三記則可以看作在前一步上加一個(gè)修正量。若在修正量前乘以一個(gè)因子w，則有對(duì)Gauss－Seidel迭代格式松弛迭代第28頁，共39頁，2023年，2月20日，星期三寫成分量形式，有第29頁，共39頁，2023年，2月20日，星期三松弛迭代算法1、輸入系數(shù)矩陣A、向量b和松弛因子omega，和誤差控制eps2、x2={1,1,…..,1}//賦初值3、while(||A*x2-b||>eps){for(i=0;i<n;i++){temp-0for(j=0;j<i;j++){temp+=A[i][j]*x2[j]}for(j=i+1;j<n;j++){temp+=A[i][j]*x2[j]}temp=-(x2[i]-b[i])/A[i][i]x2[i]=(1-omega)*x2[i]+omega*temp}}4、輸出解x2第30頁，共39頁，2023年，2月20日，星期三

迭代矩陣定理：松弛迭代收斂定理：A對(duì)稱正定，則松弛迭代收斂是否是原來的方程的解？第31頁，共39頁，2023年，2月20日，星期三

SOR方法收斂的快慢與松弛因子的選擇有密切關(guān)系.但是如何選取最佳松弛因子,即選取=*,使(G)達(dá)到最小,是一個(gè)尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗(yàn)上可取1.4<<1.6.當(dāng)松弛因子<1時(shí)，稱該算法為低松弛因子法；當(dāng)松弛因子>1時(shí)，稱該算法為超松弛因子法；第32頁，共39頁，2023年，2月20日，星期三

定理若SOR方法收斂,則0<<2.

證設(shè)SOR方法收斂,則(G)<1,所以|det(G)|=|12…n|<1而det(G)=det[(D-

L)-1((1-

)D+U)]

=det[(E-

D-1L)-

1]det[(1-

)E+D-1U)]

=(1-)n于是|1-

|<1,或0<<2第33頁，共39頁，2023年，2月20日，星期三

定理用SOR法解方程組Ax=b，

證設(shè)是G的任一特征值,y是對(duì)應(yīng)的特征向量,則[(1-)D+U]y=(D-

L)y于是(1-

)(Dy,y)+(Uy,y)=[(Dy,y)-

(Ly,y)]1）若A是對(duì)稱正定矩陣,則當(dāng)0<<2時(shí)收斂；2）若矩陣A按行(列)嚴(yán)格對(duì)角占優(yōu),則當(dāng)0<1時(shí)收斂；第34頁，共39頁，2023年，2月20日，星期三由于A=D-

L-

U是對(duì)稱正定的,所以D是正定矩陣,且L=UT.若記(Ly,y)=+i,則有(Dy,y)=>0(Uy,y)=(y,Ly)=(Ly,y)=-i0<(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以第35頁，共39頁，2023年，2月20日，星期三當(dāng)0<<2時(shí),有(-+)2-(-)2=(2-)(2-)=(2-)(2-)<0所以||2<1,因此(G)<1,即S0R方法收斂.可得=2/設(shè)是B的任一特征值,y是對(duì)應(yīng)的特征向量,則