第5章-線性方程組的迭代解

結(jié)束第5章線性方程組的迭代解法

線性方程組的直接法，用于階數(shù)不太高的線性方程組效果較好.實際工作中有的線性方程組階數(shù)很高，但其中的大多數(shù)系數(shù)為0，這一類的線性方程組的系數(shù)陣稱為稀疏矩陣.稀疏矩陣的存貯和計算有一套技術(shù)處理，可以節(jié)約大量的存貯空間和計算工作量.用直接法計算時，因一次消元就可以使系數(shù)陣喪失其稀疏性，不能有效利用其稀疏的特點.下文介紹的迭代法就有保持系數(shù)陣稀疏的優(yōu)點，此外迭代法也常用來提高已知近似解的精度.5.1迭代法的一般形式線性方程組Ax=b(5.1)其中A非奇異，b≠0，因而它有唯一非零解.

1構(gòu)造與(5.1)等價的方程組x=Bx+f(5.2)即使得(5.2)與(5.1)同解，其中B是n×n矩陣，f是n維向量.結(jié)束任取一個向量x(0)作為x的近似解，用迭代公式

x(k+1)=Bx(k)+f,(k=0,1,2,)(5.3)產(chǎn)生一個向量序列{x(k)}，若則有x=Bx+f，即x是(5.2)的解，當(dāng)然x也就是Ax=b的解.從以上的討論中，可以看出，迭代法的關(guān)鍵有：

1如何構(gòu)造迭代公式x(k+1)=Bx(k)+f

？這樣的構(gòu)造形式不止一種，它們各對應(yīng)一種迭代法.

2迭代法產(chǎn)生的向量序列{x(k)}的收斂條件是什么，收斂速度如何.后面將進(jìn)行討論.5.2幾種常用的迭代法公式5.2.1簡單迭代法

2結(jié)束先看一個算例：例1

從以上三個方程中分別解出x1,x2,x3。按下式進(jìn)行迭代

(k=0,1,2,)

3結(jié)束任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列{x(k)}(k=0,1,2,)，列表如下表5-1。容易驗證，原方程組的精確解為x=(1,2,3)T，從上面的計算可看出，{x(k)}收斂于精確解.一般說來，對方程組：

i=1,2,，n(5.4)并設(shè)aii≠0(i=1,2,,n)，從第i個方程解出xi，得等價的方程組：k012345678x100.30000.80000.91800.97160.98040.99620.99850.9998x201.50001.76001.92601.97001.98971.99611.99861.9998x302.00002.66002.95402.95402.98232.99382.99772.9997

4迭代公式為：結(jié)束

i=1,2,,n(5.5)(5.6)這種迭代形式稱為簡單迭代法，也稱雅可比(Jacobi)迭代法.雅可比迭代法的矩陣迭代形式:(推導(dǎo))

5結(jié)束5.2.2塞德爾(Seidel)迭代法在簡單迭代法的迭代形式(5.6)中，可以看出，在計算

時，要使用.但此時已計算出來.看來此時可提前使用代替，一般地，計算(n≥i≥2)時，使用代替(i>p≥1)，這樣可能收斂會快一些，這就形成一種新的迭代法，稱為塞德爾迭代法。例2

用塞德爾迭代法計算例1并作比較.解迭代公式為：(k=0,1,2,)

6結(jié)束用它計算得到的序列{x(k)}列表如表5-2：可見它對這一方程組比簡單迭代法收斂快一些。塞德爾迭代法的公式如下：(5.9)

Seidel迭代法的矩陣迭代形式：（推導(dǎo)）

7k0123456x100.30000.88040.98430.99780.99971.0000x201.50001.94481.99221.99891.99982.0000x302.68402.95392.99382.99912.99993.0000結(jié)束5.2.3逐次超松弛法(SOR方法)逐次超松弛法可看成塞德爾迭代法的加速，塞德爾迭代法是逐次超松弛法的特例.將塞德爾迭代法的(5.9)式改寫為

8結(jié)束為加快收斂，在增量

前加一個因子，得稱此公式為逐次超松弛法(SOR法).從(5.13)式不難推出SOR方法的矩陣迭代形式：下面定理5.8可以看到，必須取0<ω<2，當(dāng)ω=1時，就是Seidel迭代法.當(dāng)ω取得適當(dāng)時，對塞德爾迭代法有加速效果.

9結(jié)束例3

用塞德爾迭代法和取ω=1.45的逐次超松弛法計算下列方程組的解，當(dāng)

時退出迭代，初值取x(0)=(1,1,1)T

。由表5-３和表5-４可見，達(dá)到同樣的精度Seidel迭代法要72步，而取ω=1.45的逐次超松弛法只要25步，可見當(dāng)松弛因子選擇適當(dāng)時，逐次超松弛法有明顯加速收斂作用，它常用于求解大型線性方程組。

10結(jié)束5.3迭代法的一般形式的收斂條件5.3.1一般迭代過程

在什么條件下收斂.定理5.1

對任意初始向量x(0)和f,

由上式產(chǎn)生的迭代序列x(k)收斂的充要條件是ρ(B)<1.證:1)必要性：

11結(jié)束2)充分性：定理5.1是迭代法收斂的基本定理，它不但能判別收斂，也能判別不收斂的情況.但由于ρ(B)的計算往往比解方程組本身更困難，所以本定理在理論上的意義大于在實用上的意義.從上面的定理可以看到，迭代法的收斂與否與B的性態(tài)有關(guān)，與初始向量x(0)和右端向量f無關(guān)。.由于ρ(B)難于計算，而由第二章定理4有ρ(B)≤||B||，||B||<1時，必有

ρ(B)<1，于是得到：

12結(jié)束定理5.2

若||B||=q<1，則由迭代格式x(k+1)=Bx(k)+f

和任意初始向量x(0)產(chǎn)生的迭代序列x(k)收斂于準(zhǔn)確解x*。本定理是迭代法收斂的充分條件，它只能判別收斂的情況，當(dāng)||B||≥1時，不能斷定迭代不收斂。但由于||B||,特別是||B||1和||B||∞的計算比較容易，也不失為一種判別收斂的方法。同時當(dāng)||B||<1時可以用來估計迭代的次數(shù)，或用來設(shè)置退出計算的條件。利用此定理可以在只計算出x(1)時，就估計迭代次數(shù)k，但估計偏保守，次數(shù)偏大.定理5.4

若||B||=q<1，則x(k)的第k次近似值的近似程度有如下估計式：本定理可用于程序中設(shè)置退出條件，即只要相鄰兩次的迭代結(jié)果之差足夠小時，迭代向量對精確解的誤差也足夠小.

13定理5.3

若||B||=q<1，則迭代格式x(k+1)=Bx(k)+f產(chǎn)生的向量序列

{x(k)}中結(jié)束例4

就例1中的系數(shù)陣A1和例3中的系數(shù)陣A2討論簡單迭代法和塞德爾迭代法的收斂性.因為||BJ||∞=0.6<1，由定理5.2知簡單迭代法收斂。解：1）就A1討論因為||BS||∞=0.3<1，由定理5.2知Seidel迭代法收斂。

14結(jié)束用定理5.2無法判斷簡單迭代法收斂性，現(xiàn)計算ρ(BJ)。2）就A2討論解之有三實根：λ1=0.9207,λ2=-0.2846,λ3

=-0.6361.所以ρ(BJ)=0.9207<1，故簡單迭代法收斂.

15結(jié)束||BS||∞=0.875，故塞德爾迭代法收斂.5.3.2從矩陣A判斷收斂的條件能否直接由矩陣A

的性態(tài)，討論Ax=b

使用迭代法是否收斂.討論前必須先介紹幾個概念：1.對角優(yōu)勢若A=(aij)n×n

滿足且至少有一個i值，使成立，稱A具有對角優(yōu)勢；

16結(jié)束若稱A具有嚴(yán)格對角優(yōu)勢.定理5.5

若A

具有嚴(yán)格對角優(yōu)勢，則A非奇異。2.不可約如果矩陣A能通過行對換和相應(yīng)的列對換，變成：的形式，其中A11和A22為方陣，則稱A

可約，反之稱A

不可約.定理5.6

A不可約，且具有對角優(yōu)勢，則A非奇異.以上兩個定理的證明要使用較多的數(shù)學(xué)知識，本書從略.定理5.7

A

具有嚴(yán)格對角優(yōu)勢或A

不可約且具有對角優(yōu)勢，則簡單迭代法和塞德爾迭代法都收斂.證明：

17定理5.8

逐次超松弛法收斂的必要條件是0<ω<2.例5

用定理5.5檢驗例1中方程組的矩陣A，判斷該方程組用迭代法時是否收斂？解因為

10│-2│+│-1│，10│-2│+│-1│，

5│-1│+│-2│，所以A具有嚴(yán)格對角優(yōu)勢，該方程組用簡單迭代法和塞德爾迭代法時收斂。結(jié)束

定理5.9

如果A實對稱正定，且0<ω<2，則逐次超松弛法收斂.推論:當(dāng)A實對稱正定時，Ax=b使用塞德爾迭代法收斂.最后提一下關(guān)于ω的選取，ω的選取影響ρ(Bω)的大小，使ρ(Bω)最小的ω值稱為最佳松弛因子，記為ω

opt.ω

opt的選取是一個復(fù)雜問題，尚無完善結(jié)果，只有針對一些特殊矩陣的結(jié)果，比如

18結(jié)束定理5.10

如A對稱正定，且是三對角陣，則其中BJ是簡單迭代法的迭代矩陣.

可見即使有估計公式，計算ρ(Bω)也是困難的，一般采取試算方法確定.加速收斂的效果也隨問題而異，對有的問題，可加速好幾十倍，甚至更多，對有的問題則加速不明顯.

1