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

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

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

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

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

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

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

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

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

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

11、LU=triu(-A)+D; %令A=D-L-U,計算矩陣UM=inv(D-w*L)*(1-w)*D+w*U); %計算迭代矩陣g=w*inv(D-w*L)*b; %計算迭代格式中的常數項%下面是迭代過程while n=nm x=M*X+g; %用迭代格式進行迭代 r=norm(x-X,inf); if re return; end X=x; n=n+1; enddisp(在最大迭代次數內不收斂!)2.輸入初始值并調用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