第6章 線性方程組的迭代法

第六章解線性方程組的迭代法1.雅可比（Jacobi）迭代法2.高斯-塞德爾(Gauss-Seidel)迭代法3.超松弛迭代法（SOR方法）4.迭代法的收斂性2023/2/41

迭代法就是用某種極限過程去逐步逼近方程精確解的方法。

迭代法程序設(shè)計(jì)簡(jiǎn)單，適于自動(dòng)計(jì)算，且較直接法更少的計(jì)算量，但迭代法都要考慮是否收斂和收斂速度問題。迭代法是求解線性方程組，尤其是求解大型稀疏矩陣對(duì)應(yīng)方程組的重要方法之一。解線性方程組的迭代法2023/2/42

迭代法的基本思想是將線性方程組轉(zhuǎn)化為便于迭代的等價(jià)方程組，對(duì)任選一組初始值

，

按某種計(jì)算規(guī)則，不斷地對(duì)所得到的值進(jìn)行修正，最終獲得滿足精度要求的方程組的近似解。

收斂向量序列解向量§6.1迭代法的基本思想2023/2/43設(shè)非奇異,，將線性方程組變換為一個(gè)等價(jià)同解方程組即將上式改寫成迭代式如果(2)式求極限得即是(1)式的解2023/2/44這種方法稱為迭代法。迭代格式選定初始向量代入迭代格式，反復(fù)不斷地使用，逐步逼近方程組的精確解,直到滿足精度要求為止接下來的問題就是迭代矩陣G

的構(gòu)造法。2023/2/45§6.2雅可比（Jacobi）迭代法考察一般的n元線性方程組2023/2/46§6.2雅可比（Jacobi）迭代法2023/2/47雅可比迭代法公式的分量形式為：2023/2/48求出對(duì)角線上的2023/2/49據(jù)此建立迭代公式稱為解方程組的Jacobi迭代公式。或2023/2/410例1用雅可比迭代法求解方程組

解：從方程組中分離出x1，x2和

x32023/2/411建立迭代公式取初始向量進(jìn)行迭代,可以逐步得出一個(gè)近似解的序列：2023/2/412計(jì)算表計(jì)算結(jié)果表明，此迭代過程收斂于方程組的精確解x*=(1.1,1.2,1.3)T。直到求得的近似解能達(dá)到預(yù)先要求的精度則迭代過程終止，2023/2/413例2用迭代法求解線性方程組

或構(gòu)造方程組的等價(jià)方程組據(jù)此建立迭代公式對(duì)于給定的方程組可以構(gòu)造各種迭代公式。并非全部收斂,例如：

Jacobi迭代公式。2023/2/414例2用迭代法求解線性方程組

建立迭代公式取迭代解離精確解越來越遠(yuǎn)

迭代不收斂計(jì)算得

2023/2/415§6.2.2

雅可比迭代法的矩陣表示

上面介紹的雅可比迭代公式是實(shí)際計(jì)算中經(jīng)常使用的用分量形式表示的公式。設(shè)方程組

的系數(shù)矩陣A非奇異，且主對(duì)角元素

，則可將A分裂成為了討論雅可比迭代法的收斂性，需介紹的雅可比迭代法的矩陣形式。2023/2/416§6.2.2

雅可比迭代法的矩陣表示記作A=D-L-U2023/2/417則等價(jià)于即這樣便得到一個(gè)迭代公式令則有稱為雅可比迭代公式,B

稱為雅可比迭代矩陣2023/2/418則有2023/2/4192023/2/4206.2.1雅可比迭代法的算法實(shí)現(xiàn)2023/2/421§6.3高斯-塞德爾(Gauss-Seidel)迭代法§6.3.1

高斯-塞德爾迭代法的基本思想

在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求時(shí)用已經(jīng)求出的新分量代替舊分量,就得到高斯-賽德爾迭代法。2023/2/422高斯-塞德爾迭代法公式的分量形式。即(k=0,1,2,…)2023/2/423高斯-賽德爾迭代法迭代法格式簡(jiǎn)寫為：

(i=1,2,…,n，k=0,1,2,…)2023/2/424例3用GaussSeidel迭代格式解方程組

精度要求為ε=0.005

解Jacobi

迭代格式為取初始迭代向量,迭代結(jié)果為：

GaussSeidel

迭代格式為2023/2/4252023/2/426§

6.3.2Gauss—Seidel

迭代法的矩陣表示將A分裂成A=D-L-U，則Ax=b

等價(jià)于

(D-L-U)x=b

則高斯-塞德爾迭代形式為：

故

令因?yàn)?/p>

,所以

于是,則高斯—塞德爾迭代過程2023/2/427§

6.3.2Gauss—Seidel

迭代法的矩陣表示

則高斯-塞德爾迭代形式為：

2023/2/428§

6.3.3高斯—塞德爾迭代算法實(shí)現(xiàn)高斯-塞德爾迭代算法的計(jì)算步驟與流程圖與雅可比迭代法大致相同，只是一旦求出變?cè)哪硞€(gè)新值后,就改用新值替代老值,進(jìn)行這一步剩下的計(jì)算。

2023/2/429§6.4超松弛迭代法（SOR方法）

使用迭代法的困難在于難以估計(jì)其計(jì)算量。有時(shí)迭代過程雖然收斂，但由于收斂速度緩慢，使計(jì)算量變得很大而失去使用價(jià)值。因此，迭代過程的加速具有重要意義。逐次超松弛迭代法（SuccessiveOverRelaxaticMethod，簡(jiǎn)稱SOR方法），可以看作是帶參數(shù)的高斯—塞德爾迭代法，實(shí)質(zhì)上是高斯-塞德爾迭代的一種加速方法。

2023/2/430

超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯—塞德爾迭代公式的基礎(chǔ)上作一些修改。這種方法是將前一步的結(jié)果與高斯-塞德爾迭代方法的迭代值

適當(dāng)加權(quán)平均，期望獲得更好的近似值

。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應(yīng)用?！?.4.1超松弛迭代法的基本思想2023/2/431合并表示為：SOR方法具體計(jì)算公式如下：⑴用高斯—塞德爾迭代法計(jì)算⑵把

取為

與

的加權(quán)平均，即

前后兩次迭代結(jié)果加權(quán)平均2023/2/432式中系數(shù)ω稱為松弛因子，當(dāng)ω=1時(shí)，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0<ω<2。當(dāng)0<ω<1時(shí)，低松弛法；當(dāng)1<ω<2時(shí)稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。2023/2/433§

6.4.2超松弛迭代法的矩陣表示設(shè)線性方程組

Ax=b的系數(shù)矩陣A非奇異,且主對(duì)角元素

,

則將A分裂成A=d-L-U,則超松弛迭代公式用矩陣表示為或故

2023/2/434§

6.4.2超松弛迭代法的矩陣表示顯然對(duì)任何一個(gè)ω值,(D-ωL)非奇異,(因?yàn)榧僭O(shè)

)

于是超松弛迭代公式為令則超松弛迭代公式可寫成2023/2/435例4用SOR法求解線性方程組

取ω=1.46，要求

解：SOR迭代公式

k=0,1,2,…，

初值2023/2/436該方程組的精確解只需迭代20次便可達(dá)到精度要求.如果取ω=1(即高斯—塞德爾迭代法)和同一初值,要達(dá)到同樣精度,需要迭代110次.2023/2/437§

6.5迭代法的收斂性我們知道,對(duì)于給定的方程組可以構(gòu)造成簡(jiǎn)單迭代、雅可比迭代、高斯-塞德爾迭代和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。在什么條件下迭代序列收斂？經(jīng)過等價(jià)變換構(gòu)造出的等價(jià)方程組

對(duì)于方程組得到迭代序列2023/2/438§5.7向量和矩陣的范數(shù)

向量范數(shù)是用來度量向量長(zhǎng)度的,它可以看作是解析幾何中二、三維向量長(zhǎng)度概念的推廣。用Rn表示n維實(shí)向量空間。為了研究線性方程組近似解的誤差和迭代法的收斂性,有必要對(duì)向量及矩陣的“大小”引進(jìn)某種度量----范數(shù)的概念。2023/2/439記筆記定義5.2

對(duì)任一向量XRn,按照一定規(guī)則確定一個(gè)實(shí)數(shù)與它對(duì)應(yīng),該實(shí)數(shù)記為||X||,若||X||滿足下面三個(gè)性質(zhì):則稱該實(shí)數(shù)||X||為向量X的范數(shù)(1)||X||0；||X||=0當(dāng)且僅當(dāng)X=0；(2)對(duì)任意實(shí)數(shù)，||X||=||||X||；(3)對(duì)任意向量YRn，||X+Y||||X||+||Y||2023/2/440在Rn中，常用的幾種向量范數(shù)有：記筆記其中x1,x2,…,xn分別是X的第n個(gè)分量,以上定義的范數(shù)分別稱為

-范數(shù)，1-范數(shù)和2-范數(shù).可以驗(yàn)證它們都是滿足范數(shù)性質(zhì)的，其中是由內(nèi)積導(dǎo)出的向量范數(shù)。2023/2/441定理5.1對(duì)于任意向量x,有即

當(dāng)p→∞，

證:其中2023/2/442當(dāng)不需要指明使用哪一種向量范數(shù)時(shí)，就用記號(hào)||.||泛指任何一種向量范數(shù)。有了向量的范數(shù)就可以用它來衡量向量的大小和表示向量的誤差。設(shè)x*為Ax=b的精確解，x為其近似解，則其絕對(duì)誤差可表示成||x-x*||，其相對(duì)誤差可表示成記筆記或2023/2/4432023/2/444例5.11設(shè),計(jì)算

解:2023/2/445定義5.4(向量序列的極限)設(shè)為中的一向量序列，,記。如果(i=1,2,…,n)，則稱收斂于向量，記為

定理5.2（向量范數(shù)的等價(jià)性）設(shè)

為

上任意兩種向量范數(shù),則存在常數(shù)

C1,,C2>0,

使得對(duì)任意

恒有（證:略）

2023/2/446定理5.3

其中為向量中的任一種范數(shù)。證由于對(duì)于上的任一種范數(shù),由定理5.2知存在常數(shù)C1，C2，使于是可得從而定理得證。2023/2/447定義5.5（矩陣的范數(shù)）如果矩陣的某個(gè)

非負(fù)的實(shí)值函數(shù)，滿足則稱是上的一個(gè)矩陣范數(shù)(或模)(相容性)2023/2/448矩陣范數(shù)通常要求滿足與向量范數(shù)相容即：于是矩陣范數(shù)可由向量范數(shù)定義這樣定義的矩陣范數(shù)稱為由向量范數(shù)導(dǎo)出的矩陣范數(shù)2023/2/449矩陣范數(shù)的計(jì)算公式定理8對(duì)n

階方陣(矩陣A的行范數(shù))(矩陣A的列范數(shù))(矩陣A的2-范數(shù))2023/2/450(矩陣A的行范數(shù))(每行絕對(duì)值相加化為列向量的范數(shù))2023/2/451證明：2023/2/452例5.12計(jì)算方陣

的三種范數(shù)

解2023/2/453例5.12計(jì)算方陣

的三種范數(shù)

解先計(jì)算

所以從而

2023/2/454定義5.7（矩陣的譜半徑）設(shè)的特征值為,稱為A的譜半徑。定理5.8設(shè)A為n階方陣,則對(duì)任意矩陣范數(shù)都有2023/2/455定理5.8設(shè)A為n階方陣,則對(duì)任意矩陣范數(shù)都有由于x≠0，故，所以證:設(shè)為A的特征值，x是對(duì)應(yīng)于的特征向量,則兩端取范數(shù)并依據(jù)其性質(zhì)得因此討論A的特征值與范數(shù)的關(guān)系2023/2/456矩陣范數(shù)是矩陣譜半徑的上界對(duì)稱矩陣的譜半徑恰好等于矩陣的2范數(shù)2023/2/457定理1其中為矩陣的任一范數(shù)。定理22023/2/458證:必要性由于可以是任意向量,故收斂于0當(dāng)且僅當(dāng)收斂于零矩陣，即當(dāng)時(shí)，

基本定理5

迭代公式收斂的充要條件是迭代矩陣G

的譜半徑則在迭代公式兩端同時(shí)取極限得設(shè)迭代公式收斂,當(dāng)k→∞時(shí),2023/2/459充分性:設(shè),則必存在正數(shù)ε,使則存在某種范數(shù)

,使,由此定理可知，不論是雅可比迭代法、高斯—塞德爾迭代法還是超松弛迭代法，它們收斂的充要條件都是其迭代矩陣的譜半徑2023/2/460前例2用迭代法求解線性方程組

構(gòu)造的等價(jià)方程組據(jù)此建立迭代公式

并非所有迭代公式都收斂,例如：

迭代矩陣G=，其特征多項(xiàng)式為特征值為-2，-3，所以迭代發(fā)散2023/2/461前例2用迭代法求解線性方程組

構(gòu)造的等價(jià)方程組雅可比迭代據(jù)此建立迭代公式迭代矩陣，所以迭代收斂其特征多項(xiàng)式為2023/2/462若迭代矩陣G的一種范數(shù),則迭代公式收斂,且有誤差估計(jì)式及

計(jì)算十分麻煩，因此將定理5改為定理6(迭代法收斂的充分條件)初值選擇巡環(huán)結(jié)束①②2023/2/463若,則迭代公式收斂,且有誤差估計(jì)式

及證:矩陣的譜半徑不超過矩陣的任一種范數(shù),即根據(jù)定理5可知迭代公式收斂。定理6(迭代法收斂的充分條件)2023/2/464因?yàn)?故x＝Gx＋d

有惟一解,即兩邊取范數(shù)與迭代過程相比較,有:①2023/2/465由迭代格式，有

兩邊取范數(shù)，得證畢②2023/2/466由定理知，當(dāng)時(shí)迭代收斂，值越小，迭代收斂越快，在程序設(shè)計(jì)中通常用相鄰兩次迭代（ε為給定的精度要求）作為控制迭代結(jié)束的條件，只要迭代收斂與初值無關(guān)。2023/2/467例5已知線性方程組考察用Jacobi迭代和Gauss-Seidel迭代求解時(shí)的收斂性解:⑴雅可比迭代矩陣

2023/2/468例5已知線性方程組，考察Jacobi

迭代的收斂性故Jacobi

迭代收斂

解:雅可比迭代矩陣

2023/2/469⑵高斯-塞德爾迭代，系數(shù)矩陣

高斯-塞德爾迭代矩陣

2023/2/470高斯-塞德爾迭代矩陣

故高斯—塞德爾迭代收斂。

2023/2/471定理7

設(shè)n階方陣為嚴(yán)格對(duì)角占優(yōu)陣,則

A為非奇異陣。證:因A為對(duì)角占優(yōu)陣,其主對(duì)角元素的絕對(duì)值大于同行其它元素絕對(duì)值之和,且主對(duì)角元素全不為0,故對(duì)角陣為非奇異。作矩陣2023/2/472利用對(duì)角占優(yōu)知由定理知非奇異,從而A非奇異,證畢系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)矩陣的線性方程組稱為對(duì)角占優(yōu)方程組。結(jié)論：嚴(yán)格對(duì)角占優(yōu)線性方程組的雅可比迭代公式和高斯-賽德爾迭代公式均收斂。2023/2/473例6

設(shè)證明,方程組

的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散證:雅可比迭代矩陣其譜半徑2023/2/474例6

設(shè)證明,方程組

的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散G-S迭代矩陣2023/2/475G-S迭代矩陣其譜半徑顯然,和同時(shí)小于、等于或大于1,因而Jacobi

迭代法與G-S迭代法具有相同的收斂性。2023/2/476例7

考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b

的收斂性，其中解：先計(jì)算迭代矩陣說明什么問題？2023/2/477求特征值雅可比矩陣

∴用雅可比迭代法求解時(shí)，迭代過程收斂(B)=0<12023/2/4781=0,2=2,3=2(G1)=2>1

∴用高斯-塞德爾迭代法求解時(shí)，迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值2023/2/479∴

Ax=b的系數(shù)矩陣按行嚴(yán)格對(duì)角占優(yōu),故高斯-塞德爾迭代收斂例8

設(shè)有迭代格式X(k+1)=B

X(k)+g

(k=0,1,2……）

其中B=I-A,如果A和B的特征值全為正數(shù)，試證：該迭代格式收斂。分析:根據(jù)A，B和單位矩陣I之間的特征值的關(guān)系導(dǎo)出(B)<1,從而說明迭代格式收斂。證:2023/2/480例9

設(shè)方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。2023/2/481例9

設(shè)方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為

2023/2/482例9設(shè)方程組寫出解方程組的Gauss-Seidel迭代矩陣，并討論迭代收斂的條件。Gauss-Seidel格式，對(duì)任意初值x(0)均收斂。解②Gauss-Seidel矩陣為2023/2/483解：先計(jì)算迭代矩陣?yán)?0

討論用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性。2023/2/484求特征值雅可比矩陣

(B)=1∴用雅可比迭代法求解時(shí)，迭代過程不收斂1=-1，2,3=1/22023/2/485求特征值高斯-塞德爾迭代矩陣

∴用高斯-塞德爾迭代法求解時(shí)，迭代過程收斂1=0,(G1)=0.3536<12023/2/486解:所給迭代公式的迭代矩陣為2023/2/487取0<<1/2迭代收斂2023/2/488例12

設(shè)求解線性方程組Ax=b的簡(jiǎn)單迭代法

x(k+1)=Bx(k)+g(k=0,1,2,……)

收斂,求證:對(duì)0<<1,迭代法

x(k+1)=[(1-)I+B]x(k)+g(k=0,1,2,…)

收斂。證:設(shè)C=(1-)I+B,(C)和(B)分別為C和B

的特征值，則顯然(C)=(1-)+(B)

因?yàn)?<<1,(C)是1和(B)的加權(quán)平均,

且由迭代法

x(k+1)=Bx(k)+g(k=0,1,2,……)收斂知|(B)|<1,故|(C)|<1,從而(C)<1,即x(k+1)=[(1-)I+B]x