解線性方程組的迭代法.ppt

《解線性方程組的迭代法.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《解線性方程組的迭代法.ppt（39頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

解線性方程組的迭代法,直接法得到的解是理論上準(zhǔn)確的，但是它們的計(jì)算量都是n3數(shù)量級(jí)，存儲(chǔ)量為n2量級(jí)，這在n比較小的時(shí)候還比較合適（n400），但是在很多實(shí)際問題中，我們要求解的方程組n很大，而系數(shù)矩陣中含有大量的0元素。對(duì)于這類的矩陣，在用直接法時(shí)就會(huì)耗費(fèi)大量的時(shí)間和存儲(chǔ)單元。因此我們有必要引入一類新的方法：迭代法。,迭代法是一種逐次逼近的方法，其基本思想是：使用某個(gè)固定的公式，對(duì)解的近似值進(jìn)行反復(fù)校正，從而得到一個(gè)近似解序列，使之收斂于方程組的解。,迭代法具有算法簡(jiǎn)單、運(yùn)算速度快的特點(diǎn)。但這種方法獲得的是方程組解的近似值。,對(duì)方程組,做等價(jià)變換,從某一初值 x(0) 出發(fā)，我們可以構(gòu)造序列,若,同時(shí)：,所以，序列收斂,與初值的選取無關(guān),如令A(yù)=D-L-U，于是 x=D-1(L+U)x+D-1b,,定義5.1：設(shè)G為n階方陣，若Gk?0，則稱G為收斂矩陣,定理：,即矩陣G為收斂矩陣，當(dāng)且僅當(dāng)G的譜半徑1,迭代法的收斂性,定理：迭代法X(m+1)=GX(m)+g 收斂的充分必要條件是迭代矩陣G為收斂矩陣，即G的譜半徑 ?(G)1。,定理： 迭代法X(m+1)=GX(m)+g 的迭代矩陣G的某種范數(shù) ||G||＝q1,那么： 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).,Jacobi迭代,格式很簡(jiǎn)單：,1、輸入系數(shù)矩陣A和向量b，和誤差控制eps 2、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;ji;j++) { x2[i] += A[i][j]*x1[j] } for(j=i+1;jn;j++) { x2[i] += A[i][j]*x1[j] } x2[i]=-(x2[i]-b[i])/A[i][i] } } 4、輸出解x2,Jacobi迭代算法,迭代矩陣,記,Jacobi迭代法的收斂性,易知，Jacobi迭代有,練習(xí),討論用雅可比(Jacobi)迭代法求解下列線性方程 組的收斂性。若收斂，求其解；若發(fā)散，作適當(dāng) 變換使其收斂并求解。,G的譜半徑?(G)=4.01971. Jacobi迭代不收斂。,迭代矩陣為,G的特征值為：?1=4.02408, ?2=-2.01204 ? 3.10115 i,,? ?1?=4.02408； ? ?2,3?=3.69668,將方程組變形，化為：,G的譜半徑?(G)= 0.308507 1.Jacobi迭代收斂。,此時(shí)迭代矩陣為,G的特征值分別為： 0.308507, - 0.154254 + 0.18304 i, -0.154254 - 0.18304 i,收斂條件,迭代格式收斂的充要條件是G的譜半徑1。對(duì)于Jacobi迭代， 我們有一些保證收斂的充分條件,定理：若線性方程組AX=b的系數(shù)矩陣A滿足下列條件之一，則Jacobi迭代收斂。,① A為行對(duì)角占優(yōu)陣,② A為列對(duì)角占優(yōu)陣,③ A滿足,④ 若A對(duì)稱正定陣，且2D-A也為對(duì)稱正定陣，則Jacobi迭代收斂。,證明：,② A為列對(duì)角占優(yōu)陣，則AT為行對(duì)角占優(yōu)陣，有,＃證畢,,,在Jacobi迭代中，使用最新計(jì)算出的分量值,Gauss－Seidel迭代,,1、輸入系數(shù)矩陣A和向量b，和誤差控制eps 2、x2={1,1,…,1} //賦初值 3、while( ||A*x2-b||eps) { for(i=0;in;i++) { for(j=0;ji;j++) { x2[i] += A[i][j]*x2[j] } for(j=i+1;jn;j++) { x2[i] += A[i][j]*x2[j] } x2[i]=-(x2[i]-b[i])/A[i][i] } } 4、輸出解x2,Gauss-Siedel迭代算法,迭代矩陣,是否是原來的方程的解？,A=(D-L)-U,Gauss-Siedel迭代法的收斂性,收斂條件,迭代格式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迭代都收斂；,證明：,設(shè)G的特征多項(xiàng)式為,，則,為對(duì)角占優(yōu)陣，則,時(shí),為對(duì)角占優(yōu)陣,即,即,＃證畢,注：二種方法都存在收斂性問題。 有例子表明：Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)， Gauss-Seidel法也可能不收斂。,練習(xí)：判定用Jacobi和Gauss-Seidel迭代解方程組：AX=b 時(shí)的收斂情況，其中,1、Jacobi迭代,特征值為,2、Gauss－Seidel迭代,G的譜半徑?(G)=1.1181.Jacobi迭代不收斂。,G的譜半徑?(G)=0.51.Gauss-Seidel迭代收斂。,分別用Jacobi，Gauss-Seidel迭代法解方程組AX=b，其中,例題,1、預(yù)處理,2、格式：Jacobi迭代：,Gauss-Seidel迭代：,取初值,矩陣A按行嚴(yán)格對(duì)角占優(yōu)，都收斂,m=1 x1=0.777778 x2=0.875000 x3=0.888889 error=0.888889 m=2 x1=0.973765 x2=0.972222 x3=0.975309 error=0.195988 m=3 x1=0.994170 x2=0.996721 x3=0.997085 error=0.024498 m=4 x1=0.999312 x2=0.999271 x3=0.999352 error=0.005142 m=5 x1=0.999847 x2=0.999914 x3=0.999924 error=0.000643 m=6 x1=0.999982 x2=0.999981 x3=0.999983 error=0.000135 m=7 x1=0.999996 x2=0.999998 x3=0.999998 error=0.000017 m=8 x1=1.00000 x2=1.00000 x3=1.00000 error=0.000004,Jacobi迭代,3、結(jié)果,m=1 x1=0.777778 x2=0.972222 x3=0.975309 error=0.975309 m=2 x1=0.994170 x2=0.999271 x3=0.999352 error=0.216392 m=3 x1=0.999847 x2=0.999981 x3=0.999983 error=0.005677 m=4 x1=0.999996 x2=1.00000 x3=1.00000 error=0.000149 m=5 x1=1.00000 x2=1.000000 x3=1.000000 error=0.000004,Gauss-Seidel迭代,練習(xí),用雅可比(Jacobi)迭代法和高斯－賽德爾(Gauss-Seidel) 迭代法求解線性方程組 ：,可以看作在前一步上加一個(gè)修正量。若在修正量前乘以一個(gè) 因子w ，則有,對(duì)Gauss－Seidel迭代格式,松弛迭代,寫成分量形式，有,松弛迭代算法,1、輸入系數(shù)矩陣A、向量b和松弛因子omega，和誤差控制eps 2、x2={1,1,…,1} //賦初值 3、while( ||A*x2-b||eps) { for(i=0;in;i++) { temp-0 for(j=0;ji;j++) { temp += A[i][j]*x2[j] } for(j=i+1;jn;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,迭代矩陣,定理：,松弛迭代收斂,定理：,A對(duì)稱正定，則松弛迭代收斂,是否是原來的方程的解？,SOR方法收斂的快慢與松弛因子?的選擇有密切關(guān)系.但是如何選取最佳松弛因子,即選取?=?*,使?(G?)達(dá)到最小,是一個(gè)尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗(yàn)上可取1.4?1.6.,當(dāng)松弛因子?1時(shí)，稱該算法為低松弛因子法；,當(dāng)松弛因子?1時(shí)，稱該算法為超松弛因子法；,定理 若SOR方法收斂, 則0?2.,證 設(shè)SOR方法收斂, 則?(G?)1,所以 |det(G?)| =|?1?2… ?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,定理 用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í)收斂；,由于A=D - L - U是對(duì)稱正定的, 所以D是正定矩陣, 且L=UT. 若記(Ly,y)=?+i?, 則有,(Dy,y)=?0,(Uy,y)=(y,Ly)=(Ly,y),=? - i?,0(Ay,y)=(Dy,y) -(Ly,y) -(Uy,y) =? - 2?,所以,當(dāng)0?2時(shí),有,(? - ??+??)2 -(? - ??)2= (2?? - ??)(2? - ??) = ?? (2? - ?)(2 - ?)0,所以|?|21, 因此?(G?)1,即S0R方法收斂.,可得 ?=2?/?,設(shè)?是B的任一特征值, y是對(duì)應(yīng)的特征向量, 則,(L+U)y=?Dy,于是 (Ly,y)+(Uy,y)=?(Dy,y),當(dāng)A對(duì)稱正定時(shí),即2? - ?0,而 ((2D - A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =?+2?,即,當(dāng)A對(duì)稱正定時(shí),Jacobi迭代法收斂?2D-A正定.,共軛梯度法,給定對(duì)稱正定矩陣A?Rnn，求解方程組AX=b的共軛梯度法如下：,1.選定初值X(0) ?Rn, 設(shè)r(0)=d(0)=b-AX(0);,2. r(k+1)= r(k) - ?(k) A d(k); 其中,3. d(k+1)= r(k+1) +? (k) d(k); 其中,4. X(k+1)= X(k)+ ? (k) d(k) ;,定理：設(shè)矩陣A?Rnn對(duì)稱正定，{X(k)}為用共軛梯度法求解方程組AX=b所產(chǎn)生的迭代序列，并取條件數(shù),那么：,1)用不超過n次迭代即可獲得精確解；,2)對(duì)每次迭代結(jié)果的誤差估計(jì)為：,其中范數(shù)||X||A=(AX , X),