第七章 線性代數(shù)方程組的迭代法

第七章線性方程組的迭代法§1迭代法基礎(chǔ)

問題

在實(shí)際應(yīng)用中遇到的系數(shù)矩陣多為大型稀疏矩陣，如用求解線性方程組的直接法求解，在計(jì)算機(jī)上會(huì)耗費(fèi)大量的時(shí)間和存儲(chǔ)單元。在許多應(yīng)用問題中使用迭代法。思路將改寫為等價(jià)形式，建立迭代,從初值出發(fā)，得到序列。研究?jī)?nèi)容：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？一般迭代法定義1

對(duì)方程組，化為等價(jià)方程組，設(shè)為任取的初值，將上式寫為迭代過程這種迭代過程稱為逐次逼近法，B稱為迭代矩陣。若稱逐次逼近法收斂，否則，稱逐次逼近法不收斂或發(fā)散。問題：按上述思想迭代產(chǎn)生的向量序列在什么條件下收斂于方程組Ax=b的解？引進(jìn)誤差向量：，其中為方程組的解，即有所以，要使收斂到，則需研究在什么條件下有。迭代法的收斂條件與誤差估計(jì)引理

當(dāng)k

時(shí)，Bk0

(B)<1定理1

設(shè)有線性方程組，那么逐次逼近法對(duì)任意初始向量收斂的充分必要條件是迭代矩陣B的譜半徑

(B)<1。注：要檢驗(yàn)一個(gè)矩陣的譜半徑小于1比較困難，

所以我們希望用別的辦法判斷收斂性。

注:1.因?yàn)榫仃嚪稊?shù)都可以直接用矩陣的元素計(jì)算，因此用定理2，很容易判別逐次逼近法的收斂性。

2.定理2是充分條件，當(dāng)找不到矩陣的某一范數(shù)小于1時(shí)，并不能判斷迭代法不收斂。①②定理2設(shè)線性方程組有惟一解，若存在一個(gè)矩陣范數(shù)使得||B||<1,

則迭代收斂,且有下列誤差估計(jì)：（7.1）

1．雅克比（Jacobi）迭代法設(shè)有n階方程組§2幾種常用的迭代法若系數(shù)矩陣非奇異，且

(i=1,2,…,n)，將方程組（7.1）改寫成然后寫成迭代格式（7.2）（7.2）式也可以簡(jiǎn)單地寫為（7.3）記,其中則雅克比迭代法的矩陣形式為：(7.4)稱為雅克比迭代矩陣。…………寫成矩陣形式：2．高斯――賽得爾(Gauss-Seidel)迭代法(7.5)(7.6)其中稱為高斯―賽得爾迭代矩陣。定理4n階矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要條件是

Jacobi迭代法的迭代矩陣滿足‖BJ‖∞<1。3．Jacobi迭代法和Gauss-Seidel迭代法的收斂性定理5

如果A是嚴(yán)格對(duì)角占優(yōu)矩陣，那么Jacobi和G－S迭代法都收斂。定理6若A是n階正定矩陣，那么G-S迭代法收斂。定理3n階矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣，則A非奇異，且所有對(duì)角元

。注意的問題（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩陣不同：BJ=D-1(L+U),BG-S=(D-L)-1U（2）Jacobi迭代法和Gauss-Seidel迭代法收斂性沒有必然的聯(lián)系。即當(dāng)Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)，Gauss-Seidel法也可能不收斂（3）Jacobi迭代和Gauss-Seidel迭代的特征方程：Jacobi迭代：Gauss-Seidel迭代：用Jacobi迭代法求解收斂，但用Gauss-Seidel法不收斂。BJ的特征值為0，0，0，BG－S的特征值為0，2，2（4）舉例：用Jacobi迭代法求解不收斂，但用Gauss-Seidel法收斂。系數(shù)矩陣A是正定矩陣，因此用Gauss-Seidel法收斂。線性方程組的系數(shù)矩陣為是嚴(yán)格對(duì)角占優(yōu)的，所以Jacobi和Gauss-Seidel迭代格式均收斂。（1）迭代（2）加速（7.7）即§3超松馳迭代法（SOR法）

（SequentialOver-Relaxation)矩陣形式：注：1.稱為超松弛迭代矩陣。

2.稱為松弛因子。

3.當(dāng)時(shí)，就是G-S迭代法；當(dāng)時(shí)，稱為低

松弛迭代法；當(dāng)時(shí)，稱為超松弛迭代法。4.SOR法也稱為G-S迭代法的一種加速方法。

5.研究SOR法就是需要找到最佳松弛因子，使得迭代過程的收斂速度最快，即。

6.在找最佳松弛因子之前，先要解決在什么范圍內(nèi)取值，才能保證SOR法收斂。定理7

對(duì)Ax=b,