解線性方程組的迭代法

1、精選優(yōu)質文檔-傾情為你奉上精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè)第五章 解線性方程組的迭代法本章主要內容：迭代法收斂定義，矩陣序列收斂定義，迭代法基本定理，雅可比迭代法，高斯-塞德爾迭代法，系數(shù)矩陣為嚴格對角占優(yōu)陣的采用雅可比迭代、高斯-塞德爾迭代的收斂性。教學目的及要求：使學生了解迭代法收斂定義，迭代法基本定理，掌握雅可比迭代法、高斯-塞德爾迭代法。教學重點：雅可比迭代法，高斯-塞德爾迭代法。教學難點：迭代法基本定理的證明以及作用。教學方法及手段：應用嚴格的高等代數(shù)、數(shù)學分析知識，完整地證明迭代法基本定理，講清雅可比迭代法與高斯-

2、塞德爾迭代法的關系，介紹雅可比迭代法與高斯-塞德爾迭代法在編程中的具體實現(xiàn)方法。在實驗教學中，通過一個具體實例，讓學生掌握雅可比迭代法與高斯-塞德爾迭代法的具體實現(xiàn)，并能通過數(shù)值計算實驗，揭示高斯-塞德爾迭代法是對雅可比迭代法的一種改進這一事實。教學時間：本章的教學的講授時間為6學時，實驗學時4學時。教學內容：一 迭代法定義對于給定的線性方程組，設它有唯一解，則 (6.1)又設為任取的初始向量，按下述公式構造向量序列 (6.2)這種逐步代入求近似解的方法稱為迭代法（這里B與f與k無關）。如果存在（記為），稱此迭代法收斂，顯然就是方程組的解，否則稱此迭代法發(fā)散。迭代法求方程近似解的關鍵是是討論由

3、(6.1)式所構造出來的向量序列是否收斂。為此，我們引入誤差向量將(6.2)式與(6.1)式相減，我們可得遞推下去，得要考察的收斂性，就要研究在什么條件下有也就是要研究在什么條件下有。二 迭代法收斂性定理矩陣的收斂性定義設有矩陣序列及，如果個數(shù)列極限均存在且有則稱收斂于，記為。注：矩陣序列的收斂性是根據矩陣的每個分量序列的收斂性來定義的?！纠}1】討論約當塊矩陣的冪次所構成的矩陣序列的收斂性。形如的矩陣稱之為n階的約當塊。它可以分解成為下面，我們分幾步來研究矩陣序列的收斂性。1 矩陣的冪陣的性質我們不妨以4階陣來看看這種性質。，的性質可歸納為以下兩點：（1） 如時，；（2） m=1時，的第2條

4、對角線元素為1，其余為零；m=2時，的第3條對角線元素為1，其余為零；m=3時，的第4條對角線元素為1，其余為零。 簡言之，的第m+1條對角線元素為1，其余為零（當沒有第m+1條對角線時，應理解為零矩陣）。2 計算約當塊的冪次。當時，3 一個極限性質因為，得到這里，注意事實4 約當塊冪陣的收斂性結論當時，收斂于零矩陣；當，發(fā)散。矩陣序列極限的概念可以用矩陣范數(shù)來描述?！径ɡ?】，其中為矩陣的任意一種范數(shù)。證明 顯然有再利用矩陣范數(shù)的等價性，可證明定理對其他矩陣范數(shù)也成立?！径ɡ?】的充要條件是，有。證明 必要性 記，據，可知。設，對于，有由可知，。類似地，可證明 。這里，是中的基本單位向量組。

5、，則即 ，亦即 。充分性 據，有 ，由的任意性，如果取，則，亦即 類似地，可分別讓，可得故 從而 ?！径ɡ?】設，則的充要條件是。證明 由高等代數(shù)知識，存在非奇奇異矩陣P使其中約當塊且，顯然有其中于是 據例題1的結論，的充要條件是故的充要條件是。【定理4】（迭代法基本定理）設有方程組以及迭代法對任意選取初始向量，迭代法收斂的充要條件是矩陣的譜半徑。證明 充分性 設則矩陣的特征值均大于零，故非奇異。有唯一解，且 ，即 。誤差向量由設，應用定理3，有。于是，對任意，有，即 。必要性 設對任意有其中，顯然，極限是方程組的解，且對任意有由定理2知 。再由定理3，即得。判斷迭代收斂時，需要計算，一般情況

6、下，這不太方便。由于，在實際應用中，常常利用矩陣B的范數(shù)來判別迭代法的收斂性?！径ɡ?】（迭代法收斂的充分條件）設有方程組以及迭代法（）如果有B的某種范數(shù)，則（1）迭代法收斂，即對任取有 且 。（2）。（3）。（4）。證明 （1）由基本定理4，結論（1）是顯然的。（2）由關系式，有（3）即顯然亦成立。（4）。注：該定理中的第3款可作為誤差的事后估計式。三 幾種常見的迭代法及收斂性下面，我們討論線性方程組如何用迭代法求近似解的問題。這里，為非奇異矩陣，。（一） 雅可比迭代法。設，將A分解成以下三部分記，那么 形成迭代式對于任意初值，（）這就是雅可比迭代法。注：1 形成雅可比迭代式的條件是A的主對

7、角線元素均非零。2 雅可比迭代收斂的條件是?！纠}2】對于線性方程組利用雅可比迭代法求其近似解（允許的最大迭代次數(shù)N，近似解的精度eps，由用戶設定）。（二） 高斯-塞德爾迭代法。從雅可比迭代的分量形式可以發(fā)現(xiàn)，在進行第k次迭代時，利用，生成向量，其分量產生的次序是，。我們對雅可比方法進行以下改變設計：步1 應用信息，據雅可比迭代分量式，生成分量；步2 應用信息，據雅可比迭代分量式，生成分量；步3 應用信息，據雅可比迭代分量式，生成分量；步n 應用信息，據雅可比迭代分量式，生成分量。如此生成的設計方案，是想更好地利用已有的最新有用信息。有理由相信，如此所獲得的迭代式，其計算效果應該會更好一些。

8、下面，我們具體給出這種迭代法的表達形式。即左邊可改寫為右邊可改寫為亦即注意到： ，于是有迭代矩陣為迭代向量為故高斯-塞德爾迭代式為（）故高斯-塞德爾迭代式的分量計算公式為，（）實現(xiàn)高斯-塞德爾迭代法的分量計算公式的算法步1 ，輸入允許的最大迭代次數(shù)N，用戶精度eps，k=0。步2 對于i=1,2,n， 步3 對于i=1,2,n步4 k=k+1步5 若，輸出近似解，停止計算。否則，執(zhí)行步6。步6 若k=N，輸出達到迭代次數(shù)信息，程序中止。否則，執(zhí)行步7。步7 對于i=1,2,n，返回步2。注：1 形成高斯-塞德爾迭代式的條件是存在，而，故只要A的主對角線元素均非零，該逆陣存在。2 高斯-塞德爾迭

9、代收斂的條件是。【例題3】對于線性方程組1 高斯塞德爾迭代法求其近似解（允許的最大迭代次數(shù)N，近似解的精度eps，由用戶設定）。2 通過數(shù)值實驗說明，求該線性方程組的近似解時，高斯塞德爾迭代法的收斂速度較雅可比迭代法要快一些。3 采用分量計算公式編程求該線性方程組的近似解，驗證用矩陣迭代形式求解所得的結果。四 關于解某些特殊方程組迭代法的收斂性在科學及工程計算中，要求方程組，其矩陣常常具有某些特性。例如，具有對角占優(yōu)性質或為不可約陣，或是對稱正定陣等，下面討論用基本迭代法解這些方程組的收斂性?！径x1】設1 如果A的元素滿足稱A為嚴格對角占優(yōu)陣。2 如果A的元素滿足且上式至少有一個不等式嚴格成

10、立，稱A為弱對角占優(yōu)陣。【定義2】設()，如果存在置換陣P，使其中，為r階方陣，為n-r階方陣()，則稱A為可約矩陣。否則，則稱A為不可約矩陣。【定理6】（對角占優(yōu)定理）如果為嚴格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣，則A為非奇異矩陣。證明 只就A為嚴格對角占優(yōu)矩陣證明此定理。采用反證法，如果，則有非零解，記為，則。由齊次方程組第k個方程則有即 與假設矛盾，故，A為非奇異矩陣?！径ɡ?】設，如果1 A為嚴格對角占優(yōu)矩陣，則解的雅可比迭代法，高斯-塞德爾迭代法均收斂。2 A為弱對有占優(yōu)陣，且A為不可約矩陣，則解的雅可比迭代法，高斯-塞德爾迭代法均收斂。證明 只證明1A為嚴格對角占優(yōu)矩陣，故，故A的主對角元素均為非零的，可以生成雅可比迭代式其中，。從而 ，雅可比迭代法收斂。同樣，也可以生成高斯-塞德爾迭代其中，。下面考察B的特征值情況。設為B的任一特征值，于是有由于，于是記 下面來證明，當時，則，于是便證明了B的任一特征值均滿足，從而，高斯-塞德爾迭代法收斂。事實上，當時，由A為嚴格對角占優(yōu)矩陣，則有即C矩陣為嚴格對角占優(yōu)