數(shù)值積分（基于MATLAB）課件 chapter3 線性代數(shù)方程組的迭代法

第3章3.5迭代法迭代法基礎(chǔ)

問(wèn)題

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

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？一般迭代法迭代格式的構(gòu)造把矩陣A分裂為

則將上式寫(xiě)為迭代過(guò)程這種迭代過(guò)程稱為逐次逼近法，B稱為迭代矩陣。收斂性定義：若稱逐次逼近法收斂，否則，稱逐次逼近法不收斂或發(fā)散。給定初值就得到向量序列問(wèn)題：定理1

任意給定初始向量x0，如果由逐次逼近法產(chǎn)生的向量序列收斂于向量x*，那么，x*是方程組x=Bx+g的解。證明：是否為方程組Ax=b的解？迭代法的收斂條件定理

當(dāng)k

時(shí)，Bk0

(B)<1定理2

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

(B)<1。

證明：因此，注：要檢驗(yàn)一個(gè)矩陣的譜半徑小于1比較困難，所以我們希望用別的辦法判斷收斂性。

定理3

若逐次逼近法的迭代矩陣滿足‖B‖<1，那么逐次逼近法收斂。Remark:因?yàn)榫仃嚪稊?shù)都可以直接用矩陣的元素計(jì)算，因此,用定理3，很容易判別逐次逼近法的收斂性。第3章3.6迭代法的收斂性定理3.3

（充分條件）若存在一個(gè)矩陣范數(shù)使得||B||<1,

則迭代收斂，且有下列誤差估計(jì)：②①證明：②迭代法的誤差估計(jì)誤差表達(dá)式及收斂速度。停機(jī)準(zhǔn)則。①（1）

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

(i=1,2,…,n)，將方程組（1）改寫(xiě)成然后寫(xiě)成迭代格式（2）（2）式也可以簡(jiǎn)單地寫(xiě)為（3）寫(xiě)成矩陣形式：A=LUDBJacobi迭代陣(4)Algorithm:JacobiIterativeMethodSolve.Givenaninitialapproximation.Input:thenumberofequationsandunknownsn;thematrixentriesa[][];theentriesb[];theinitialapproximationX0[];toleranceTOL;maximumnumberofiterationsMmax.Output:approximatesolutionX[]oramessageoffailure.Step1Setk=1;Step2While(k

Mmax)dosteps3-6

Step3Fori=1,…,n

Set;/*computexk*/

Step4IfthenOutput(X[]);STOP;/*successful*/

Step5Fori=1,…,nSetX0[]=X[];/*updateX0*/

Step6Setk++;Step7Output(Maximumnumberofiterationsexceeded);STOP./*unsuccessful*/Whatifaii

=0?迭代過(guò)程中，A

的元素不改變，故可以事先調(diào)整好A

使得aii

0，否則

A不可逆。必須等X(k)完全計(jì)算好了才能計(jì)算X(k+1)，因此需要兩組向量存儲(chǔ)。Abitwasteful,isn’tit?…………只存一組向量即可。寫(xiě)成矩陣形式：BGauss-Seidel

迭代陣2．高斯――賽得爾(Gauss-Seidel)迭代法(5)(6)BG-SGauss-Seidel

迭代陣其迭代格式的矩陣形式為事實(shí)上，這相當(dāng)于對(duì)系數(shù)矩陣A作的另一個(gè)分裂：

定理5n階矩陣A是按行嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要條件是Jacobi迭代法的迭代矩陣滿足‖BJ‖∞<1.定理6n階矩陣A是按列嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要條件是Jacobi迭代法的迭代矩陣滿足‖BJ‖1<1.相關(guān)性質(zhì)

Jacobi迭代法和Gauss-Seidel迭代法的收斂性

定理7

如果A是按行(列)嚴(yán)格對(duì)角占優(yōu)的矩陣，那么Jacobi和G－S迭代法都收斂.

定理8

設(shè)A是不可約對(duì)角占優(yōu)矩陣，那么Jacobi迭代法與G－S迭代法都收斂.定理9

若A是n階正定矩陣，那么，G-S迭代法收斂.定理10

設(shè)A是有正對(duì)角元的n階對(duì)稱矩陣，那么Jacobi迭代法收斂的充分必要條件是A和2D-A同為正定矩陣.注意的問(wèn)題（2）Jacobi迭代法和Gauss-Seidel迭代法的收斂性沒(méi)有必然的聯(lián)系：即當(dāng)Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)，Gauss-Seidel法也可能不收斂。（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩陣不同：BJ=D-1(L+U),BG-S=(D-L)-1U（3）Jacobi迭代和Gauss-Seidel迭代的特征方程：Jacobi迭代Gauss-Seidel迭代舉例用Jacobi迭代法求解不收斂，但用Gauss-Seidel法收斂。用Jacobi迭代法求解收斂，但用Gauss-Seidel法不收斂。

BJ的特征值為0，0，0，而B(niǎo)