第三章線性方程組的迭代解法第一頁，共二十三頁，編輯于2023年，星期四任取一個向量x(0)作為x的近似解，用迭代公式則有x*=Bx*+f，即x*是(3.2)的解，當然x*也就是Ax=b的解.1如何構造迭代公式x(k+1)=Bx(k)+f.這樣的構造形式不止一種，它們各對應一種迭代法.2迭代法產生的向量序列{x(k)}的收斂條件是什么，收斂速度如何.結束

2從以上的討論中，可以看出，迭代法的關鍵有：x(k+1)=Bx(k)+f,(k=0,1,2,)(3.3)產生一個向量序列{x(k)}，若第二頁，共二十三頁，編輯于2023年，星期四先看一個算例：按下式進行迭代

(k=0,1,2,)結束

33.2幾種常用的迭代法公式例13.2.1Jacobi迭代法從以上三個方程中分別解出x1,x2,x3第三頁，共二十三頁，編輯于2023年，星期四任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列{x(k)}(k=0,1,2,)，列表如下表3-1。容易驗證，原方程組的精確解為x=(1,2,3)T，從上面的計算可看出，{x(k)}收斂于精確解.一般說來，對方程組：設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第四頁，共二十三頁，編輯于2023年，星期四迭代公式為：

i=1,2,,n(3.5)(3.6)這種迭代形式稱為Jacobi迭代法(雅可比迭代法)，也稱簡單迭代法.Jacobi迭代法的矩陣迭代形式:(推導)結束

5其中第五頁，共二十三頁，編輯于2023年，星期四3.2.2Gauss-Seidel迭代法在Jacobi迭代法的迭代形式(3.6)中，可以看出，在計算時，要使用.但此時已計算出來.看來此時可提前使用代替，一般地，計算(n≥i≥2)時，使用代替(i>p≥1)，這樣可能收斂會快一些，這就形成一種新的迭代法，稱為Gauss-Seidel迭代法。例2用Gauss-Seidel迭代法計算例1并作比較.(k=0,1,2,)結束

6解迭代公式為：第六頁，共二十三頁，編輯于2023年，星期四用它計算得到的序列{x(k)}列表如表3-2：可見它對這一方程組比Jacobi迭代法收斂快一些。Gauss-Seidel迭代法的公式如下：(3.9)Gauss-Seidel迭代法的矩陣迭代形式：（推導）k0123456x100.30000.88040.98430.99780.99971.0000x201.50001.94481.99221.99891.99982.0000x302.68402.95392.99382.99912.99993.0000結束

7其中第七頁，共二十三頁，編輯于2023年，星期四SOR迭代法也稱為逐次超松弛法，它可看成Gauss-Seidel迭代法的加速，Gauss-Seidel迭代法是SOR迭代法的特例.改寫為結束

83.2.3SOR迭代法將Gauss-Seidel迭代法的(3.9)式記則第八頁，共二十三頁，編輯于2023年，星期四為加快收斂，在增量前加一個因子,得稱此公式為SOR法(逐次超松弛法).從(3.13)式不難推出SOR法的矩陣迭代形式：今后可以看到，必須取0<ω<2，當ω=1時,就是Gauss-Seidel迭代法.當ω取得適當時，對Gauss-Seidel迭代法有加速效果.結束

9其中改寫為第九頁，共二十三頁，編輯于2023年，星期四例3用Gauss-Seidel迭代法和取ω=1.45的SOR法計算下列方程組的解，當時退出迭代，初值取x(0)=(1,1,1)T。由表３-３和表３-４可見，達到同樣的精度Gauss-Seidel迭代法要72步，而取ω=1.45的SOR法只要25步，可見當松弛因子選擇適當時，SOR法有明顯加速收斂作用，它常用于求解大型線性方程組。結束

10第十頁，共二十三頁，編輯于2023年，星期四3.3迭代法的一般形式的收斂條件定理3.1

對任意初始向量x(0)和f,由上式產生的迭代序列x(k)收斂的充要條件是ρ(B)<1.3.3.1一般迭代過程的收斂條件.結束

11證:1)必要性：x(k)收斂于x*,有x*=Bx*+f成立,記k=x(k)-

x*有k+1=x(k+1)-

x*

=Bx(k)+f-Bx*-f=B(x(k)

-x*)=Bk有k+1=Bk=B2k-1=…=Bk+10,這里0=x(0)-

x*,對任意的x(0)

,0=x(0)-

x*

也是任意的,因此要有Bk+100(k),必須有Bk0(k)由上章定理2.8,必有(B)<1.第十一頁，共二十三頁，編輯于2023年，星期四2)充分性：定理3.1是迭代法收斂的基本定理，它不但能判別收斂，也能判別不收斂的情況.但由于ρ(B)的計算往往比解方程組本身更困難，所以本定理在理論上的意義大于在實用上的意義.結束

12從上面的定理可以看到,迭代法的收斂與否與B的性態有關，而與初始向量x(0)和右端向量f無關.由于ρ(B)難于計算，而由定理2.7有ρ(B)≤||B||，||B||<1時,必有ρ(B)<1，于是得到：設(B)<1,則1不是B的特征值,有|I-B|0,于是(I-B)x=f有唯一解

,

記為x*,即有x*=Bx*+f成立,則k+1=B(x(k)

-x*)=Bk

仍成立,k+1=Bk+10仍成立,因此k+1

0(k)成立,也即是x(k)

x*(k)由上章定理2.8,由(B)<1,可得Bk+10(k)成立,第十二頁，共二十三頁，編輯于2023年，星期四定理3.2

若||B||=q<1，則由迭代格式x(k+1)=Bx(k)+f和任意初始向量x(0)產生的迭代序列x(k)收斂于準確解x*.本定理是迭代法收斂的充分條件，它只能判別收斂的情況，當||B||≥1時,不能斷定迭代不收斂.但由于||B||,特別是||B||1和||B||∞的計算比較容易，也不失為一種判別收斂的方法。利用此定理可以在只計算出x(1)時，就估計迭代次數k，但估計偏保守，次數偏大.稱為事前誤差估計.定理3.3若||B||=q<1，則迭代格式x(k+1)=Bx(k)+f產生的向量序列{x(k)}中結束

13同時當||B||<1時可以用來估計迭代的次數，或用來設置退出計算的條件.這時有定理3.3和定理3.4第十三頁，共二十三頁，編輯于2023年，星期四例4就例1中的系數陣A1和例3中的系數陣A2討論Jacobi迭代法和Gauss-Seidel迭代法的收斂性.因為||BJ||∞=0.6<1，由定理3.2知Jacobi迭代法收斂。解：1）就A1討論結束

14定理3.4若||B||=q<1，則x(k)的第k次近似值的近似程度有如下估計式：本定理可用于程序中設置退出條件，即只要相鄰兩次的迭代結果之差足夠小時，迭代向量對精確解的誤差也足夠小.稱為事后誤差估計.第十四頁，共二十三頁，編輯于2023年，星期四用定理3.2無法判斷Jacobi迭代法收斂性，現計算ρ(BJ)。2）就A2討論解之有三實根：λ1=0.9207,λ2=-0.2846,λ3=-0.6361.所以ρ(BJ)=0.9207<1，故Jacobi迭代法收斂.結束

15因為||BS||∞=0.3<1，由定理3.2知Gauss-Seidel迭代法收斂。第十五頁，共二十三頁，編輯于2023年，星期四||BS||∞=0.875，故Gauss-Seidel迭代法收斂.3.3.2從矩陣A判斷收斂的條件下面討論直接由矩陣A的性態,判定Ax=b使用迭代法是否收斂.討論前必須先介紹幾個概念：1對角優勢若A=(aij)n×n滿足且至少有一個I值，使成立,稱A具有對角優勢；結束

16第十六頁，共二十三頁，編輯于2023年，星期四若稱A具有嚴格對角優勢.定理3.5若A具有嚴格對角優勢，則A非奇異。定理3.6

A不可約，且具有對角優勢，則A非奇異.結束

172不可約如果矩陣A能通過行對換和相應的列對換，變成：矩陣

A是否可約是不易判別的，但以下兩條準則比較常用:A沒有零元素或零元素太少(少于n-1)時不可約;三對角陣如果三條對角線上的元素都不為零時不可約.的形式,其中A11和A22為方陣,則稱A可約,反之稱A不可約.第十七頁，共二十三頁，編輯于2023年，星期四例5用定理3.7檢驗例1中方程組的矩陣A，判斷該方程組用迭代法時是否收斂？解因為10│-2│+│-1│，10│-2│+│-1│，5│-1│+│-2│，結束

18定理3.7

A具有嚴格對角優勢或A不可約且具有對角優勢，則Jacobi迭代法和Gauss-Seidel迭代法都收斂.證明所以A具有嚴格對角優勢，該方程組用Jacobi迭代法和Gauss-Seidel迭代法時收斂.第十八頁，共二十三頁，編輯于2023年，星期四定理3.8逐次超松弛法收斂的必要條件是0<ω<2.

定理3.9如果A實對稱正定，且0<ω<2，則SOR法收斂.推論:當A實對稱正定時，Ax=b使用Gauss-Seidel迭代法收斂.

注意A實對稱正定時,Jacobi法并不一定收斂，這時有結論:

定理3.10如果A實對稱,且對角元全為正,且A和2D-A均正定，則Jacobi迭代法收斂.第十九頁，共二十三頁，編輯于2023年，星期四可見即使有估計公式，計算ρ(