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

第七線性代數(shù)方程組的迭代法第1頁(yè)，共32頁(yè)，2023年，2月20日，星期一問(wèn)題驅(qū)動(dòng)：絎架設(shè)計(jì)

絎架是能夠承受重負(fù)載的輕量結(jié)構(gòu)，在橋梁設(shè)計(jì)中，一個(gè)個(gè)絎架和可旋轉(zhuǎn)的支點(diǎn)連接起來(lái)，可以把力通過(guò)該絎架從一個(gè)節(jié)點(diǎn)傳到另一個(gè)節(jié)點(diǎn)。如圖7.1.1所示給出了一個(gè)4個(gè)支點(diǎn)的絎架，①，②，③和④都是支點(diǎn)。在左下角①是一個(gè)固定的點(diǎn)，絎架在右下角點(diǎn)④可以水平移動(dòng)量值。在支點(diǎn)③施加10000N的力，絎架的受力情況如圖所示由和給出。固定支點(diǎn)同時(shí)受到水平方向的力和垂直方向的力的作用，但移動(dòng)支點(diǎn)只受到垂直方向的力的作用。第2頁(yè)，共32頁(yè)，2023年，2月20日，星期一圖7.1.1絎架的受力分析圖第3頁(yè)，共32頁(yè)，2023年，2月20日，星期一

如果整個(gè)絎架處以平衡狀態(tài)，每個(gè)支點(diǎn)的合力應(yīng)為零向量，因此每個(gè)支點(diǎn)上力的水平分量和垂直分量之和都應(yīng)該為零。由此可得到一個(gè)如表7.1.1所示的線性方程組，該方程組中的系數(shù)矩陣中含有46個(gè)零元素，而僅有18個(gè)非零元素，通常把含有大量零元素的矩陣稱為稀疏矩陣，由于使用直接法求解這類方程組，會(huì)破壞系數(shù)矩陣的稀疏性，這種情況下一般采用迭代法求解方程組。表7.1.1支點(diǎn)水平分量垂直分量①②③④第4頁(yè)，共32頁(yè)，2023年，2月20日，星期一

問(wèn)題

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

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？一般迭代法第6頁(yè)，共32頁(yè)，2023年，2月20日，星期一迭代格式的構(gòu)造把矩陣A分裂為

則第7頁(yè)，共32頁(yè)，2023年，2月20日，星期一將上式寫為迭代過(guò)程這種迭代過(guò)程稱為逐次逼近法，B稱為迭代矩陣。收斂性定義：若稱逐次逼近法收斂，否則，稱逐次逼近法不收斂或發(fā)散。給定初值就得到向量序列第8頁(yè)，共32頁(yè)，2023年，2月20日，星期一問(wèn)題：定理1

任意給定初始向量x0，如果由逐次逼近法產(chǎn)生的向量序列收斂于向量x*，那么，x*是方程組x=Bx+g的解。證明：是否為方程組Ax=b的解？第9頁(yè)，共32頁(yè)，2023年，2月20日，星期一迭代法的收斂條件定理

當(dāng)k

時(shí)，Bk0(B)<1定理2

設(shè)線性方程組x=Bx+g有惟一解，那么逐次逼近法對(duì)任意初始向量X０收斂的充分必要條件是迭代矩陣B的譜半徑(B)<1。證明：因此，第10頁(yè)，共32頁(yè)，2023年，2月20日，星期一注：要檢驗(yàn)一個(gè)矩陣的譜半徑小于1比較困難，所以我們希望用別的辦法判斷收斂性。

定理3

若逐次逼近法的迭代矩陣滿足‖B‖<1，那么逐次逼近法收斂。Remark:因?yàn)榫仃嚪稊?shù)都可以直接用矩陣的元素計(jì)算，因此,用定理3，很容易判別逐次逼近法的收斂性。第11頁(yè)，共32頁(yè)，2023年，2月20日，星期一定理4

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

則迭代收斂，且有下列誤差估計(jì)：②①證明：②迭代法的誤差估計(jì)誤差表達(dá)式及收斂速度。停機(jī)準(zhǔn)則。第12頁(yè)，共32頁(yè)，2023年，2月20日，星期一①第13頁(yè)，共32頁(yè)，2023年，2月20日，星期一（4.1）

1．雅克比（Jacobi）迭代法設(shè)有n階方程組幾種常用的迭代格式第14頁(yè)，共32頁(yè)，2023年，2月20日，星期一若系數(shù)矩陣非奇異，且

(i=1,2,…,n)，將方程組（4.1）改寫成第15頁(yè)，共32頁(yè)，2023年，2月20日，星期一然后寫成迭代格式（4.2）（4.2）式也可以簡(jiǎn)單地寫為（4.3）第16頁(yè)，共32頁(yè)，2023年，2月20日，星期一寫成矩陣形式：A=LUDBJacobi迭代陣(4.4)第17頁(yè)，共32頁(yè)，2023年，2月20日，星期一第18頁(yè)，共32頁(yè)，2023年，2月20日，星期一第19頁(yè)，共32頁(yè)，2023年，2月20日，星期一Algorithm:JacobiIterativeMethodSolve.Givenaninitialapproximation.Input:thenumberofequationsandunknownsn;thematrixentriesa[][];theentriesb[];theinitialapproximationX0[];toleranceTOL;maximumnumberofiterationsMmax.Output:approximatesolutionX[]oramessageoffailure.Step1Setk=1;Step2While(kMmax)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?第20頁(yè)，共32頁(yè)，2023年，2月20日，星期一…………只存一組向量即可。寫成矩陣形式：BGauss-Seidel

迭代陣2．高斯――賽得爾(Gauss-Seidel)迭代法(4.5)(4.6)第21頁(yè)，共32頁(yè)，2023年，2月20日，星期一BG-SGauss-Seidel

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

第22頁(yè)，共32頁(yè)，2023年，2月20日，星期一定理5n階矩陣A是按行嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要條件是Jacobi迭代法的迭代矩陣滿足‖BJ‖∞<1.定理6n階矩陣A是按列嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要條件是Jacobi迭代法的迭代矩陣滿足‖BJ‖1<1.相關(guān)性質(zhì)第23頁(yè)，共32頁(yè)，2023年，2月20日，星期一

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

定理7

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

定理8

設(shè)A是不可約對(duì)角占優(yōu)矩陣，那么Jacobi迭代法與G－S迭代法都收斂.第24頁(yè)，共32頁(yè)，2023年，2月20日，星期一定理9

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

設(shè)A是有正對(duì)角元的n階對(duì)稱矩陣，那么Jacobi迭代法收斂的充分必要條件是A和2D-A同為正定矩陣.第25頁(yè)，共32頁(yè)，2023年，2月20日，星期一注意的問(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第26頁(yè)，共32頁(yè)，2023年，2月20日，星期一（3）Jacobi迭代和Gauss-Seidel迭代的特征方程：Jacobi迭代第27頁(yè)，共32頁(yè)，2023年，2月20日，星期一Gauss-Seidel迭代第28頁(yè)，共32頁(yè)，2023年，2月20日，星期一舉例用Jacobi迭代法求解不收斂，但用Gauss-Seidel法收斂。用Jacobi迭代法求解收斂，但用Gauss-Seidel法不收斂。

BJ的特征值為0，0，0，而BG－S的特征值為

0，2，2第29頁(yè)，共32頁(yè)，2023年，2月20日，星期一系數(shù)矩陣A是正定矩陣，因此用Gauss-Seidel法收斂.是正定矩陣，因此用

Jacob