數(shù)值分析第三章線性方程組的迭代法課件

我們知道，凡是迭代法都有一個收斂問題，有時某種方法對一類方程組迭代收斂，而對另一類方程組進行迭代時就會發(fā)散。一個收斂的迭代法不僅具有程序設計簡單，適于自動計算，而且較直接法更少的計算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。第三章解線性方程組的迭代法我們知道，凡是迭代法都有一個收斂問題，有時某種方法對一1§3.1迭代法的基本思想

迭代法的基本思想是將線性方程組轉化為便于迭代的等價方程組，對任選一組初始值，按某種計算規(guī)則，不斷地對所得到的值進行修正，最終獲得滿足精度要求的方程組的近似解。

§3.1迭代法的基本思想2設非奇異，，則線性方程組有惟一解，經過變換構造出一個等價同解方程組將上式改寫成迭代式選定初始向量,反復不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法設非奇異，，則線性方程3如果存在極限則稱迭代法是收斂的，否則就是發(fā)散的。收斂時，在迭代公式中當時，,則,故是方程組的解。對于給定的方程組可以構造各種迭代公式。并非全部收斂如果4例1用迭代法求解線性方程組

解構造方程組的等價方程組據(jù)此建立迭代公式取計算得迭代解離精確解越來越遠迭代不收斂

例1用迭代法求解線性方程組解構造方程組的等價方程組5§3.2雅可比（Jacobi）迭代法§3.2.1雅可比迭代法算法構造例2用雅可比迭代法求解方程組解：從方程組的三個方程中分離出和建立迭代公式精確解x*=(3,2,1)T§3.2雅可比（Jacobi）迭代法例2用雅可比迭代法6取初始向量進行迭代,可以逐步得出一個近似解的序列：（k=1,2,…）直到求得的近似解能達到預先要求的精度，則迭代過程終止，以最后得到的近似解作為線性方程組的解。當?shù)降?0次有計算結果表明，此迭代過程收斂于方程組的精確解x*=(3,2,1)T。取初始向量7考察一般的方程組，將n元線性方程組寫成若,分離出變量據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式?？疾煲话愕姆匠探M，將n元線性方程組寫成若8§3.2.2雅可比迭代法的矩陣表示設方程組的系數(shù)矩陣A非奇異，且主對角元素，則可將A分裂成

記作A=D+L+U§3.2.2雅可比迭代法的矩陣表示記作A9則等價于即因為

，則這樣便得到一個迭代公式令則有（k=0,1,2…）稱為雅可比迭代公式,B稱為雅可比迭代矩陣則等價于即因為10雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，要用雅可比迭代法公式的分量形式。即(k=0,1,2,…)雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，要113.2.1雅可比迭代法的算法實現(xiàn)3.2.1雅可比迭代法的算法實現(xiàn)12§3.3高斯-塞德爾（Gauss-Seidel）迭代法§

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

在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當前最新的迭代值，即在求時用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：

(i=1,2,…,nk=0,1,2,…)§3.3高斯-塞德爾（Gauss-Seidel）迭代法13例3用GaussSeidel迭代格式解方程組

精確要求為ε=0.005

解GaussSeidel迭代格式為取初始迭代向量,迭代結果為：x*≈例3用GaussSeidel迭代格式解方程組精確要14§

3.3.2Gauss—Seidel迭代法的矩陣表示將A分裂成A=D+L+U，則等價于

(D+L+U)x=b于是,則高斯—塞德爾迭代過程因為,所以

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

故

令§3.3.2Gauss—Seidel迭代法的矩陣表示15§

3.3.3高斯—塞德爾迭代算法實現(xiàn)

高斯-塞德爾迭代算法的計算步驟與流程圖與雅可比迭代法大致相同，只是一旦求出變元的某個新值后,就改用新值替代老值

，再進行這一步剩下的計算。

§3.3.3高斯—塞德爾迭代算法實現(xiàn)16§3.4超松弛迭代法（SOR方法）

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

§3.4超松弛迭代法（SOR方法）17§

3.4.1超松弛迭代法的基本思想

超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯—塞德爾迭代公式的基礎上作一些修改。這種方法是將前一步的結果與高斯-塞德爾迭代方法的迭代值適當加權平均，期望獲得更好的近似值。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應用。其具體計算公式如下：⑴用高斯—塞德爾迭代法定義輔助量?！?.4.1超松弛迭代法的基本思想⑴用高斯—塞德爾迭代法18⑵把取為與的加權平均，即

合并表示為：式中系數(shù)ω稱為松弛因子，當ω=1時，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0<ω<2。當0<ω<1時，低松弛法；當1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。⑵把取為與19§

3.4.2超松弛迭代法的矩陣表示設線性方程組Ax=b的系數(shù)矩陣A非奇異,且主對角元素,則將A分裂成A=d+L+U,則超松弛迭代公式用矩陣表示為或故

顯然對任何一個ω值,(D+ωL)非奇異,(因為假設)于是超松弛迭代公式為§3.4.2超松弛迭代法的矩陣表示或故顯然對任何一個ω20令則超松弛迭代公式可寫成令則超松弛迭代21例4用SOR法求解線性方程組

取ω=1.46，要求解：SOR迭代公式

k=0,1,2,…，

初值該方程組的精確解只需迭代20次便可達到精度要求如果取ω=1(即高斯—塞德爾迭代法)和同一初值,要達到同樣精度,需要迭代110次例4用SOR法求解線性方程組取ω=1.46，要求解：22

§

3.5迭代法的收斂性我們知道,對于給定的方程組可以構造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。對于方程組經過等價變換構造出的等價方程組

在什么條件下迭代序列收斂？先引入如下定理

§3.5迭代法的收斂性在什么條件下迭代23基本定理5迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑證:必要性設迭代公式收斂,當k→∞時,則在迭代公式兩端同時取極限得記,則收斂于0(零向量),且有

于是

由于可以是任意向量,故收斂于0當且僅當收斂于零矩陣，即當時

于是

所以必有

基本定理5迭代公式24充分性:設,則必存在正數(shù)ε,使則存在某種范數(shù)

,使,,則,所以,即。故收斂于0,收斂于由此定理可知，不論是雅可比迭代法、高斯—塞德爾迭代法還是超松弛迭代法，它們收斂的充要條件是其迭代矩陣的譜半徑。

事實上,在例1中,迭代矩陣G=，其特征多項式為,特征值為-2，-3，,所以迭代發(fā)散

充分性:設,則必存在正數(shù)ε25定理6(迭代法收斂的充分條件)若迭代矩陣G的一種范數(shù),則迭代公式收斂,且有誤差估計式,且有誤差估計式及證:矩陣的譜半徑不超過矩陣的任一種范數(shù),已知,因此,根據(jù)定理4.9可知迭代公式收斂定理6(迭代法收斂的充分條件)及證:矩陣的譜半徑不超過26又因為,則det(I-G)≠0,I-G為非奇異矩陣,故x＝Gx＋d有惟一解,即與迭代過程相比較,有兩邊取范數(shù)

∴

又因為,則det(I-G)27由迭代格式，有

兩邊取范數(shù)，代入上式，得證畢由定理知，當時，其值越小，迭代收斂越快，在程序設計中通常用相鄰兩次迭代（ε為給定的精度要求）作為控制迭代結束的條件由迭代格式，有兩邊取范數(shù)，代入上式，得證畢由28例5已知線性方程組考察用Jacobi迭代和G-S迭代求解時的收斂性解:⑴雅可比迭代矩陣故Jacobi迭代收斂

例5已知線性方程組考察用Jacobi迭代和G-S迭代29⑵

將系數(shù)矩陣分解

則高斯-塞德爾迭代矩陣

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

⑵將系數(shù)矩陣分解則高斯-塞德爾迭代矩陣故高斯—塞德爾迭30定義3.2設矩陣每一行對角元素的絕對值都大于同行其他元素絕對值之和

則稱A為弱對角占優(yōu)矩陣。若上式中不等號均嚴格成立，則稱A為嚴格對角占優(yōu)矩陣。

定理8設n階方陣

為嚴格對角占優(yōu)陣,則A非奇異。定義3.2設矩陣每一行對角元素的絕對31定理9

若矩陣A按行(或列)嚴格對角占優(yōu),或按行(或列)弱對角占優(yōu)不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。定理9若矩陣A按行(或列)嚴格對角占優(yōu),或按行(或列)弱對32例6考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性，其中解：先計算迭代矩陣例6考察用雅可比迭代法和高斯-塞德爾迭代解：先計算33求特征值雅可比矩陣

(B)=0<1∴用雅可比迭代法求解時，迭代過程收斂求特征值雅可比矩陣(B)=0<1341=0,2=2,3=2(G1)=2>1

∴用高斯-塞德爾迭代法求解時，迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值1=0,2=2,3=2(G1)=2>35當時a<1時,Jacobi矩陣GJ∞<1,對初值x(0)均收斂例7設方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為

當時a<1時,Jacobi矩陣GJ∞<1,對初值36例7設方程組寫出解方程組的Gauss-Seidel迭代矩陣，并討論迭代收斂的條件。解②Gauss-Seidel矩陣為

當時a<1時,Gauss-Seidel矩陣Gs∞<1,所以對任意初值x(0)均收斂。也可用矩陣的譜半徑p(GS)<1來討論例7設方程組當時a<1時,Gauss-Seid37解：先計算迭代矩陣例8討論用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性。解：先計算迭代矩陣例8討論用雅可比迭代法和高斯-38求特征值雅可比矩陣

(B)=1∴用雅可比迭代法求解時，迭代過程不收斂1=-1，2,3=1/2求特征值雅可比矩陣(B)=1139求特征值高斯-塞德爾迭代矩陣(G1)=0.3536<1∴用高斯-塞德爾迭代法求解時，迭代過程收斂1=0,求特征值高斯-塞德爾迭代矩陣(G1)=0.40求解AX=b,當取何值時迭代收斂？解:所給迭代公式的迭代矩陣為例9給定線性方程組AX=b

用迭代公式X(K+1)=X(K)+(b-AX(K))(k=0,1,…）求解AX=b,當取何值時迭代收斂？例9給定線性方41即2-(2-5)+1-5+4

2=0

2-(2-5)+(1-)(1-4)=0

[-(1-)][-(1-4)]=0

1=1-2=1-4(B)=max{|1-|,|1-4|}<1取0<<1/2迭代收斂即2-(2-5)+1-5+4242

本章小結本章介紹了解線性方程組迭代法的一些基本理論和具體方法。迭代法是一種逐次逼近的方法，即對任意給定的初始近似解向量，按照某種方法逐步生成近似解序列，使解序列的極限為方程組的解。注意到在使用迭代法解方程組時，其迭代矩陣B和迭代向量f在計算過程中始終不變,迭代法具有循環(huán)的計算公式,方法簡單，程序實現(xiàn)方便，它的優(yōu)點是能充分利用系數(shù)的稀疏性,適宜解大型稀疏系數(shù)矩陣的方程組。

43迭代法不存在誤差累積問題。使用迭代法的關鍵問題是其收斂性與收斂速度，收斂性與迭代初值的選取無關，這是比一般非線性方程求根的優(yōu)越之處。在實際計算中，判斷一種迭代格式收斂性較麻煩，由于求迭代的譜半徑時需要求特征值，當矩陣的階數(shù)較大時，特征值不易求出，通常采用矩陣的任一種范數(shù)都小于1或對角占優(yōu)來判斷收斂性。有時也可邊計算邊觀察其收斂性。如何加快迭代過程的收斂速度是一個很重要的問題，實用中更多的采用SOR法，選擇適當?shù)乃神Y因子ω有賴于實際經驗。我們應針對不同的實際問題，采用適當?shù)臄?shù)值算法。迭代法不存在誤差累積問題。使用迭代法的44我們知道，凡是迭代法都有一個收斂問題，有時某種方法對一類方程組迭代收斂，而對另一類方程組進行迭代時就會發(fā)散。一個收斂的迭代法不僅具有程序設計簡單，適于自動計算，而且較直接法更少的計算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。第三章解線性方程組的迭代法我們知道，凡是迭代法都有一個收斂問題，有時某種方法對一45§3.1迭代法的基本思想

迭代法的基本思想是將線性方程組轉化為便于迭代的等價方程組，對任選一組初始值，按某種計算規(guī)則，不斷地對所得到的值進行修正，最終獲得滿足精度要求的方程組的近似解。

§3.1迭代法的基本思想46設非奇異，，則線性方程組有惟一解，經過變換構造出一個等價同解方程組將上式改寫成迭代式選定初始向量,反復不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法設非奇異，，則線性方程47如果存在極限則稱迭代法是收斂的，否則就是發(fā)散的。收斂時，在迭代公式中當時，,則,故是方程組的解。對于給定的方程組可以構造各種迭代公式。并非全部收斂如果48例1用迭代法求解線性方程組

解構造方程組的等價方程組據(jù)此建立迭代公式取計算得迭代解離精確解越來越遠迭代不收斂

例1用迭代法求解線性方程組解構造方程組的等價方程組49§3.2雅可比（Jacobi）迭代法§3.2.1雅可比迭代法算法構造例2用雅可比迭代法求解方程組解：從方程組的三個方程中分離出和建立迭代公式精確解x*=(3,2,1)T§3.2雅可比（Jacobi）迭代法例2用雅可比迭代法50取初始向量進行迭代,可以逐步得出一個近似解的序列：（k=1,2,…）直到求得的近似解能達到預先要求的精度，則迭代過程終止，以最后得到的近似解作為線性方程組的解。當?shù)降?0次有計算結果表明，此迭代過程收斂于方程組的精確解x*=(3,2,1)T。取初始向量51考察一般的方程組，將n元線性方程組寫成若,分離出變量據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式?？疾煲话愕姆匠探M，將n元線性方程組寫成若52§3.2.2雅可比迭代法的矩陣表示設方程組的系數(shù)矩陣A非奇異，且主對角元素，則可將A分裂成

記作A=D+L+U§3.2.2雅可比迭代法的矩陣表示記作A53則等價于即因為

，則這樣便得到一個迭代公式令則有（k=0,1,2…）稱為雅可比迭代公式,B稱為雅可比迭代矩陣則等價于即因為54雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，要用雅可比迭代法公式的分量形式。即(k=0,1,2,…)雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，要553.2.1雅可比迭代法的算法實現(xiàn)3.2.1雅可比迭代法的算法實現(xiàn)56§3.3高斯-塞德爾（Gauss-Seidel）迭代法§

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

在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當前最新的迭代值，即在求時用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：

(i=1,2,…,nk=0,1,2,…)§3.3高斯-塞德爾（Gauss-Seidel）迭代法57例3用GaussSeidel迭代格式解方程組

精確要求為ε=0.005

解GaussSeidel迭代格式為取初始迭代向量,迭代結果為：x*≈例3用GaussSeidel迭代格式解方程組精確要58§

3.3.2Gauss—Seidel迭代法的矩陣表示將A分裂成A=D+L+U，則等價于

(D+L+U)x=b于是,則高斯—塞德爾迭代過程因為,所以

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

故

令§3.3.2Gauss—Seidel迭代法的矩陣表示59§

3.3.3高斯—塞德爾迭代算法實現(xiàn)

高斯-塞德爾迭代算法的計算步驟與流程圖與雅可比迭代法大致相同，只是一旦求出變元的某個新值后,就改用新值替代老值

，再進行這一步剩下的計算。

§3.3.3高斯—塞德爾迭代算法實現(xiàn)60§3.4超松弛迭代法（SOR方法）

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

§3.4超松弛迭代法（SOR方法）61§

3.4.1超松弛迭代法的基本思想

超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯—塞德爾迭代公式的基礎上作一些修改。這種方法是將前一步的結果與高斯-塞德爾迭代方法的迭代值適當加權平均，期望獲得更好的近似值。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應用。其具體計算公式如下：⑴用高斯—塞德爾迭代法定義輔助量?！?.4.1超松弛迭代法的基本思想⑴用高斯—塞德爾迭代法62⑵把取為與的加權平均，即

合并表示為：式中系數(shù)ω稱為松弛因子，當ω=1時，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0<ω<2。當0<ω<1時，低松弛法；當1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。⑵把取為與63§

3.4.2超松弛迭代法的矩陣表示設線性方程組Ax=b的系數(shù)矩陣A非奇異,且主對角元素,則將A分裂成A=d+L+U,則超松弛迭代公式用矩陣表示為或故

顯然對任何一個ω值,(D+ωL)非奇異,(因為假設)于是超松弛迭代公式為§3.4.2超松弛迭代法的矩陣表示或故顯然對任何一個ω64令則超松弛迭代公式可寫成令則超松弛迭代65例4用SOR法求解線性方程組

取ω=1.46，要求解：SOR迭代公式

k=0,1,2,…，

初值該方程組的精確解只需迭代20次便可達到精度要求如果取ω=1(即高斯—塞德爾迭代法)和同一初值,要達到同樣精度,需要迭代110次例4用SOR法求解線性方程組取ω=1.46，要求解：66

§

3.5迭代法的收斂性我們知道,對于給定的方程組可以構造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。對于方程組經過等價變換構造出的等價方程組

在什么條件下迭代序列收斂？先引入如下定理

§3.5迭代法的收斂性在什么條件下迭代67基本定理5迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑證:必要性設迭代公式收斂,當k→∞時,則在迭代公式兩端同時取極限得記,則收斂于0(零向量),且有

于是

由于可以是任意向量,故收斂于0當且僅當收斂于零矩陣，即當時

于是

所以必有

基本定理5迭代公式68充分性:設,則必存在正數(shù)ε,使則存在某種范數(shù)

,使,,則,所以,即。故收斂于0,收斂于由此定理可知，不論是雅可比迭代法、高斯—塞德爾迭代法還是超松弛迭代法，它們收斂的充要條件是其迭代矩陣的譜半徑。

事實上,在例1中,迭代矩陣G=，其特征多項式為,特征值為-2，-3，,所以迭代發(fā)散

充分性:設,則必存在正數(shù)ε69定理6(迭代法收斂的充分條件)若迭代矩陣G的一種范數(shù),則迭代公式收斂,且有誤差估計式,且有誤差估計式及證:矩陣的譜半徑不超過矩陣的任一種范數(shù),已知,因此,根據(jù)定理4.9可知迭代公式收斂定理6(迭代法收斂的充分條件)及證:矩陣的譜半徑不超過70又因為,則det(I-G)≠0,I-G為非奇異矩陣,故x＝Gx＋d有惟一解,即與迭代過程相比較,有兩邊取范數(shù)

∴

又因為,則det(I-G)71由迭代格式，有

兩邊取范數(shù)，代入上式，得證畢由定理知，當時，其值越小，迭代收斂越快，在程序設計中通常用相鄰兩次迭代（ε為給定的精度要求）作為控制迭代結束的條件由迭代格式，有兩邊取范數(shù)，代入上式，得證畢由72例5已知線性方程組考察用Jacobi迭代和G-S迭代求解時的收斂性解:⑴雅可比迭代矩陣故Jacobi迭代收斂

例5已知線性方程組考察用Jacobi迭代和G-S迭代73⑵

將系數(shù)矩陣分解

則高斯-塞德爾迭代矩陣

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

⑵將系數(shù)矩陣分解則高斯-塞德爾迭代矩陣故高斯—塞德爾迭74定義3.2設矩陣每一行對角元素的絕對值都大于同行其他元素絕對值之和

則稱A為弱對角占優(yōu)矩陣。若上式中不等號均嚴格成立，則稱A為嚴格對角占優(yōu)矩陣。

定理8設n階方陣

為嚴格對角占優(yōu)陣,則A非奇異。定義3.2設矩陣每一行對角元素的絕對75定理9

若矩陣A按行(或列)嚴格對角占優(yōu),或按行(或列)弱對角占優(yōu)不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。定理9若矩陣A按行(或列)嚴格對角占優(yōu),或按行(或列)弱對76例6考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性，其中解：先計算迭代矩陣例6考察用雅可比迭代法和高斯-塞德爾迭代解：先計算77求特征值雅可比矩陣

(B)=0<1∴用雅可比迭代法求解時，迭代過程收斂求特征值雅可比矩陣(B)=0<1781=0,2=2,3=2(G1)=2>1

∴用高斯-塞德爾迭代法求解時，迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值1=0,2=2,3=2(G1)=2>79當時a<1時,Jacobi矩陣GJ∞<1,對初值x(0)均收斂例7設方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為

當時a