第六章-解線性方程組的迭代法優(yōu)秀文檔

1第6章

解線性方程組的迭代法26.1迭代法的基本概念6.2Jacobi迭代法與Gauss-Seidel迭代法6.3超松弛迭代法6.4共軛梯度法3

迭代法的基本概念

考慮線性方程組（1.1）其中為非奇異矩陣，當(dāng)為低階稠密矩陣時(shí)，第5章所討論的選主元消去法是有效方法.

但對(duì)于的階數(shù)很大，零元素較多的大型稀疏矩陣方程組，例如求某些偏微分方程數(shù)值解所產(chǎn)生的線性方程組來說，利用迭代法求解則更為合適.

迭代法通常都可利用中有大量零元素的特點(diǎn).4

例1（1.2）記為,方程組的精確解是.求解方程組其中現(xiàn)將(1.2)改寫為5（1.3）或?qū)憺?其中有，(1)由基本定理4結(jié)論(1)是顯然的.將分裂為研究雅可比迭代法(2.任取初始值，例如取.問題是：迭代矩陣滿足什么條件時(shí)，由迭代法產(chǎn)生由于，當(dāng)時(shí)，有高斯-塞德爾迭代法6)式可知，雅可比迭代法計(jì)算公式簡(jiǎn)單，每迭代解大型稀疏線性方程組的逐次超松弛迭代法要考察的收斂性,就要研究在什么條件下有迭代法產(chǎn)生的向量序列不一定都能逐步逼近方程組如果個(gè)數(shù)列極限存在且有選取分裂矩陣為帶參數(shù)的下三角陣方程組，例如求某些偏微分方程數(shù)值解所產(chǎn)生的線性方程8)可知，高斯-塞德爾迭代法每迭代一次只需計(jì)算6

將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解，但一般不滿足).

任取初始值，例如取.再將分量代入(1.3)式右邊得到，反復(fù)利用這個(gè)計(jì)算程序，得到一向量序列和一般的計(jì)算公式(迭代公式)

得到新的值7（1.4）簡(jiǎn)寫為其中表示迭代次數(shù)

迭代到第10次有8

從此例看出，由迭代法產(chǎn)生的向量序列逐步逼近方程組的精確解.

對(duì)于任何由變形得到的等價(jià)方程組，迭代法產(chǎn)生的向量序列不一定都能逐步逼近方程組的解.

如對(duì)方程組9構(gòu)造迭代法則對(duì)任何的初始向量，得到的序列都不收斂.

對(duì)于給定方程組，設(shè)有唯一解，（1.5）又設(shè)為任取的初始向量，（1.6）其中表迭代次數(shù).則按下述公式構(gòu)造向量序列10

定義1(1)對(duì)于給定的方程組，逐步代入求近似解的方法稱為迭代法(或稱為一階定常迭代法，這里與無關(guān)).(2)如果存在(記為)，顯然就是方程組的解，否則稱此迭代法發(fā)散.用公式(1.6)稱此迭代法收斂，

研究的收斂性.

引進(jìn)誤差向量由(1.6)減去(1.5)式，得，11

要考察的收斂性,就要研究在什么條件下有亦即要研究滿足什么條件時(shí)有遞推得12Jacobi迭代法與Gauss-Seidel迭代法

設(shè)有（2.1）其中，為非奇異矩陣.

將分裂為（2.2）其中，為可選擇的非奇異矩陣，且使容易求解，一般選擇為的某種近似，稱為分裂矩陣.13

于是，求解轉(zhuǎn)化為求解，即求解可構(gòu)造一階定常迭代法（2.3）其中稱為迭代法的迭代矩陣.14

選取陣，就得到解的各種迭代法.

設(shè),并將寫為三部分（2.4）15

雅可比迭代法

由，選取為的對(duì)角元素部分，解的雅可比(Jacobi)迭代法即選取(對(duì)角陣)，，（2.5）其中

稱為解的雅可比迭代法的迭代陣.由(2.3)式得到16

研究雅可比迭代法(2.5)的分量計(jì)算公式.記由雅可比迭代公式(2.5),有或于是，解的雅可比迭代法的分量計(jì)算公式為17（2.6）

由(2.6)式可知，雅可比迭代法計(jì)算公式簡(jiǎn)單，每迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)算過程中原始矩陣始終不變.18(下三角陣)，

高斯-塞德爾迭代法

選取分裂矩陣為的下三角部分，即選取于是由(2.3)式得到解（2.7）其中稱為解的高斯-塞德爾迭代法的迭代陣.的高斯-塞德爾(Gauss-Seidel)迭代法19

研究高斯-塞德爾迭代法的分量計(jì)算公式.由(2.7)式有或即記20于是解的高斯-塞德爾迭代法計(jì)算公式為（2.8）或（2.9）21而由高斯-塞德爾迭代公式可知，

雅可比迭代法不使用變量的最新信息計(jì)算，計(jì)算的第個(gè)分量

時(shí)，利用了已經(jīng)計(jì)算出的最新分量.

由(2.8)可知，高斯-塞德爾迭代法每迭代一次只需計(jì)算一次矩陣與向量的乘法.高斯-塞德爾迭代法可看作雅可比迭代法的一種改進(jìn).

算法1(高斯-塞德爾迭代法)

設(shè)，其中為非奇異矩陣且本算法用高斯-塞德爾迭代法解，22

迭代一次，這個(gè)算法需要的運(yùn)算次數(shù)至多與矩陣的非零元素的個(gè)數(shù)一樣多.數(shù)組開始存放,后存放為最大迭代次數(shù).23

例2按高斯-塞德爾迭代公式迭代7次，得，（1.2）用高斯-塞德爾迭代法解線性方程組(1.2).取，24

由此例可知，用高斯-塞德爾迭代法，雅可比迭代法解線性方程組(1.2)(且取)均收斂.

而高斯-塞德爾迭代法比雅可比迭代法收斂較快(即取相同，達(dá)到同樣精度所需迭代次數(shù)較少).

但這結(jié)論只當(dāng)滿足一定條件時(shí)才是對(duì)的.且25

解大型稀疏線性方程組的逐次超松弛迭代法

選取分裂矩陣為帶參數(shù)的下三角陣其中為可選擇的松弛因子.

于是，由(2.3)可構(gòu)造一個(gè)迭代法，其迭代矩陣為從而得到解的逐次超松弛迭代法(SuccessiveOverRelaxationMethod,簡(jiǎn)稱SOR方法).

逐次超松弛迭代法26

解的SOR方法為（2.10）其中

研究解的SOR迭代法的分量計(jì)算公式.記27或由(2.10)式可得由此，得到解的SOR方法的計(jì)算公式（2.11）28或（2.12）

關(guān)于SOR迭代法，有(1)顯然，當(dāng)時(shí)，SOR方法即為高斯-塞德爾迭代法.29(2)SOR方法每迭代一次主要運(yùn)算量是計(jì)算一次矩陣與向量的乘法.(3)當(dāng)時(shí)，稱為超松弛法；當(dāng)時(shí)，稱為低松弛法.(4)在計(jì)算機(jī)實(shí)現(xiàn)時(shí)可用控制迭代終止，或用控制迭代終止.

SOR迭代法是高斯-塞德爾迭代法的一種修正.30

設(shè)已知及已計(jì)算的分量(1)首先用高斯-塞德爾迭代法定義輔助量（2.13）(2)再由與加權(quán)平均定義，將(2.13)代入(2.14)得到解的SOR迭代(2.11)式.即（2.14）31

例3它的精確解為取，迭代公式為用SOR方法解方程組解32取，取其他值，迭代次數(shù)如下表.第11次迭代結(jié)果為33

從此例看到，松弛因子選擇得好，會(huì)使SOR迭代法的收斂大大加速.本例中是最佳松弛因子.34

迭代法的收斂性

一階定常迭代法的基本定理

設(shè)（3.1）其中為非奇異矩陣，記為(3.1)精確解，于是（3.2）且設(shè)有等價(jià)的方程組35

設(shè)有解的一階定常迭代法（3.3）

問題是：迭代矩陣滿足什么條件時(shí)，由迭代法產(chǎn)生的向量序列收斂到

引進(jìn)誤差向量由(3.3)式減(3.2)式得到誤差向量的遞推公式36

由節(jié)可知，研究迭代法(3.3)收斂性問題就是要研究迭代矩陣滿足什么條件時(shí)，有

定義2設(shè)有矩陣序列及,如果個(gè)數(shù)列極限存在且有則稱收斂于，記為37

例4且設(shè)，考查其極限.

解由于，當(dāng)時(shí)，有設(shè)有矩陣序列所以38

矩陣序列極限概念可以用矩陣算子范數(shù)來描述.

定理1

證明再利用矩陣范數(shù)的等價(jià)性，可證定理對(duì)其他算子范數(shù)亦對(duì).

定理2

對(duì)任何向量都有其中‖·‖為矩陣的任意一種算子范數(shù).顯然有（證明略）控制迭代終止，或用控制迭代組來說，利用迭代法求解則更為合適.其中‖·‖為矩陣的任意一種算子范數(shù).由，選取為的對(duì)角元素部分，問題是：迭代矩陣滿足什么條件時(shí)，由迭代法產(chǎn)生取，(2)由關(guān)系式及亦即要研究滿足什么條件時(shí)有本例中是最佳松弛因子.雅可比迭代法設(shè),并將寫為三部分如果個(gè)數(shù)列極限存在且有即選取(對(duì)角陣)，，于是，解的雅可比迭代法的分量計(jì)算公式為如果個(gè)數(shù)列極限存在且有亦即要研究滿足什么條件時(shí)有按下述公式構(gòu)造向量序列39

定理3設(shè),則(零矩陣)的充分必要條件是矩陣的譜半徑

證明由矩陣的若當(dāng)標(biāo)準(zhǔn)型，存在非奇異矩陣使其中若當(dāng)塊40且，其中于是

下面考查的情況.顯然有引進(jìn)記號(hào)41

顯然有，由于,

因此42其中利用極限，所以的充要條件是，得到即43

定理4（3.4）(迭代法基本定理)設(shè)有方程組及一階定常迭代法（3.5）對(duì)任意選取初始向量，矩陣的譜半徑迭代法(3.5)收斂的充要條件是

證明設(shè)，易知)有唯一解，記為，充分性.(其中則44誤差向量由設(shè)，應(yīng)用定理3，有

于是對(duì)任意,有，

必要性.設(shè)對(duì)任意有其中即

顯然，極限是方程組(3.4)的解，且對(duì)任意有45由定理2知再由定理3，即得

推論設(shè)，其中為非奇異矩陣且非奇異，則(1)解方程組的雅可比迭代法收斂的充要條件是，其中(2)解方程組的高斯-塞德爾迭代法收斂的充要條件是其中(3)解方程組的SOR方法收斂的充要條件是，其中或?qū)憺?(3)考查按下述公式構(gòu)造向量序列亦即要研究滿足什么條件時(shí)有本例中是