解線性方程組的迭代法.ppt
《解線性方程組的迭代法.ppt》由會員分享,可在線閱讀,更多相關《解線性方程組的迭代法.ppt(39頁珍藏版)》請在裝配圖網(wǎng)上搜索。
解線性方程組的迭代法,直接法得到的解是理論上準確的,但是它們的計算量都是n3數(shù)量級,存儲量為n2量級,這在n比較小的時候還比較合適(n400),但是在很多實際問題中,我們要求解的方程組n很大,而系數(shù)矩陣中含有大量的0元素。對于這類的矩陣,在用直接法時就會耗費大量的時間和存儲單元。因此我們有必要引入一類新的方法:迭代法。,迭代法是一種逐次逼近的方法,其基本思想是:使用某個固定的公式,對解的近似值進行反復校正,從而得到一個近似解序列,使之收斂于方程組的解。,迭代法具有算法簡單、運算速度快的特點。但這種方法獲得的是方程組解的近似值。,對方程組,做等價變換,從某一初值 x(0) 出發(fā),我們可以構造序列,若,同時:,所以,序列收斂,與初值的選取無關,如令A=D-L-U,于是 x=D-1(L+U)x+D-1b,定義5.1:設G為n階方陣,若Gk0,則稱G為收斂矩陣,定理:,即矩陣G為收斂矩陣,當且僅當G的譜半徑1,迭代法的收斂性,定理:迭代法X(m+1)=GX(m)+g 收斂的充分必要條件是迭代矩陣G為收斂矩陣,即G的譜半徑 (G)1。,定理: 迭代法X(m+1)=GX(m)+g 的迭代矩陣G的某種范數(shù) |G|q1,那么: 1)對任意初值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迭代,格式很簡單:,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+) x2i=0; for(j=0;ji;j+) x2i += Aij*x1j for(j=i+1;jn;j+) x2i += Aij*x1j x2i=-(x2i-bi)/Aii 4、輸出解x2,Jacobi迭代算法,迭代矩陣,記,Jacobi迭代法的收斂性,易知,Jacobi迭代有,練習,討論用雅可比(Jacobi)迭代法求解下列線性方程 組的收斂性。若收斂,求其解;若發(fā)散,作適當 變換使其收斂并求解。,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迭代收斂。,此時迭代矩陣為,G的特征值分別為: 0.308507, - 0.154254 + 0.18304 i, -0.154254 - 0.18304 i,收斂條件,迭代格式收斂的充要條件是G的譜半徑1。對于Jacobi迭代, 我們有一些保證收斂的充分條件,定理:若線性方程組AX=b的系數(shù)矩陣A滿足下列條件之一,則Jacobi迭代收斂。, A為行對角占優(yōu)陣, A為列對角占優(yōu)陣, A滿足, 若A對稱正定陣,且2D-A也為對稱正定陣,則Jacobi迭代收斂。,證明:, A為列對角占優(yōu)陣,則AT為行對角占優(yōu)陣,有,證畢,在Jacobi迭代中,使用最新計算出的分量值,GaussSeidel迭代,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+) x2i += Aij*x2j for(j=i+1;jn;j+) x2i += Aij*x2j x2i=-(x2i-bi)/Aii 4、輸出解x2,Gauss-Siedel迭代算法,迭代矩陣,是否是原來的方程的解?,A=(D-L)-U,Gauss-Siedel迭代法的收斂性,收斂條件,迭代格式X=GX+g 對任意的初值X0和向量g,收斂的充要條件是G的譜半徑 (G)1。 下面我們看一些充分條件:,定理:若線性方程組AX=b的系數(shù)矩陣A,, 若A對稱正定陣,則Gauss-Seidel迭代收斂;, 若A對稱正定陣,且2D- A也為對稱正定陣,則Jacobi迭代收斂。,若A為行或列強對角占優(yōu)陣,則Jacobi和Gauss-Seidel迭代都收斂;,證明:,設G的特征多項式為,,則,為對角占優(yōu)陣,則,時,為對角占優(yōu)陣,即,即,證畢,注:二種方法都存在收斂性問題。 有例子表明:Gauss-Seidel法收斂時,Jacobi法可能不收斂;而Jacobi法收斂時, Gauss-Seidel法也可能不收斂。,練習:判定用Jacobi和Gauss-Seidel迭代解方程組:AX=b 時的收斂情況,其中,1、Jacobi迭代,特征值為,2、GaussSeidel迭代,G的譜半徑(G)=1.1181.Jacobi迭代不收斂。,G的譜半徑(G)=0.51.Gauss-Seidel迭代收斂。,分別用Jacobi,Gauss-Seidel迭代法解方程組AX=b,其中,例題,1、預處理,2、格式:Jacobi迭代:,Gauss-Seidel迭代:,取初值,矩陣A按行嚴格對角占優(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、結果,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迭代,練習,用雅可比(Jacobi)迭代法和高斯賽德爾(Gauss-Seidel) 迭代法求解線性方程組 :,可以看作在前一步上加一個修正量。若在修正量前乘以一個 因子w ,則有,對GaussSeidel迭代格式,松弛迭代,寫成分量形式,有,松弛迭代算法,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 += Aij*x2j for(j=i+1;jn;j+) temp += Aij*x2j temp = -(x2i-bi)/Aii x2i = (1-omega)*x2i+omega*temp 4、輸出解x2,迭代矩陣,定理:,松弛迭代收斂,定理:,A對稱正定,則松弛迭代收斂,是否是原來的方程的解?,SOR方法收斂的快慢與松弛因子的選擇有密切關系.但是如何選取最佳松弛因子,即選取=*,使(G)達到最小,是一個尚未很好解決的問題.實際上可采用試算的方法來確定較好的松弛因子.經驗上可取1.41.6.,當松弛因子1時,稱該算法為低松弛因子法;,當松弛因子1時,稱該算法為超松弛因子法;,定理 若SOR方法收斂, 則02.,證 設SOR方法收斂, 則(G)1,所以 |det(G)| =|12 n|1,而 det(G) =det(D - L)-1 (1 - )D+U),=det(E - D - 1L) - 1det(1 - )E+D-1U),=(1-)n,于是 |1 - |1, 或 02,定理 用SOR法解方程組Ax=b,,證 設是G的任一特征值, y是對應的特征向量, 則,(1-)D+Uy= (D - L)y,于是 (1 - )(Dy,y)+(Uy,y)=(Dy,y) - (Ly,y),1)若A是對稱正定矩陣, 則當02時收斂;,2)若矩陣A按行(列)嚴格對角占優(yōu), 則當01時收斂;,由于A=D - L - U是對稱正定的, 所以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,所以,當02時,有,( - +)2 -( - )2= (2 - )(2 - ) = (2 - )(2 - )0,所以|21, 因此(G)1,即S0R方法收斂.,可得 =2/,設是B的任一特征值, y是對應的特征向量, 則,(L+U)y=Dy,于是 (Ly,y)+(Uy,y)=(Dy,y),當A對稱正定時,即2 - 0,而 (2D - A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =+2,即,當A對稱正定時,Jacobi迭代法收斂2D-A正定.,共軛梯度法,給定對稱正定矩陣ARnn,求解方程組AX=b的共軛梯度法如下:,1.選定初值X(0) Rn, 設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) ;,定理:設矩陣ARnn對稱正定,X(k)為用共軛梯度法求解方程組AX=b所產生的迭代序列,并取條件數(shù),那么:,1)用不超過n次迭代即可獲得精確解;,2)對每次迭代結果的誤差估計為:,其中范數(shù)|X|A=(AX , X),- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 線性方程組 迭代法
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學習交流,未經上傳用戶書面授權,請勿作他用。
鏈接地址:http://appdesigncorp.com/p-2866397.html