線性方程組的迭代解法及收斂分析

1、河南科技學院 2015屆本科畢業(yè)論文論文題目：線性方程組的三種迭代解法 及收斂分析 學生姓名： 韋成州 所在院系： 數學科學學院 所學專業(yè)： 信息與計算科學 導師姓名： 李巧萍 完成時間： 2015年5月20日 線性方程組的三種迭代解法及收斂分析摘 要對于線性方程組的迭代解法，本文重點討論雅可比迭代法，高斯塞德爾迭代法和超松弛迭代法三種迭代解法。主要討論內容有：首先，寫出三種迭代解法的基本思想，基本算法及收斂條件；其次，針對這三種迭代解法進行舉例分析，通過MATLAB程序，求得三種迭代法各自的迭代次數、每次迭代的結果及誤差；最后，在滿足設定精度的情況下，對每個迭代方法所用的迭代次數進行通過分析

2、比較，得出了在選擇適當的松弛因子后，三種迭代法的收斂速度：超松弛迭代法高斯塞德爾迭代法雅可比迭代法，對于方程組，迭代法的收斂性只與系數矩陣有關，而與右端項無關。同時，本文又對算法設計，收斂速度的判定等問題提出了改進意見。關鍵詞： MATLAB,數學模型,迭代解法,收斂,線性方程組Three kinds of solutions of systems of linear equations iterative method and convergence analysisAbstractFor iterative solution of linear equations, this articl

3、e focuses on the Jacobi iteration method, gauss seidel iteration method and overrelaxation iteration method of three kinds of iterative method.Main discussion: first of all, write down three iterative method, the basic idea of the basic algorithm and convergence condition;Secondly, in view of the th

4、ree kinds of iterative solution methods for analysis, through the MATLAB program, get three iterative method respective number of iterations, the results of each iteration and error;Finally, in the case of meet the setting precision, for each iteration method to carry through analysis and comparison

5、, the number of iterations used in selecting the appropriate relaxation factor is obtained, the convergence rate of the three types of iterative method: overrelaxation iteration method, gauss seidel iteration method, Jacobi iteration method for the system of equations, the convergence of iterative m

6、ethod is only related to the coefficient matrix, and has nothing to do with the right items.And at the same time, this paper, the algorithm design, and the convergence rate of decision problems, such as improvement opinions are put forward.Keywords：MATLAB, Mathematical model, Iterative method, Conve

7、rgence System of linear equations目 錄1引言12迭代法的基本思想13三種迭代法的思想，算法及收斂條件1 3.1 雅可比迭代法13.1.1 雅可比迭代法的思想與算法13.1.2 雅格比迭代法的收斂條件23.2 高斯塞德爾迭代法23.2.1 高斯塞德爾迭代法的思想和算法23.2.2 高斯塞德爾迭代法的收斂條件33.3超松弛迭代法33.3.1 松弛法思想和算法33.3.2 超松弛迭代法的收斂條件44數學模型44.1雅可比迭代法求解44.2高斯賽德爾方法求解74.3超松弛迭代法求解95小結13致謝15參考文獻 151引言在實際生活中，存在著大量求解線性方程組的問題。這

8、些方程組具有數據量大，系數矩陣稀疏，在一定精度保證下，只需要求解近似解等特點。線性方程組的迭代解法特別適合于這類方程組的求解，它具有程序設計簡單，需要計算機的貯存單元少等特點，但也有收斂性與收斂速度問題。因此，研究線性方程組的迭代解法及收斂分析對于解決實際問題具有非常重要的作用。2迭代法的基本思想將方程組寫成等價的形式，定一個初值向量,可以得到迭代公式:這樣構造一個向量序列，使其極限向量是方程組的精確解。3三種迭代法的思想，算法及收斂條件3.1 雅可比迭代法 雅可比迭代法的思想與算法1基本思想：如果方程組的系數矩陣，滿足條件。把分解成。其中，為主對角線為零的下三角矩陣，為主對角線為零的上三角矩

9、陣，于是方程組等價于整理得：由此可得迭代公式：其中任選，由上式所表示的迭代法就是雅可比迭代法，其中 就是該迭代法的迭代矩陣，其分量式為：2基本算法：步一.取初始向量,精度；步二.計算初始誤差，并進入循環(huán)，運算迭代公式步三.如果誤差小于精度，則輸出，否則，轉步二3.1.2 雅格比迭代法的收斂條件1.雅可比迭代法收斂的充要條件是該迭代法的迭代矩陣的譜半徑小于1。2.若系數矩陣為對稱正定矩陣，且對角元則有雅可比迭代法收斂的充要條件是及都是正定矩陣。3.若方程組的系數矩陣是主對角線按行(或按列)嚴格占優(yōu)矩陣,即 則有雅可比迭代法收斂。3.2 高斯塞德爾迭代法3.2.1 高斯塞德爾迭代法的思想和算法1基

10、本思想：高斯塞德爾迭代法是在雅可比迭代法的基礎上得到的迭代算法,主要不同是在計算時,前面的個值已經算出,用這些新值代替上次迭代的舊值,用矩陣表示為兩邊左乘,整理得 于是可得迭代公式為:其中迭代矩陣為: ，其分量式為：2基本算法：步一.取初始向量;精度；步二.計算初始誤差，并進入循環(huán)，運算迭代公式步三.如果誤差小于精度，則輸出，否則，轉步二3.2.2 高斯塞德爾迭代法的收斂條件1高斯塞德爾迭代法收斂的充要條件是該迭代法的迭代矩陣的譜半徑小于12 若系數矩陣為對稱正定矩陣，且對角元則有高斯塞德爾迭代法收斂的充要條件是是正定矩陣。3若方程組的系數矩陣是主對角線按行(或按列)嚴格占優(yōu)矩陣,即 則有高斯

11、塞德爾迭代法收斂。3.3超松弛迭代法3.3.1 松弛法思想和算法1基本思想：超松弛迭代法一種加速收斂的新的迭代算法,與高斯塞德爾迭代法相比,它明顯地提高了收斂的速度，具體來說就是采用加權平均的算法，在計算時，用高塞德爾算法得到的與前一步迭代中得到的加權平均，即，其矩陣形式為:其分量形式為：其中w為松弛因子2基本算法:步一.輸入初始向量;步二.重復執(zhí)行1) 用迭代格式:塞德爾迭代，加權平均: 2) 計算誤差3) 直到誤差小于所給的精度步三.輸出迭代次數 超松弛迭代法的收斂條件1超松弛迭代法收斂的充分必要條件是該迭代法的迭代矩陣的譜半徑小于12超松弛迭代法收斂的必要條件是3設系數矩陣A對稱正定,且

12、,則解線性方程組的超松弛迭代法收斂。4數學模型4.1雅可比迭代法求解先將轉化為等價方程組:由此建立等價的迭代格式:MATLAB代碼為：function x,a,count,e=jacobi(A,b,jd,x)%A表示系數矩陣,b表示常數項矩陣,jd表示精度(本程序選擇精度為1e-6),x表示任選的初始向量(本程序選零向量)xx=inv(A)*b; %求出真實解er=sqrt(abs(sum(x-xx);%求出誤差(二范數)D=diag(10 9 7 12 15);%求對角矩陣Ddd=inv(D);%求對角矩陣的逆矩陣L=tril(A,-1);%求下三角矩陣U=triu(A,1);%求上三角矩陣

13、M=-dd*(L+U);%求迭代矩陣g=dd*b;j=1;count=0;k=1;er=sqrt(sum(x-xx).*(x-xx);%求誤差while er>=jd %迭代求解 x=M*x+g; for i=1:5 a(j)=x(i);%把每次迭代結果(x的五個分量)保存 j=j+1; end er=sqrt(sum(x-xx).*(x-xx); e(k)=er;%把每次迭代的誤差向量保存 k=k+1; count=count+1;%記錄迭代次數 end在命令窗口中輸入：A=10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -

14、1 15;b=12 -27 14 -17 12'jd=1e-6; x=0 0 0 0 0' x,a,count,e=jacobi(A,b,jd,x),可以得到:1.近似解:x=1.0000 -2.0000 3.0000 -2.0000 1.00002.迭代次數count=753.每次迭代結果及誤差見表4.1表4.1 雅可比迭代法中每次迭代結果及誤差Tab4.1 The each iteration results and errors of jacobi iteration method次數x1(k)x2(k)x3(k)x4(k)x5(k)誤差er11.200003.00002

15、.00001.41670.80001.555721.20502.32962.40711.65000.45220.961631.26562.34902.35311.89370.70510.842141.25042.22332.61811.87110.65080.630151.19972.21532.59191.95900.76990.554561.18292.15342.73021.93120.77040.432771.14052.14212.73231.97190.83520.373581.12522.10652.80981.95830.84680.297491.09752.09542.821

16、71.97880.88470.2533101.08502.07382.86711.97350.89690.2041111.06732.06452.88021.98430.92000.1723121.05772.05092.90771.98280.93030.1400131.04632.04372.91911.98870.94480.1174141.03922.03502.93631.98860.95270.0959151.03182.02972.94511.99200.96200.0801161.02672.02412.95611.99240.96780.0657171.02182.02032

17、.96271.99440.97390.0547181.01822.01652.96991.99490.97810.0449191.01492.01382.97461.99610.98210.0373201.01242.01132.97931.99660.98510.03070由表4.1可知：隨著迭代次數的增多，x的各個分量越來越接近真實解，并且誤差也在逐漸減小，可以知道，此時雅可比迭代法收斂。 4.2高斯賽德爾方法求解如下:由高斯塞德爾迭代法與雅可比迭代法的關系,易得高斯塞德爾的迭代公式:MATLAB代碼為:function x,a,count,e=gsshiyan1(A,b,jd,x)%A表

18、示系數矩陣,b表示常數項矩陣,jd表示精度(本程序選擇精度為1e-6）,x表示任選的初始向量(本程序選零向量)xx=inv(A)*b; %求出真實解er=sqrt(sum(x-xx).*(x-xx);%求出誤差(二范數)count=0;k=1;j=1;while er>=jd %迭代求解for i=1:5x(i)=-1/A(i,i).*(A(i,1:i-1)*x(1:i-1)+A(i,i+1:5)*x(i+1:5)-b(i);a(j)=x(i); %把每次迭代結果(x的五個分量)保存j=j+1;ender=sqrt(sum(x-xx).*(x-xx);e(k)=er;%把每次迭代的誤差向

19、量保存k=k+1;count=count+1; %記錄迭代次數 end在命令窗口中輸入：A=10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -1 15;b=12 -27 14 -17 12'jd=1e-6; x=0 0 0 0 0' x=gs(A,b,jd,x),可以得到:1.近似解:x=1.0000 -2.0000 3.0000 -2.0000 1.00002.迭代次數count=443.每次迭代結果及誤差見表4.2表4.2 高斯塞德爾迭代法中每次迭代結果及誤差Tab 4.2 The each iteration

20、results and errors of gauss seidel iteration method次數x1(k)x2(k)x3(k)x4(k)x5(k)誤差er11.2000-3.13331.2095-1.49680.15672.344021.6578-2.66491.8991-1.84870.33471.597631.5074-2.43412.2530-1.92320.53401.107741.3562-2.29502.4903-1.95130.67940.760851.2451-2.20162.6513-1.9670.78030.521261.1680-2.13792.7613-1.9

21、7760.84960.356871.1150-2.0942.8366-1.98470.89700.244381.0787-2.06462.8882-1.98950.92950.167091.0539-2.04422.9234-1.99280.95170.1145101.0369-2.03032.9476-1.99510.96700.0784111.0253-2.02072.9641-1.99660.97740.0536121.0173-2.01422.9754-1.99770.98450.0367131.0118-2.00972.9832-1.99840.98940.0251141.0081-

22、2.00672.9885-1.99890.99270.0172151.0055-2.00462.9921-1.99930.99500.0118161.0038-2.00312.9946-1.99950.99660.0081171.0026-2.00212.9963-1.99970.99770.0055181.0018-2.00152.9975-1.99980.99840.0038191.0012-2.00102.9983-1.99980.99890.0026201.0008-2.00072.9988-1.99990.99930.0018由表4.2可知：隨著迭代次數的增多，x的各個分量越來越接近

23、真實解，并且誤差也在逐漸減小，可以知道，此時高斯塞德爾迭代法收斂。4.3超松弛迭代法求解超松弛迭代法是在雅可比迭代法與高斯塞德爾迭代法基礎上得到的加速收斂迭代法,迭代公式為:超松弛迭代法的收斂性與松弛因子有關, 不同的松弛因子使得超松弛迭代法的迭代次數不同,松弛因子與迭代次數的關系見表4.3表4.3 松弛因子與迭代次數的關系Tab 4.3 The relationship between the number of iterations and relaxation factorW(松弛因子)Count(迭代次數)W(松弛因子)Count(迭代次數)W<0inf1.4191.0401.5

24、241.1321.6331.2241.7471.3151.8741.9157W>=2>10000由表4.3可知:w<0,輸出結果中有Inf NaN這樣的解出現，可以知道此時超松弛迭代法不收斂，w>=2,迭代次數大于10000次，迭代次數過大，此時也不收斂。畫出松弛因子與迭代次數的關系圖像見圖4.3圖4.3 松弛因子與迭代次數的關系圖像由圖4.3可以看出：1.不同的松弛因子對超松弛迭代法的收斂速度的影響不同。2.w=1.3時，迭代次數最少，因此對于該方程組，最佳松弛因子是1.3選取松弛因子為w=1.3,MATLAB代碼為:function x,a,count,e=SOR(

25、A,b,jd,x)%A表示系數矩陣,b表示常數項矩陣,jd表示精度(本程序選擇精度為1e-6),x表示任選的初始向量(本程序選零向量)xx=inv(A)*b; %求出真實解er=sqrt(sum(x-xx).*(x-xx);%求出誤差(二范數)count=0;w=1.3,k=1;j=1;while er>=jd %迭代求解for i=1:5x1(i)=-1/A(i,i).*(A(i,1:i-1)*x(1:i-1)+A(i,i+1:5)*x(i+1:5)-b(i); %求出高斯塞德爾解x(i)=(1-w)*x(i)+w*x1(i);%求出超松弛解a(j)=x(i); %把每次迭代結果(x的

26、五個分量)保存j=j+1;ender=sqrt(sum(x-xx).*(x-xx);e(k)=er;%把每次迭代的誤差向量保存k=k+1;count=count+1; %記錄迭代次數if count>10000disp '迭代次數過大,該迭代法不收斂'break; end endend在命令窗口中輸入：A=10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -1 15;b=12 -27 14 -17 12'jd=1e-6; x=0 0 0 0 0' x=SOR(A,b,jd,x),可以得到:1.近似

27、解:x=1.0000 -2.0000 3.0000 -2.0000 1.00002.迭代次數count=153.每次迭代結果及誤差見表4.4表4.4 超松弛迭代法中每次迭代結果及誤差Tab 4.4 The each iteration results and errors of Overrelaxation iteration method 次數x1(k)x2(k)x3(k)x4(k)x5(k)誤差er11.5600-4.12531.2544-1.8625-0.19123.052122.1280-2.33341.8601-2.09420.37751.754831.3617-2.35942.61

28、53-1.95390.80520.669441.1215-2.06302.8520-2.01270.93470.212351.0491-2.03422.9662-2.00080.97890.071961.0098-2.00492.9865-1.99980.99580.017871.0033-2.00282.9983-2.00040.99860.004981.0007-2.00002.9992-2.00000.99980.001191.0001-2.00023.0000-2.00001.00000.0002101.0000-1.99993.0000-2.00001.00000.0001111.0

29、000-2.00003.0000-2.00001.00000.0000121.0000-2.00003.0000-2.00001.00000.0000131.0000-2.00003.0000-2.00001.00000.0000141.0000-2.00003.0000-2.00001.00000.0000151.0000-2.00003.0000-2.00001.00000.0000由表4.3可知：1.當0<w<2時，超松弛迭代法是收斂的，而當w<=0或w>=2時，該迭代法是不收斂的，這與理論分析”0<w<2是超松弛迭代法收斂的必要條件”相一致2.選擇不

30、同的w的值，迭代次數是不同的，因此選擇適當的w的值，可使迭代速度達到最快。3.當w=1時，根據SOR的構造方法知，SOR法就是高斯塞德爾迭代法。5小結通過以上數據測試可以分析出以下幾點：1. 雅可比迭代法、高斯塞德爾迭代法、超松弛迭代法三種迭代法對應的迭代次數是逐漸減少的，從而可以得到它們的收斂速度上是逐漸增加的。2. 經過很少次的迭代運算,在滿足設定精度情況下,三種迭代法計算得到的近似解與嚴格計算方程組后的精確解達到了相同，說明三種迭代法的求解精度是高的。3.由MATLAB計算得，A與2D-A均為對稱正定矩陣，有收斂條件知，這三種迭代法均收斂，由上機實驗得到的數據知，三種迭代方法均收斂，這與理論分析相一致。4.由收斂條件知，三種迭代法的收斂性只與迭代矩陣M(或者說系數矩陣A)有關，與右端項無關。線性方程組