數(shù)值分析第6章 解線性方程組的迭代法

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

2、迭代方法。1.1向量序列和矩陣序列的極限由于中的向量可與的點(diǎn)建立對應(yīng)關(guān)系，由點(diǎn)列的收斂概念及向量范數(shù)的等價性，可得到向量序列的收斂概念。定義6.1 設(shè)為中的向量序列，如果其中為向量范數(shù)，則稱序列收斂于，記為。定理6.1中的向量序列收斂于中的向量當(dāng)且僅當(dāng)其中。證明由定義6.2，收斂于，即而對任意，有由極限存在準(zhǔn)則得即定義6.2 設(shè)為中的矩陣序列，如果其中為矩陣范數(shù)，則稱序列收斂于，記為。定理6.2中的矩陣序列收斂于中的矩陣的充要條件為證明留給讀者。定理6.1和6.2表明，向量序列和矩陣序列的收斂可以歸結(jié)為對應(yīng)分量或?qū)?yīng)元素序列的收斂。定理6.3的充分必要條件是其中兩個極限的右端分別指零矩陣和零向

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

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

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

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

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

8、把元素為1的那條斜線向右上方推一步。以為例由于，其中為階單位陣。因此其中。利用極限，得到所以的充要條件是，即。定理6.5 對任意的初始向量和右端項(xiàng)，由迭代格式 (6-11)產(chǎn)生的向量序列收斂的充要條件。證明必要性。設(shè)存在向量，使得，則由此及迭代公式(6-12)，有于是因?yàn)闉槿我饩S向量，因此上式成立必須由定理6.4，即得。充分性。若，則不是的特征值，因而有，于是對任意維向量，方程組有唯一解，記為，即并且又因?yàn)樗?，對任意初始向量，都有即由迭代公?6-11)產(chǎn)生的向量序列。推論1對任一種矩陣范數(shù)，若，則收斂。推論2 SOR法收斂的必要條件是。證明設(shè)有特征值。因?yàn)橛啥ɡ?.5，SOR法收斂必有，又

9、因?yàn)橛谑怯兴?。定?.5表明，迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量以方程組的右端項(xiàng)無關(guān)。對同一方程組，由于不同的迭代法迭代矩陣不同，因此可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。例3 研究用Jacobi和Gauss-Seidel迭代法解方程組的斂散性。(1) ； (2) 解 (1) Jacobi法的迭代矩陣為其特征方程為由已知得，所以，因此Jacobi迭代法收斂。如果用Gauss-Seidel法，迭代矩陣為特征方程由已知得特征值，所以，因此Gauss-Seidel迭代法發(fā)散。(2) J法的特征方程為令，因?yàn)樗栽谥杏幸桓?，于是因此Jacobi迭代法發(fā)散。G法的特征方程為得特征根

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

11、，否則，稱為不可約。定義 若，當(dāng)時，如果存在一個下標(biāo)的非空子集，使得當(dāng)而時有則稱為可約陣。 例如就是可約矩陣，因?yàn)槿《x中的，當(dāng)，而，即時，有，即另一方面，從定義6.5判斷，將其第二行和第三行對換，同時也把第二列和第三列對換，就可化為定理6.6 若嚴(yán)格對角占優(yōu)或?yàn)椴豢杉s弱對角占優(yōu)矩陣，則，且非奇異。證明 從嚴(yán)格對角占優(yōu)可知。若奇異，則有滿足。設(shè)，則方程組的第個方程為由此得與為嚴(yán)格對角占優(yōu)矛盾。我們有如下結(jié)論：1若為嚴(yán)格對角占優(yōu)陣或不可約弱對角占優(yōu)，則Jacobi迭代法和Gauss-Seidel均收斂。2若為嚴(yán)格對角占優(yōu)陣或不可約弱對角占優(yōu)，則SOR法收斂。3若為對稱正定矩陣，則SOR收斂的充要

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

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

14、只能，即，于是SOR法收斂。6.3 誤差估計定理6.10 設(shè)有方程組及一階定常迭代法如果有的某種算子范數(shù)，則(1) 迭代法收斂，即對任意的有且(2) (3) (4) 證明由定理6.5，結(jié)論(1)是顯然的事實(shí)。(2) 由關(guān)系式及，有(a)(b)反復(fù)利用(b)即得(2)。(3) 利用(b)得于是(4) 反復(fù)利用(a)，則得到(4)。注：1）利用定理6.10作誤差估計，一般可取1，2或范數(shù)。結(jié)論（3）是近似解的誤差事后估計式，對于給定的精度（當(dāng)然應(yīng)當(dāng)選得恰當(dāng)，小于或接近于機(jī)器精度可能會造成死循環(huán)），只要不是很接近1，則可用來控制迭代終止。若，即使很小，也不能判定很小。2）結(jié)論（4）可用作迭代次數(shù)的估

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