迭代法及其在數(shù)值求解線性方程組中的應(yīng)用

1、-. z師學(xué)院畢業(yè)論文題目迭代法及其在數(shù)值求解線性方程組中的應(yīng)用*丹丹*院系數(shù)學(xué)與統(tǒng)計學(xué)院專業(yè)數(shù)學(xué)與應(yīng)用數(shù)學(xué)年級班級 B12數(shù)應(yīng)2班指導(dǎo)教師王明建2016年 5 月 20 日-. z畢業(yè)論文作者聲明本人重聲明：所呈交的畢業(yè)論文是本人在導(dǎo)師的指導(dǎo)下獨立進(jìn)展研究所取得的研究成果。除了文中特別加以標(biāo)注引用的容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。本人完全了解有關(guān)保障、使用畢業(yè)論文的規(guī)定，同意學(xué)校保存并向有關(guān)畢業(yè)論文管理機(jī)構(gòu)送交論文的復(fù)印件和電子版。同意省級優(yōu)秀畢業(yè)論文評選機(jī)構(gòu)將本畢業(yè)論文通過影印、縮印、掃描等方式進(jìn)展保存、摘編或匯編；同意本論文被編入有關(guān)數(shù)據(jù)庫進(jìn)展檢索和查閱。本

2、畢業(yè)論文容不涉及國家。論文題目：迭代法及其在數(shù)值求解線性方程組中的應(yīng)用作者單位：師學(xué)院作者簽名：目錄TOC o 1-3 h u HYPERLINK l _Toc30814 摘要 PAGEREF _Toc30814 3 HYPERLINK l _Toc12032 引言 PAGEREF _Toc12032 3 HYPERLINK l _Toc7361 1.預(yù)備知識 PAGEREF _Toc7361 3 HYPERLINK l _Toc18060 1.1迭代法的根本形式 PAGEREF _Toc18060 3 HYPERLINK l _Toc31510 1.2 Jocabi迭代法 PAGEREF _

3、Toc31510 3 HYPERLINK l _Toc6509 分量形式的Jacobi迭代法 PAGEREF _Toc6509 3 HYPERLINK l _Toc21877 矩陣形式的Jacobi迭代法 PAGEREF _Toc21877 3 HYPERLINK l _Toc15204 1.2.3 Jacobi迭代法的算法實現(xiàn)步驟 PAGEREF _Toc15204 3 HYPERLINK l _Toc24054 1.3 Gauss-Seidel迭代法 PAGEREF _Toc24054 3 HYPERLINK l _Toc20948 分量形式的Gauss-seidel迭代法 PAGEREF

4、 _Toc20948 3 HYPERLINK l _Toc6506 矩陣形式的Gauss-seidel迭代法 PAGEREF _Toc6506 3 HYPERLINK l _Toc30531 1.3.3 Gauss-Seidel迭代法的算法實現(xiàn)步驟 PAGEREF _Toc30531 3 HYPERLINK l _Toc9560 1.4超松弛迭代法SOR迭代法 PAGEREF _Toc9560 3 HYPERLINK l _Toc21482 分量形式的SOR方法 PAGEREF _Toc21482 3 HYPERLINK l _Toc11958 矩陣形式的SOR方法 PAGEREF _Toc1

5、1958 3 HYPERLINK l _Toc30716 1.4.3 SOR迭代法的算法實現(xiàn)步驟 PAGEREF _Toc30716 3 HYPERLINK l _Toc10135 1.5迭代法的收斂性 PAGEREF _Toc10135 3 HYPERLINK l _Toc27948 2. 數(shù)值求解線性方程組 PAGEREF _Toc27948 3 HYPERLINK l _Toc31530 2.1用Jacobi迭代法求解 PAGEREF _Toc31530 3-. z HYPERLINK l _Toc24872 2.2用Gauss-Seidel迭代法求解 PAGEREF _Toc24872

6、 3 HYPERLINK l _Toc15030 2.3用超松弛迭代法求解 PAGEREF _Toc15030 3 HYPERLINK l _Toc6438 小結(jié) PAGEREF _Toc6438 3 HYPERLINK l _Toc21371 參考文獻(xiàn) PAGEREF _Toc21371 3 HYPERLINK l _Toc7870 致 PAGEREF _Toc7870 3-. z迭代法及其在數(shù)值求解線性方程組中的應(yīng)用摘要：迭代解法就是通過逐次迭代逼近來得到的近似解的方法。而線性方程組的求解問題是科學(xué)研究及工程計算中最常出現(xiàn)的問題，如構(gòu)造分析、網(wǎng)絡(luò)分析、數(shù)據(jù)分析、測量等，都需求解線性方程組。

7、由于從不同的問題而導(dǎo)出的線性方程組的系數(shù)矩陣不同，因此對于大型稀疏矩陣(零元素很多的多階矩陣，一般)所對應(yīng)的線性代數(shù)方程組，用迭代法求解，在*些精度要求比擬高的問題中，經(jīng)常用迭代法求解。其根本思想為：從*一初始向量出發(fā)，按照*種迭代規(guī)則，不停地對上一次的近似值進(jìn)展修正，得到近似解的向量。當(dāng)近似解收斂于方程組的準(zhǔn)確解向量時，滿足給定精度要求的近似解向量就可看作是的數(shù)值解。關(guān)鍵詞：線性方程組；迭代法；Jacobi法；Gauss-Seidel法；逐次超松弛法Iterative Method and Its Application to Numerical Solution of Linear Equ

8、ationsAbstract：Iterative method is the appro*imate solution obtained by successive iteration. The problem of solving linear equations is the most mon problems in scientific research and engineering calculation, such as structural analysis, network analysis, data analysis, geodetic survey, etc., all

9、need solution of linear equations. Due to the different problems of different and the coefficient matri* of the linear equations derived from, so for large sparse matri* corresponding to the system of linear algebraic equations, is solved by iterative method. In certain accuracy requirement is relat

10、ively high, often solved by iterative method. The basic idea is as follows: starting from a certain initial vector, according to some kind of iterative rule, the last time appro*imation is corrected, and the appro*imate solution is obtained. When the appro*imate solution converges to the e*act solut

11、ion of the equation, the appro*imate solution vector which satisfies the given accuracy requirement can be regarded as the numerical solution.Keywords：linear equations; iterative method; Jacobi method; Gauss-Seidel method; successive over rela*ation method引言一般情況下，對于中小型方程組，直接法是非常有效并且迅速的，而對于高階并且系數(shù)矩陣稀疏

12、的線性方程組，尤其是大型線性方程組，卻遇到了難題。因為直接法的計算量大，存儲量大，連非零元素也要存儲。因而對于大型的線性方程組，常常用迭代法來求解。迭代法與直接法是有差異的，它不能直接通過有限次的算術(shù)運(yùn)算求出方程的準(zhǔn)確解，而是間接的通過迭代來逐步逼近此方程組的準(zhǔn)確解。因此，考慮其收斂性是使用迭代法的關(guān)鍵問題。迭代法較直接法有明顯的優(yōu)勢：程序設(shè)計簡潔，存儲量和計算量少等。尤為重要的是，迭代法是解決具有大型稀疏矩陣的線性方程組的重要方法之一。1.預(yù)備知識為了更深入的學(xué)習(xí)迭代法在數(shù)值求解線性方程組中的應(yīng)用，我們有必要回憶一下迭代法的根本知識。1.1迭代法的根本形式設(shè)有線性方程組，其中為非奇異矩陣，向

13、量，因此有唯一的解。下面介紹迭代法的根本格式。將方程組變形可得到等價的線性方程組，任取初值向量為的近似解，由公式可構(gòu)造出向量序列，假設(shè)滿足下面的式子，則迭代法收斂，就是方程組的解，反之，迭代法就發(fā)散。而式子為迭代格式，為迭代矩陣，為第次迭代的近似的解，而為第次的近似誤差。1.2 Jocabi迭代法分量形式的Jacobi迭代法對線性方程組，有分量形式：1設(shè)，用其它的個變元來表示線性方程組的第個方程中的第個變元，就可得到： (1.2.2)也既是： (1.2.3)2用迭代格式寫出來就是： (1.2.4)也就是： (1.2.5)(3)任意給定的初值向量代入式(1.2.4)就可逐步算出向量序列，且。當(dāng)向

14、量序列收斂時，對于事先給定的精度要求(為一個很小的正數(shù))，就有也即是方程組的近似解。矩陣形式的Jacobi迭代法假設(shè)線性方程組的系數(shù)矩陣A為非奇異，并且對于對角線上的元素，則就可將矩陣分解成 (1.2.6)假設(shè)令則有,即可替換為，變形為：，因為，則，得到迭代公式如下：， (1.2.7)假設(shè)令；，就有，則就稱公式(1.2.7)矩陣形式的Jacobi迭代格式，稱為Jacobi迭代矩陣。以上為Jacobi迭代格式的兩種不同形式，在討論收斂性的時候，主要用Jacobi迭代格式的矩陣形式，而在實際的應(yīng)用計算中，則需要用到Jacobi迭代格式的分量形式。1.2.3 Jacobi迭代法的算法實現(xiàn)步驟步1.輸

15、入必要的初始數(shù)據(jù)，及(迭代的最大次數(shù))步2.對做到步5其過程為：步3.對做步4.假設(shè)，則輸出停機(jī)。否則步5.對做步6.輸出超出最大迭代次數(shù)，停機(jī)。1.3 Gauss-Seidel迭代法分量形式的Gauss-seidel迭代法對于公式，可將公式右端前個分量的上標(biāo)由換成，可得到分量形式的Gauss-seidel迭代法。矩陣形式的Gauss-seidel迭代法對方程組，由前文知。由于,因此等價于，解得，所以可得到迭代格式假設(shè)令,，則公式就是矩陣形式的Gauss-Seidel迭代格式，是Gauss-Seidel迭代矩陣。1.3.3 Gauss-Seidel迭代法的算法實現(xiàn)步驟步1.輸入必要的初始數(shù)據(jù)，

16、及迭代的最大次數(shù)步2.對,做到步4其過程為：步3.對做，步4.假設(shè)，則輸出，停機(jī)。步5.輸出超出最大迭代次數(shù)，停機(jī)。1.4超松弛迭代法SOR迭代法對于解線性方程組，一般來說，Jacobi迭代法的收斂速度緩慢，在實際的生活中很少運(yùn)用。Gauss-Seidel迭代法雖說比Jacobi迭代法收斂的速度稍快，但收斂的速度也不是說特別明顯，因此就需要對其修改，提高收斂的速度。而逐次超松弛迭代法又稱SOR方法就是對修改后的迭代法的一種加速。它的計算公式簡潔，但為了使其在迭代的過程中保持較快的迭代速度，選擇適宜的松弛因子是關(guān)鍵。分量形式的SOR方法設(shè)線性方程組，其中系數(shù)矩陣為非奇異的，,，第步迭代近似值記為

17、，則表示近似解的剩余誤差，則有加速迭代格式就稱作松弛因子。假設(shè)用分量形式的Jacobi迭代格式就是： (1.4.3)中選擇恰當(dāng)?shù)乃沙谝蜃?，就可獲得期望的較快的收斂速度。而在計算時，假設(shè)用前面的Gauss-Seidel迭代思想，利用已經(jīng)計算出來的分量，則就得到一個全新的迭代格式：當(dāng)然，當(dāng)時，將迭代格式應(yīng)用到方程組，可得到由此可推出以下松弛迭代格式：容易發(fā)現(xiàn)，當(dāng)?shù)娜≈禐?時，式是Gauss-Seidel迭代格式。為保證迭代過程的收斂，就必須使，當(dāng)時稱低松弛法，當(dāng)時稱超松弛法。矩陣形式的SOR方法對方程組，仍由前文知對任意實數(shù)，線性方程組就等價于同樣，線性方程組也等價于假設(shè)，可得出也即是是非奇異的。

18、令得到矩陣形式的SOR迭代格式：同樣，矩陣就是矩陣形式的SOR迭代法的迭代矩陣，稱為松弛因子。1.4.3 SOR迭代法的算法實現(xiàn)步驟步1.輸入必要的初始數(shù)據(jù)，及(迭代的最大次數(shù))步2.對做到步4其過程為：步3.對做，步4.假設(shè)，則輸出,停機(jī)。步5.輸出超出最大迭代次數(shù)，停機(jī)。1.5迭代法的收斂性定理1.對任意的初始向量和任意的，設(shè)矩陣為迭代矩陣，則是迭代法收斂的充分必要條件。定義1.對于矩陣，假設(shè)即主對角線上元素的絕對值大于同行其他元素的絕對值之和，則稱矩陣是對角占優(yōu)矩陣。定理2.如果線性方程組的系數(shù)矩陣A是對角占優(yōu)矩陣，則線性方程組的Jacobi迭代格式和Gauss-Seidel迭代格式都是

19、收斂的。定理3.假設(shè)是對稱正定矩陣，則解方程組的Gauss-Seidel迭代法收斂。定理4.假設(shè)解方程組的SOR法收斂，則。定理5.假設(shè)是對稱正定矩陣，且有，則解方程組的SOR法收斂。2.數(shù)值求解線性方程組在此給出幾個例子從而更清晰的理解用迭代法來求解線性方程組。2.1用Jacobi迭代法求解例1.解線性方程組解：對方程進(jìn)展變形，別離出變量，：對應(yīng)的迭代格式為：取迭代初值為,迭代的結(jié)果如下表1所示。可得到方程組的準(zhǔn)確解為，。表1 Jacobi迭代格式的數(shù)值結(jié)果00.20001.30002.000010.73001.72002.380020.84801.84902.782030.94131.94

20、122.878640.96981.96982.953050.98761.98762.975860.99391.99392.990170.99741.99742.995180.99881.99882.999090.99971.99972.9998100.99991.99992.9990迭代解為，2.2用Gauss-Seidel迭代法求解例2.用Gauss-Seidel迭代格式求解例1，即求解以下方程組。解：對方程組進(jìn)展變形，別離出變量由迭代格式，可得到方程組的準(zhǔn)確解,迭代的初始向量選為。迭代的結(jié)果如下表2所示。表2 Gauss-Seidel迭代格式的數(shù)值結(jié)果000010.20001.32002.

21、38420.80881.85772.900030.96581.97662.974840.99261.99422.994450.99831.99872.998760.99961.99972.9997由本例可比擬出，Gauss-Seidel迭代法比Jacobi迭代法收斂速度快。當(dāng)初始向量一樣，近似解到達(dá)同樣精度的時候取，Gauss-Seidel迭代法僅需要6次迭代就滿足要求，而Jacobi迭代法則要迭代9次才能夠滿足此要求。2.3用超松弛迭代法求解例31.用SOR法求解方程組松弛因子取值為，要求。解：由題意知，方程組的系數(shù)矩陣為正定矩陣，所以用SOR法求解此方程組一定是收斂的。可求出迭代公式為：迭

22、代的初始向量選為，迭代的結(jié)果如下表3所示。表3 SOR迭代格式的數(shù)值結(jié)果000014.961.5872-3.228022.29352.6854-2.112831.91213.1223-2.245041.59733.2692-2.167751.53633.3146-2.172261.50873.3280-2.166971.50283.3319-2.167081.50063.3330-2.166791.50013.3333-2.1666小結(jié)迭代法是一種通過逐次逼近來求解方程組準(zhǔn)確解的方法，它的優(yōu)點是：程序算法簡單、占用的存小，有利于在計算機(jī)上實現(xiàn)，因此它適用于求解大型稀疏線性方程組。常用的迭代法有

23、：Jacobi迭代法、Gauss-Seidel迭代法及超松弛迭代法SOR迭代法。Jacobi迭代法簡單，有很好的并行性，適用于并行計算，但收斂的速度較慢；Gauss-Seidel迭代法是典型的串行算法，當(dāng)Jacobi迭代法與Gauss-Seidel迭代法同時收斂的時候，后者比前者收斂速度要快，但這兩種迭代法互不包含，不能夠互相代替。而在實際應(yīng)用中較多的是超松弛迭代法，且Gauss-Seidel迭代法是超松弛迭代法的特例，超松弛迭代法實際上就是Gauss-Seidel迭代法的一種加速，然而選取最正確松弛因子是不太容易的，在本論文中沒有詳細(xì)的展開。對于迭代法來說，迭代法的收斂性和收斂速是使用的關(guān)鍵，并且判別收斂的充分條件應(yīng)該掌握好，同時不收斂的迭代公式在迭代法中是毫無意義的。有些時候?qū)€性方程組做一些簡單的同解的變形8后，再次構(gòu)造迭代公式就可以起到意想不到的結(jié)果。本論文中針對典型的系數(shù)矩陣是對角占優(yōu)矩陣和對稱正定矩陣線性方程組展開討論，非線性方程組的迭代法不在本文的討論圍。此外，對于解線性方程組的迭代法，還有SSOR迭代法、USSOR迭代法、TOR迭代法11、子空間迭代法、遞歸迭代法、濾頻迭代法、主元加權(quán)迭代