超松弛迭代法解線性方程組

1、設(shè)計題目： 超松弛迭代法解線性方程組 摘要本文是在matlab環(huán)境下熟悉的運用計算機編程語言并結(jié)合超松弛變量超松弛迭代法的理論基礎(chǔ)對方程組求解。 首先，本文以微分方程邊值問題為例，導(dǎo)出了離散化后線性方程組即稀疏線性方程組，轉(zhuǎn)化對稀疏線性方程組求解問題。其次，用超松弛( SOR) 迭代法編寫matlab程序，對產(chǎn)生的稀疏線性方程組進行迭代法求解。然后，分別改變松弛因子和分段數(shù)n的值，分析其收斂性和收斂速度，做出各個方面的分析和比較得到相關(guān)結(jié)論。最后，將超松弛迭代算法在計算機上運用matlab語言實現(xiàn), 得出了一組與精確解較接近的數(shù)值解,并畫圖比較，驗證逐次超松弛( SOR) 迭代法的精確性。關(guān)鍵

2、詞 ： 稀疏線性方程組 逐次超松弛迭代法 松弛因子 matlab編程1、 問題提出考慮兩點邊值問題容易知道它的精確解為為了把微分方程離散，把區(qū)間等分，令，得到差分方程簡化為從而離散后得到的線性方程組的系數(shù)矩陣為對，分別用、和的超松弛迭代法求解線性方程組，要求有4位有效數(shù)字，然后比較與精確解的誤差，探討使超松弛迭代法收斂較快的取值，對結(jié)果進行分析。改變，討論同樣問題。二、超松弛迭代法產(chǎn)生的背景 對從實際問題中得到維數(shù)相當(dāng)大的線性代數(shù)方程組的求解仍然十分困難, 以至使人們不能在允許的時間內(nèi)用直接方法得到解, 因此, 客觀上要求用新的方法來解決大維數(shù)方程組的求解問題。 現(xiàn)有大多數(shù)迭代法不是對各類線性

3、方程組都有收斂性, 在解題時, 要對原方程組矩陣作一根本的變換, 從而可能使條件數(shù)變壞, 也可能破壞了變換前后方程組的等價性, 以及喪失使原方程組的對稱性等。探求新的有效的解題方法依然是迫切的任務(wù)。逐次超松弛(Successive Over Relaxation)迭代法是在高斯-賽德爾(GS)迭代法基礎(chǔ)上為提高收斂速度，采用加權(quán)平均而得到的新算法。 在求解過程中由于線性方程組的系數(shù)矩陣維數(shù)較大, 采用計算機編寫算法來求解, 從而實現(xiàn)了對解析模型的計算機數(shù)值逼近的計算方法#本論文以逐次超松弛迭代法為主要的求解方法。三、超松弛迭代法的理論基礎(chǔ)（1） 逐次超松弛迭代法逐次超松弛(Successive

4、 Over Relaxation)迭代法，簡稱SOR迭代法，它是在GS法基礎(chǔ)上為提高收斂速度，采用加權(quán)平均而得到的新算法，設(shè)解方程(7.1.3)的GS法記為 (1)再由與加權(quán)平均得 這里0稱為松弛參數(shù)，將(1)代入則得 (2)該法稱為SOR迭代法，WTBX0稱為松弛因子，當(dāng)=1時(2)式即為高斯-賽德爾迭代法，簡記GS法，將(2）寫成矩陣形式，則得 即于是得SOR迭代的矩陣表示 (3)其中 (4) 分解后，有.（2） 逐次超松弛迭代法的收斂性根據(jù)迭代法收斂性定理，SOR法收斂的充分必要條件為，收斂的充分條件為，但要計算比較復(fù)雜，通常都不用此結(jié)論，而直接根據(jù)方程組的系數(shù)矩陣A判斷SOR迭代收斂性

5、，下面先給出收斂必要條件. 定理1設(shè)，則解方程的SOR迭代法收斂的必要條件是02. 該定理為SOR迭代法收斂的必要條件。 定理 2若對稱正定，且02，則解Ax=b的SOR迭代法對迭代收斂.對于SOR迭代法，松弛因子的選擇對收斂速度影響較大，關(guān)于最優(yōu)松弛因子研究較為復(fù)雜，且已有不少理論結(jié)果.下面只給出一種簡單且便于使用的結(jié)論。 定理3設(shè)為對稱正定的三對角矩陣，是解方程的J法迭代矩陣，若，記，則SOR法的最優(yōu)松弛因子為(5)且(6)根據(jù)定理，,如圖1所示.由(6)可知，當(dāng)=1，時，收斂速度為.說明GS法比J法快一倍.圖1定理4 設(shè),如果：（1） A為嚴(yán)格對角占優(yōu)矩陣；（2）0=1.則解的SOR迭代

6、法收斂。4、 實驗內(nèi)容1.自定義函數(shù) sor(A, b, nm, e, w)，以實現(xiàn)SOR方法求解線性方程組AX=B，其中A系數(shù)矩陣；b常數(shù)列向量；w松弛因子；nm迭代的最大次數(shù)e達到的精度上限由離散后的差分方程：得到的線性方程組的系數(shù)矩陣為 常數(shù)列向量b=其中，則有。A為（aij）200*200型矩陣，b為（bij）200*1型矩陣。在本次試驗中，由于所提供數(shù)據(jù)較小，當(dāng)最大迭代次數(shù)nm較小時，在nm迭代次數(shù)范圍內(nèi)，不能判斷該超松弛迭代法是否收斂，此次取nm=30000。迭代精度e也應(yīng)取較小值才能使誤差更小，此次取e=0.00001。由定理1可知，本次試驗中，的取值范圍為：02才能保證迭代法收

7、斂。取，為的矩陣。用SOR迭代公式得取不同值時，對應(yīng)的迭代次數(shù)、與精確解的誤差如下表1。表1 取不同值時對應(yīng)的迭代次數(shù)與誤差松弛因子 區(qū)間等分?jǐn)?shù)=200迭代次數(shù)誤差 0.5 18111136931.548910.10531.639450.07311.730170.04601.820870.02611.911130.0236滿足誤差的迭代次數(shù) 圖1 計算值與精確值圖形比較 從本組的實驗中，可以看出w 值的取定十分重要，它對求解的迭代次數(shù)影響十分明顯。一個不好的w 值甚至?xí)?dǎo)致迭代超過10000次仍未能求得需要精度的值。由表1可得，當(dāng)=1.9時SOR迭代法收斂速度最快，誤

8、差最小。取=1.9，nm=30000,等各個因子相同時，當(dāng)分段點n取不同值時，對應(yīng)的迭代次數(shù)、與精確解的誤差如下表2。區(qū)間等分?jǐn)?shù)n松弛因子 =1.9迭代次數(shù)誤差1204160.24771504160.24772004160.24772504160.2477滿足誤差的迭代次數(shù)從本組的實驗中，當(dāng)其他各個因子取適當(dāng)值時，改變分段數(shù)時，對結(jié)果沒有影響。 圖3 精確圖形由圖3可得，當(dāng)各個參數(shù)取值適當(dāng)時，用SOR迭代法所得線性方程組的解與精確解誤差極小，從而驗證了SOR迭代法的準(zhǔn)確性。五、結(jié)論1. 通過本次的課程設(shè)計，可知逐次超松弛迭代法與Jacobi 迭代法, Seidel 迭代法相比, 收斂速度較快。

9、由逐次超松弛迭代法求出的方程組的數(shù)值解與該方程組的精確解十分接近, 離散化后線性方程組的逐次超松弛迭代法的精確性較高。逐次超松弛迭代法可以廣泛地應(yīng)用于實際。該算法不僅可以用來求解高階稀疏線性方程組, 還可以用來求解熱傳導(dǎo)問題這樣可以大大減少計算量和計算機的內(nèi)存儲量, 從而提高計算效率。本次的課程設(shè)計，我們運用了matlab語言來實現(xiàn)相關(guān)的計算，這樣不僅對逐次超松弛迭代法有了更深層的了解掌握，還提高了對matlab的操作技術(shù)，深刻體會到了MATLAB功能的強大之處。通過本次試驗，我掌握了用Jacobi、Gauss-Seidel、SOR迭代法求解線性方程組的方法；六、參考文獻1 李慶揚，王能超，易

10、大義.數(shù)值分析M, 清華大學(xué)出版社，2008.2 劉衛(wèi)國. MATLAB程序設(shè)計與應(yīng)用M，高等教育出版社，2008.3 王詩然. 稀疏線性方程組求解的逐次超松弛迭代法J，沈陽師范大學(xué)學(xué)報,4,407-409,2006.4 李建宇，黎燕. 牛頓一SOR迭代方法中最佳松弛因子的算法J，四川大學(xué)學(xué)報，4,381-382,1995.5 蔡大用.數(shù)值分析與實驗學(xué)習(xí)指導(dǎo)M，清華大學(xué)出版社，2001.附錄1.超松弛迭代法function n,x=cscdd(A,b,X,nm,e,w)n=1;D=diag(diag(A); %令A(yù)=D-L-U,計算矩陣DL=tril(-A)+D; %令A(yù)=D-L-U,計算矩陣

11、LU=triu(-A)+D; %令A(yù)=D-L-U,計算矩陣UM=inv(D-w*L)*(1-w)*D+w*U); %計算迭代矩陣g=w*inv(D-w*L)*b; %計算迭代格式中的常數(shù)項%下面是迭代過程while n=nm x=M*X+g; %用迭代格式進行迭代 r=norm(x-X,inf); if re return; end X=x; n=n+1; enddisp(在最大迭代次數(shù)內(nèi)不收斂!)2.輸入初始值并調(diào)用SOR迭代法n0=200;m=1;a=0.4;h=1/n0;A=zeros(n0,n0);for i=1:n0 A(i,i)=-(2*m+h);endfor i=2:n0-1 A(i,i-1)=m; A(i,i+1)=m+h;endA(1,2)=m+h;A(n0,n0-1)=m;for i=1:n0-1 b(i,1)=a*h2;endb(n0,1)=a*h2-(m+h);for i=1:n0 xi=i/n0; y0(i,1)=(1-0.4)/(1-exp(-1)*(1-exp(-xi)+0.4*xi; x0(i,1)=1; endn1,x1=cscdd(A,b,x0,30000,0.00001,0.5);n1u1=norm(x1-y0,2)n2,x2=cscdd(A,b,x0,30000,0.00001,1.0);n2u2=norm(x2-y0,2)n3,x