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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、為嚴(yán)格對(duì)角占優(yōu)矩陣，故，與已知矛盾。因而只能，即，于是SOR法收斂。6.3 誤差估計(jì)定理6.10 設(shè)有方程組及一階定常迭代法如果有的某種算子范數(shù)，則(1) 迭代法收斂，即對(duì)任意的有且(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作誤差估計(jì)，一般可取1，2或范數(shù)。結(jié)論（3）是近似解的誤差事后估計(jì)式，對(duì)于給定的精度（當(dāng)然應(yīng)當(dāng)選得恰當(dāng)，小于或接近于機(jī)器精度可能會(huì)造成死循環(huán)），只要不是很接近1，則可用來(lái)控制迭代終止。若，即使很小，也

15、不能判定很小。2）結(jié)論（4）可用作迭代次數(shù)的估計(jì)。根據(jù)事先給定的精度，可以估算出迭代的次數(shù)：迭代法是否收斂雖與初始向量的選取無(wú)關(guān)，但由上面的公式看出對(duì)迭代次數(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)其中因子是個(gè)小數(shù)。因?yàn)椋?，我們可選擇足夠大的使這樣便可使上面的不等式(6-13)成立。對(duì)于所有使的，上式等價(jià)于 (6-14)所以達(dá)到(6-13)要求的最小迭代次數(shù)反比于。定義6.6 稱(chēng)為迭代法的平均收斂率。以上定義的是平均壓縮率的對(duì)數(shù)值（再取負(fù)號(hào)）。它是依賴(lài)于所選