解線性方程組迭代法

1、解線性方程組的迭代法Haha送給需要的學(xué)弟學(xué)妹摘要:因?yàn)槔碚摰姆治霰砻?，求解病態(tài)的線性方程組是困難的，但是實(shí)際情況是否如此，需要我們來(lái)具體檢驗(yàn)。系數(shù)矩陣H為Hilbert矩陣，是著名的病態(tài)問(wèn)題。因而決定求解此線性方程組來(lái)驗(yàn)證上述問(wèn)題。詳細(xì)過(guò)程是通過(guò)用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四種方法求解線性方程組。關(guān)鍵詞：病態(tài)方程組、Gauss消去法、J迭代法、GS迭代法、SOR迭代法目錄：一、問(wèn)題背景介紹二、建立正確額數(shù)學(xué)模型三、求解模型的數(shù)學(xué)原理1、Gauss消去法求解原理2、Jacobi迭代法求解原理3、G-S迭代法求解原理4、SOR迭代法求解原理5、Jacobi和G-S兩種迭

2、代法收斂的充要條件四、計(jì)算過(guò)程（一）Hilbert矩陣維數(shù)n=6時(shí)1、Gauss消去法求解2、Jacobi迭代法求解3、G-S迭代法求解4、SOR迭代法求解（二）Hilbert矩陣維數(shù)n=20、50和100時(shí)1、G-S迭代法求解圖形2、SOR迭代法求解圖形五、編寫計(jì)算程序六、解釋計(jì)算結(jié)果1、Gauss消去法誤差分析2、G-S迭代法誤差分析3、SOR迭代法誤差分析G-S迭代法與SOR迭代法的誤差比較七、心得體會(huì)正文：一、問(wèn)題背景介紹。理論的分析表明，求解病態(tài)的線性方程組是困難的。實(shí)際情況是否如此，會(huì)出現(xiàn)怎樣的現(xiàn)象呢？二、建立正確的數(shù)學(xué)模型。考慮方程組的求解，其中系數(shù)矩陣H為Hilbert矩陣，這

3、是一個(gè)著名的病態(tài)問(wèn)題。通過(guò)首先給定解（為方便計(jì)算，筆者取x的各個(gè)分量等于1），再計(jì)算出右端這樣的解就明確了，再用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四種方法分別求解將求解結(jié)果與給定解比較，而后求出上述四種方法的誤差，得出哪種方法比較好。三、求解模型的數(shù)學(xué)原理。1、Gauss消去法求解原理對(duì)于（A非奇異）求解時(shí)，可以先將A分解成一個(gè)下三角矩陣L和一個(gè)上三角矩陣U的乘積，即，就可以通過(guò)求解出的值。接下來(lái)就具體講講如何將A分解成L和U，也就是Gauss消去法。欲把一個(gè)給定的矩陣A分解為一個(gè)下三角陣L與一個(gè)上三角陣U的乘積，最自然的做法便是通過(guò)一系列的初等變換，逐步將A約化為一個(gè)上三角

4、陣，而又能保證這些變換的乘積是一個(gè)下三角陣。這可歸結(jié)為：對(duì)于一個(gè)任意給定的向量找一個(gè)盡可能簡(jiǎn)單的下三角陣，使經(jīng)這一矩陣作用之后的第至第個(gè)分量均為零。能夠完成這一任務(wù)的最簡(jiǎn)單的下三角陣便是如下形式的初等下三角陣：其中即這種類型的初等下三角陣稱作Gauss變換，而稱向量為Gauss向量。對(duì)于一個(gè)給定的向量我們有由此立即可知，只要取便有當(dāng)然，這里我們要求而后經(jīng)過(guò)多次變換可以得到從而求出上三角陣U，而后通過(guò)求得下三角陣將(1.2)和(1.3)帶入到(1.1)式中求出的值即可。2、J迭代法求解原理考慮非奇異線性代數(shù)方程組令其中那么(1.4)式和合并后可以寫成其中若給定初始向量并代入(1.4)式右邊，又可

5、得到一個(gè)向量；一次類推，有 這就是所謂的Jacobi迭代法，其中叫做Jacobi迭代法的迭代矩陣，叫做Jacobi迭代法的常數(shù)項(xiàng)。3、GS迭代法求解原理注意到Jacobi迭代法中各分量的計(jì)算順序是沒(méi)有關(guān)系的，先算那個(gè)分量都一樣?，F(xiàn)在，假設(shè)不按Jacobi迭代格式，而是在計(jì)算的第一個(gè)分量用的各個(gè)分量計(jì)算，但當(dāng)計(jì)算的第二個(gè)分量時(shí)，因已經(jīng)算出，用它代替，其他分量仍用。類似地，計(jì)算時(shí)，因都已算出，用它們代替其他分量仍用的分量，于是有我們稱這種迭代格式為Gauss-Seidel迭代法，簡(jiǎn)稱為G-S迭代法。它的一個(gè)明顯的好處是在編寫程序是存儲(chǔ)量減少了。如果存在，G-S迭代法可以改寫成我們把叫做G-S迭代法

6、的迭代矩陣，而把叫做G-S迭代法的常數(shù)項(xiàng)。4、SOR迭代法求解原理我們知道，G-S迭代法的迭代格式為現(xiàn)在令則有這就是說(shuō)，對(duì)G-S迭代法來(lái)說(shuō)，可以看作在向量上加上修正項(xiàng)而得到的。若修正項(xiàng)的前面加上一個(gè)參數(shù)，便得到松弛迭代法的迭代格式用分量形式表示即為 其中叫做松弛因子。當(dāng)時(shí)，相應(yīng)的迭代法叫做超松弛迭代法；當(dāng)時(shí)，叫做低松弛迭代法；當(dāng)時(shí)，就是G-S迭代法。我們把超松弛迭代法簡(jiǎn)稱為SOR迭代法。因?yàn)榇嬖?，所?1.10)式可以改寫為 其中叫做松弛迭代法矩陣。而SOR迭代法收斂的充要條件是由(1.12)式知，SOR迭代法的譜半徑依賴于，當(dāng)然會(huì)問(wèn)：能否適當(dāng)選取使收斂速度最快？這就是選擇最佳松弛因子的問(wèn)題。

7、經(jīng)過(guò)相關(guān)計(jì)算可知，隨著從0增加，減少，直至?xí)r，達(dá)到極小再增加時(shí)，開始增加。因此，稱為最佳松弛因子。5、Jacobi和G-S兩種迭代法收斂的充要條件Jacobi迭代法和G-S迭代法兩種迭代法有一個(gè)共同的特點(diǎn)，那就是新的近似解是已知近似解的線性函數(shù)，并且只與有關(guān)，即它們都可以表示成如下形式：事實(shí)上，對(duì)Jacobi迭代法，有對(duì)G-S迭代法，有故要求出上述兩個(gè)迭代法中有確定的解，且與相對(duì)誤差較小，就必須說(shuō)明用上述兩種迭代法求解時(shí)收斂。下面就給出關(guān)于上述兩種迭代法收斂的證明原理解方程組的單步線性定常迭代法(1.15)收斂的充分必要條件是其迭代矩陣的譜半徑小于1，即從上述的(1.16)可知，迭代序列收斂取

8、決于迭代矩陣的譜半徑，而與初始向量的選取和常數(shù)項(xiàng)無(wú)關(guān)。四、計(jì)算過(guò)程。方程組的求解，其中系數(shù)矩陣H為Hilbert矩陣，（一）求解，我們暫時(shí)選擇系數(shù)矩陣H的維數(shù)，所以令x的各分量都為1,，即根據(jù)得而后我們接下來(lái)就用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四種迭代法求解的解x。1、Gauss消去法求解因?yàn)樗杂?1.2)式知H分解的上三角矩陣由(1.3)式求出H的下三角矩陣再通過(guò)(1.1)求出x的值所以2、Jacobi迭代法求解將系數(shù)矩陣H用(1.4)方法分解成所以由(1.5)式知 在用Jacobi迭代法求解前，我們先計(jì)算迭代矩陣B的譜半徑，B的特征值為所以 由(1.16)知迭代矩陣B

9、發(fā)散，所以無(wú)法用Jacobi迭代法解x的值。3、G-S迭代法求解由(1.8)式知通過(guò)計(jì)算得迭代矩陣的特征值為所以由(1.16)式知迭代矩陣收斂。令初始值 將其代入(1.8)式中，直到得 此時(shí)即為的解。4、SOR迭代法求解根據(jù)(1.18)和(1.19)知 再代入(1.13)式，得因?yàn)闉橐粋€(gè)虛數(shù)，從而說(shuō)明其最佳松弛因子不存在，故取所以，其特征值為故的譜半徑為由(1.12)知SOR迭代法收斂。令初始值 將其代入(1.10)式中，直到得 此時(shí)即為的解。（二）現(xiàn)在逐步增大問(wèn)題的維數(shù)，因?yàn)橛桑ㄒ唬┛芍姆N方法只能有Gauss消去法、G-S迭代法和SOR迭代法求解，故下面只列出這三種求解方法。1、當(dāng)n=2

10、0時(shí)，Gauss消去法通過(guò)計(jì)算知道，此時(shí)上三角矩陣U的第十八行全部變成0了，從而導(dǎo)致結(jié)果無(wú)法計(jì)算，故此方法無(wú)法求解。因?yàn)閚=20時(shí)，Gauss消去法求解無(wú)法算出結(jié)果，故以下計(jì)算不用此方法了。G-S迭代法SOR迭代法2、當(dāng)n=50時(shí)G-S迭代法：SOR迭代法3、當(dāng)n=100時(shí)G-S迭代法：SOR迭代法：五、編寫計(jì)算程序。（一） 1、Gauss消去法求解 2、Jacobi迭代法求解 3、G-S迭代法求解部分程序在上面2（Jacobi迭代法求解）的里面 4、SOR迭代法求解部分程序在上面2（Jacobi迭代法求解）的里面 （二）Gauss消去法前面部分算法和（一）中的1（Gauss消去法）類似，此處

11、就不列出了。G-S迭代法此處程序基本上（一）中的3（G-S迭代法求解）基本類似，此處就不累贅了。SOR迭代法此處程序基本上（一）中的4（SOR迭代法求解）基本類似，此處就不累贅了。六、解釋計(jì)算結(jié)果。（一）Gauss消去法誤差分析：雖然保留三位小數(shù)的情況下，此方法求出的結(jié)果和標(biāo)準(zhǔn)結(jié)果是一樣的，但是誤差還是有的，下面給出用此方法求解保留十二位小數(shù)后的結(jié)果由此結(jié)果可知，誤差是存在的，只是很小而已。G-S迭代法誤差分析：用此方法計(jì)算的結(jié)果的相對(duì)誤差：可見，此誤差在允許范圍。（二）G-S迭代法誤差分析：當(dāng)n=20時(shí)當(dāng)n=50時(shí)當(dāng)n=100時(shí)由上述圖形可知，使用G-S迭代法求解方程組時(shí)，在絕對(duì)誤差相同的情

12、況下，即矩陣H的維數(shù)越大，求出的結(jié)果的相對(duì)誤差就越小。SOR迭代法誤差分析當(dāng)n=20時(shí)當(dāng)n=50時(shí)當(dāng)n=100時(shí)由上述圖形可知，使用SOR迭代法求解方程組時(shí)，在絕對(duì)誤差相同的情況下，即矩陣H的維數(shù)越大，求出的結(jié)果的相對(duì)誤差就越小。兩種迭代方法雖然都能計(jì)算出結(jié)果，但是由圖可知，SOR迭代法的計(jì)算結(jié)果相對(duì)G-S迭代法計(jì)算的結(jié)果準(zhǔn)確，但是迭代次數(shù)遠(yuǎn)遠(yuǎn)高于G-S迭代法（相同的絕對(duì)誤差，在系數(shù)矩陣H維數(shù)n=6時(shí)，G-S迭代法迭代次數(shù)是997次，而SOR迭代法迭代次數(shù)卻是5635次）。因此對(duì)于求解方程組，用G-S迭代法更為適合。七、心得體會(huì)通過(guò)本次課程設(shè)計(jì)，我更清楚地了解了如何使用Mathcad這個(gè)數(shù)學(xué)軟件，并且能夠靈活的運(yùn)用。在做本次課程設(shè)計(jì)的過(guò)程中，又一次地認(rèn)真的學(xué)習(xí)了Gauss消去法、Jacobi迭代法、G-S迭代法和SOR迭代法這四種求解線性方程組的方法，自己用更深