數值分析--第6章解線性方程組的迭代法

1、.第6章 解線性方程組的迭代法直接方法比較適用于中小型方程組。對高階方程組，即使系數矩陣是稀疏的，但在運算中很難保持稀疏性，因而有存儲量大，程序復雜等不足。迭代法則能保持矩陣的稀疏性，具有計算簡單，編制程序容易的優(yōu)點，并在許多情況下收斂較快。故能有效地解一些高階方程組。1 迭代法概述迭代法的基本思想是構造一串收斂到解的序列，即建立一種從已有近似解計算新的近似解的規(guī)則。由不同的計算規(guī)則得到不同的迭代法。迭代法的一般格式式中與有關，稱為多步迭代法。若只與有關，即稱為單步迭代法。再設是線性的，即式中，稱為單步線性迭代法。稱為迭代矩陣。若和與無關，即稱為單步定常線性迭代法。本章主要討論具有這種形式的各

2、種迭代方法。1.1 向量序列和矩陣序列的極限由于中的向量可與的點建立對應關系，由點列的收斂概念及向量范數的等價性，可得到向量序列的收斂概念。定義6.1 設為中的向量序列，如果其中為向量范數，則稱序列收斂于，記為。定理6.1 中的向量序列收斂于中的向量當且僅當其中。證明 由定義6.2，收斂于，即而對任意，有由極限存在準則得即定義6.2 設為中的矩陣序列，如果其中為矩陣范數，則稱序列收斂于，記為。定理6.2 中的矩陣序列收斂于中的矩陣的充要條件為證明留給讀者。定理6.1和6.2表明，向量序列和矩陣序列的收斂可以歸結為對應分量或對應元素序列的收斂。定理6.3 的充分必要條件是其中兩個極限的右端分別指

3、零矩陣和零向量。證明 對任一種算子范數，有，從而可證必要性。若依次取個單位向量，其中的第個分量為1，其它分量為零。得所以。充分性得證。1.2 迭代公式的構造將非奇異線性方程組變形為等價方程組 (6-1)由此構造迭代公式 (6-2)給定初始向量后，按此迭代公式產生向量序列，當充分大時，以作為方程組的近似解，這就是求解線性方程組的單步定常線性迭代法。稱為迭代矩陣。定義6.3 如果對任意的初始向量及，迭代法(6-2)得出的向量序列都有成立，其中為一確定的向量，它不依賴于的選取，則稱迭代法(6-2)是收斂的，否則稱迭代法(6-2)是發(fā)散的。顯然，若按式(6-2)產生的向量序列收斂于向量，則有即是方程組

4、(6-1)的解。2 基本迭代法2.1 Jacobi（雅可比）迭代法考慮方程組，即 (6-3)其中非奇異，故不妨設。(6-3)等價變形為有 (6-4)由此構造迭代公式 (6-5)記則。由式(6-3)到式(6-4)的過程用矩陣形式表示為因此式(6-5)的矩陣形式為 (6-6)其中。式(6-5)為迭代法的分量形式，它可用于計算迭代近似解；式(6-6)為迭代法的矩陣形式，它主要用于驗證迭代法是否收斂及定性分析。算法6.11輸入，維數，最大容許迭代次數。2置3對4若，輸出，停機，否則轉5。5若，置，轉3；否則，輸出失敗信息，停機。2.2 Gauss-Seidel（高斯-賽德爾）迭代法在Jacobi迭代法

5、中，是用的全部分量來計算的全部分量的，然而在計算分量時，都已經算出，如果Jacobi迭代法收斂，試想用多迭代一次的代替來計算，可望取得更好的結果。這就是Gauss-Seidel迭代法的基本思想。其迭代公式為 (6-7)式(6-7)的矩陣形式為因此迭代法的矩陣形式為 (6-8)其中。算法6.21輸入，維數，最大容許迭代次數。2置3計算4若，輸出，停機，否則轉5。5若，置，轉3；否則，輸出失敗信息，停機。2.3 SOR迭代法解線性方程組的超松弛法，也叫SOR法，是目前求解大型方程組的一種最常用的方法。是Gauss- Seidal迭代法的一種加速方法。對一個收斂的Gauss-Seidel迭代法，第次

6、的迭代結果一般要比第次的好。第次的迭代結果可看作第次基礎上的修正，現在我們引入一個參數，來改變這個修正量。這就是SOR方法的基本思想。記，其中由Gauss-Seidel迭代公式算得。于是有可以把看作Gauss-Seidel迭代的修正項，即第次近似解以此項修正后得到的近似解。松弛法是將乘上一個參數因子作為修正項而得到新的近似解，其具體公式為即 (6-9)按式(6-9)計算方程組的近似解序列的方法稱為松弛法，稱為松弛因子。當為低松弛，是Gauss-Seidel迭代，當時稱為超松弛法，簡稱SOR法。式(6-9)的矩陣形式為即注意到，有 (6-10)其中。算法6.31輸入，維數，最大容許迭代次數。2置

7、3計算4若，輸出，停機，否則轉5。5若，置，轉3；否則，輸出失敗信息，停機。例1 用Jacobi和Gauss-Seidel迭代法求解線性方程組解 Jacobi迭代法的迭代公式為(算法語言)取，迭代9次的近似解。容易驗證，方程組的精確解為。G-S法的迭代公式為迭代6次的近似解。例2 取，用超松弛法求解方程組解 迭代公式為3 迭代法的收斂性6.1 一階定常迭代法的基本定理定理6.4 設，則（零矩陣）的充分必要條件是矩陣的譜半徑。證明 根據Jordan標準形定理，恒有非奇異方陣，使其中若當塊且，顯然有，其中于是。引進記號表示階方陣，其元素僅在對角線右上方第條平行線上的值為1，其余為0，即當時，。不難

8、證得即具有特點：每乘一次，相當于把元素為1的那條斜線向右上方推一步。以為例由于，其中為階單位陣。因此其中。利用極限，得到所以的充要條件是，即。定理6.5 對任意的初始向量和右端項，由迭代格式 (6-11)產生的向量序列收斂的充要條件。證明 必要性。設存在向量，使得，則由此及迭代公式(6-12)，有于是因為為任意維向量，因此上式成立必須由定理6.4，即得。充分性。若，則不是的特征值，因而有，于是對任意維向量，方程組有唯一解，記為，即并且又因為所以，對任意初始向量，都有即由迭代公式(6-11)產生的向量序列。推論1 對任一種矩陣范數，若，則收斂。推論2 SOR法收斂的必要條件是。證明 設有特征值。

9、因為由定理6.5，SOR法收斂必有，又因為于是有所以。定理6.5表明，迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量以方程組的右端項無關。對同一方程組，由于不同的迭代法迭代矩陣不同，因此可能出現有的方法收斂，有的方法發(fā)散的情形。例3 研究用Jacobi和Gauss-Seidel迭代法解方程組的斂散性。(1) ； (2) 解 (1) Jacobi法的迭代矩陣為其特征方程為由已知得，所以，因此Jacobi迭代法收斂。如果用Gauss-Seidel法，迭代矩陣為特征方程由已知得特征值，所以，因此Gauss-Seidel迭代法發(fā)散。(2) J法的特征方程為令，因為所以在中有一根，于是因此Jacob

10、i迭代法發(fā)散。G法的特征方程為得特征根，所以因此G-S迭代法收斂。注：1）在求G-S法和SOR法的特征方程時，注意到事實可避免求逆矩陣。2）J法和G法的收斂性沒有必然聯系。3）定理6.5雖然給出了判別迭代法收斂的充要條件，但實際使用時很不方便。因為求譜半徑卻是比較困難的事，因此常利用，作為上界的一種估計式。需要指出的是：矩陣范數可以是任何一種矩陣范數，不限于算子范數，常用的范數有；其次，使用矩陣范數判別只是充分條件，而非必要條件。6.2特殊方程組迭代法的收斂性定義6.4 若滿足且至少有一個，使上式中不等式嚴格成立，則稱為弱對角占優(yōu)。若所有的不等式均成立，則稱為嚴格對角占優(yōu)。定義6.5 若，能找

11、到排列矩陣，使得其中均為方陣，稱為可約，否則，稱為不可約。定義 若，當時，如果存在一個下標的非空子集，使得當而時有則稱為可約陣。 例如就是可約矩陣，因為取定義中的，當，而，即時，有，即另一方面，從定義6.5判斷，將其第二行和第三行對換，同時也把第二列和第三列對換，就可化為定理6.6 若嚴格對角占優(yōu)或為不可約弱對角占優(yōu)矩陣，則，且非奇異。證明 從嚴格對角占優(yōu)可知。若奇異，則有滿足。設，則方程組的第個方程為由此得與為嚴格對角占優(yōu)矛盾。我們有如下結論：1若為嚴格對角占優(yōu)陣或不可約弱對角占優(yōu)，則Jacobi迭代法和Gauss-Seidel均收斂。2若為嚴格對角占優(yōu)陣或不可約弱對角占優(yōu)，則SOR法收斂。

12、3若為對稱正定矩陣，則SOR收斂的充要條件為。例4 考慮系數矩陣，的方程組。顯然，為嚴格對角占優(yōu)，故J和G-S法均收斂。非嚴格對角占優(yōu)，但為對稱正定矩陣，故取，SOR法收斂。例5 若計算可得，所以J和G-S法均發(fā)散。如果改變方程的次序，有顯然為嚴格對角占優(yōu)，故J和G-S法均收斂。表明，改變方程組中方程的次序，即將系數矩陣作行交換會改變迭代法的收斂性。定理6.7 若為嚴格對角占優(yōu)陣或不可約弱對角占優(yōu)，則J法和GS法均收斂。證明 我們只給出嚴格對角占優(yōu)情形的證明。只需證明和。J法的迭代陣顯然有，故，從而J法收斂。GS法的特征方程為令，有。現在證明。采用反證法，若，則由為嚴格對角占優(yōu)陣有因此為嚴格對

13、角占優(yōu)陣，故，矛盾，因此只能，即，從而GS法收斂。定理6.8 若為對稱正定矩陣，則解的SOR法收斂的充要條件為。證明 只需證明充分性。設是的任一特征值（可能是復數），若能證明，則定理得證。設是的相應于的特征向量（可能是復向量），即也就是上式兩邊與作復內積，有則利用正定陣的對角元素大于0，有（由于為對稱正定陣，所以對，有，特別取，有）記由于，所以，故于是，而注意到及的正定性可知的分子小于分母，即，從而，SOR法收斂。定理6.9 若為嚴格對角占優(yōu)陣或不可約弱對角占優(yōu)，則SOR法收斂。證明 SOR法的特征方程為即設是上述方程的任一根，我們只需證明。采用反證法，假設，由已知，則，于是令，有。由于所以也

14、為嚴格對角占優(yōu)矩陣，故，與已知矛盾。因而只能，即，于是SOR法收斂。6.3 誤差估計定理6.10 設有方程組及一階定常迭代法如果有的某種算子范數，則(1) 迭代法收斂，即對任意的有且(2) (3) (4) 證明 由定理6.5，結論(1)是顯然的事實。(2) 由關系式及，有(a) (b) 反復利用(b)即得(2)。(3) 利用(b)得于是(4) 反復利用(a)，則得到(4)。注：1）利用定理6.10作誤差估計，一般可取1，2或范數。結論（3）是近似解的誤差事后估計式，對于給定的精度（當然應當選得恰當，小于或接近于機器精度可能會造成死循環(huán)），只要不是很接近1，則可用來控制迭代終止。若，即使很小，也

15、不能判定很小。2）結論（4）可用作迭代次數的估計。根據事先給定的精度，可以估算出迭代的次數：迭代法是否收斂雖與初始向量的選取無關，但由上面的公式看出對迭代次數卻有很大的影響，因而應重視初始向量的選取。6.4 迭代法的收斂速度及最佳松弛因子為非奇異矩陣，設是(6-1)的解，即以(6-2)式減去上式，并記誤差向量為，則有由此遞推得 (6-12)設迭代格法(6-2)收斂，即，從(6-12)知，現設，則有這里的矩陣范數均從屬于向量范數，根據范數的性質有所以給出了迭代次后誤差向量范數與初始誤差向量范數之比的上確界。這樣，迭代次后，平均每次迭代誤差范數的壓縮率就可以看成是。如果要求迭代次后有 (6-13)其中因子是個小數。因為，所以，我們可選擇足夠大的使這樣便可使上面的不等式(6-13)成立。對于所有使的，上式等價于 (6-14)所以達到(6-13)要求的最小迭代次數反比于。定義6.6 稱為迭代法的平均收斂率。以上定義的是平均壓縮率的對數值（再取負號）。它是依賴于所選