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

1.雅可比（Jacobi）迭代法2.高斯-塞德爾(Gauss-Seidel)迭代法3.超松弛迭代法（SOR方法）4.迭代法的收斂性第六章解線性方程組的迭代法2023/1/171迭代法就是用某種極限過程去逐步逼近方程精確解的方法。迭代法不僅具有程序設計簡單，適于自動計算，而且較直接法更少的計算量，但迭代法都要考慮是否收斂和收斂速度問題。迭代法是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。解線性方程組的迭代法2023/1/172§6.1迭代法的基本思想

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

收斂向量序列解向量2023/1/173設非奇異,

，將線性方程組變換為一個等價同解方程組即將上式改寫成迭代式如果2023/1/174選定初始向量,反復不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法。2023/1/175考察一般的方程組，將n元線性方程組§6.2雅可比（Jacobi）迭代法2023/1/176考察一般的方程組，將n元線性方程組寫成

若

,分離出變量據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式?！?.2雅可比（Jacobi）迭代法2023/1/177雅可比迭代法公式的分量形式為：2023/1/178例1用雅可比迭代法求解方程組解：從方程組中分離出

和2023/1/179建立迭代公式取初始向量進行迭代,可以逐步得出一個近似解的序列：2023/1/1710計算表計算結果表明，此迭代過程收斂于方程組的精確解x*=(1.1,1.2,1.3)T。直到求得的近似解能達到預先要求的精度，則迭代過程終止2023/1/1711例2用迭代法求解線性方程組

解構造方程組的等價方程組據(jù)此建立迭代公式

對于給定的方程組可以構造各種迭代公式。并非全部收斂,例如：

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

建立迭代公式取計算得

迭代解離精確解越來越遠

迭代不收斂2023/1/1713§6.2.2雅可比迭代法的矩陣表示

A=D-L-U雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，用雅可比迭代法公式的分量形式。設方程組

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

，則可將A分裂成2023/1/1714§6.2.2雅可比迭代法的矩陣表示記作A=D-L-U2023/1/1715則等價于即這樣便得到一個迭代公式令則有稱為雅可比迭代公式,B稱為雅可比迭代矩陣2023/1/1716則有2023/1/17172023/1/17186.2.1雅可比迭代法的算法實現(xiàn)2023/1/1719§6.3.1高斯-塞德爾迭代法的基本思想

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

(i=1,2,…,nk=0,1,2,…)§6.3高斯-塞德爾（Gauss-Seidel）迭代法2023/1/1720高斯-塞德爾迭代法公式的分量形式。即(k=0,1,2,…)2023/1/1721例3用GaussSeidel迭代格式解方程組

精度要求為ε=0.005

解GaussSeidel迭代格式為取初始迭代向量,迭代結果為：2023/1/17222023/1/1723§

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

(D-L-U)x=b

于是,則高斯—塞德爾迭代過程因為

,所以

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

故

令2023/1/1724§

6.3.3高斯—塞德爾迭代算法實現(xiàn)高斯-塞德爾迭代算法的計算步驟與流程圖與雅可比迭代法大致相同，只是一旦求出變元的某個新值后,就改用新值替代老值,進行這一步剩下的計算。

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

§6.4超松弛迭代法（SOR方法）2023/1/1726

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

適當加權平均，期望獲得更好的近似值

。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應用?！?.4.1

超松弛迭代法的基本思想2023/1/1727⑵把

取為

與

的加權平均，即

合并表示為：SOR方法具體計算公式如下：⑴用高斯—塞德爾迭代法計算2023/1/1728式中系數(shù)ω稱為松弛因子，當ω=1時，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0<ω<2。當0<ω<1時，低松弛法；當1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。2023/1/1729§

6.4.2

超松弛迭代法的矩陣表示設線性方程組

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

,

則將

A

分裂成

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

顯然對任何一個ω值,(D+ωL)非奇異,

(因為假設

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

取ω=1.46，要求

解：SOR迭代公式

k=0,1,2,…，

初值2023/1/1732該方程組的精確解只需迭代20次便可達到精度要求.如果取ω=1(即高斯—塞德爾迭代法)和同一初值,要達到同樣精度,需要迭代110次.2023/1/1733我們知道,對于給定的方程組可以構造成簡單迭代、雅可比迭代、高斯-塞德爾迭代和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。在什么條件下迭代序列收斂？先引入如下定理

經(jīng)過等價變換構造出的等價方程組

對于方程組得到迭代序列§

6.5迭代法的收斂性2023/1/1734定理

對給定方陣G,若,則為非奇異矩陣,且

若為奇異矩陣,則存在非零向量x,使

由于,兩端消去,有,與已知條件矛盾,假設不成立,命題得證。證:用反證法由相容性條件得

,即有2023/1/1735定理

對給定方陣G,若,則為非奇異矩陣,且

即

將G分別取成G和-G，再取范數(shù)

又由于有2023/1/17362023/1/1737證:必要性由于可以是任意向量,故收斂于0當且僅當收斂于零矩陣，即當時，

基本定理5

迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑則在迭代公式兩端同時取極限得設迭代公式收斂,當k→∞時,2023/1/1738充分性:設,則必存在正數(shù)ε,使則存在某種范數(shù)

,使,,則,

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

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

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

迭代矩陣G=，其特征多項式為特征值為-2，-3，所以迭代發(fā)散2023/1/1740定理6(迭代法收斂的充分條件)若迭代矩陣G的一種范數(shù),則迭代公式收斂,且有誤差估計式及計算十分麻煩，因此將定理5改為2023/1/1741定理6(迭代法收斂的充分條件)

,則迭代公式收斂,且有誤差估計式及證:矩陣的譜半徑不超過矩陣的任一種范數(shù),即根據(jù)定理4.9可知迭代公式收斂。2023/1/1742因為,故x＝Gx＋d有惟一解,即兩邊取范數(shù)與迭代過程相比較,有:2023/1/1743由迭代格式，有

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

2023/1/1745例5已知線性方程組，考察Jacobi迭代的收斂性故Jacobi迭代收斂

解:雅可比迭代矩陣

2023/1/1746⑵高斯-塞德爾迭代，將系數(shù)矩陣分解

則高斯-塞德爾迭代矩陣

2023/1/1747高斯-塞德爾迭代矩陣

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

2023/1/1748定理7

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

的Jacobi迭代與G-S迭代同時收斂或發(fā)散證:雅可比迭代矩陣其譜半徑2023/1/1751例6設,證明,求解方程組

的Jacobi迭代與G-S迭代同時收斂或發(fā)散證:G-S迭代矩陣2023/1/1752證:G-S迭代矩陣其譜半徑顯然,和同時小于、等于或大于1,因而Jacobi迭代法與G-S迭代法具有相同的收斂性2023/1/1753例7

設求解線性方程組的雅可比迭代

x(k+1)=Bx(k)+fk=0,1,…

求證當‖B‖<1時,相應的G-S迭代收斂證這里以‖B‖

為例,‖B‖1類似由于B是雅可比迭代的迭代矩陣，故有

∴

Ax=b的系數(shù)矩陣按行嚴格對角占優(yōu),

故高斯-塞德爾迭代收斂2023/1/1754例8考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性，其中解：先計算迭代矩陣2023/1/1755求特征值雅可比矩陣

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

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

Ax=b的系數(shù)矩陣按行嚴格對角占優(yōu),故高斯-塞德爾迭代收斂例9設有迭代格式X(k+1)=BX(k)+g(k=0,1,2……）其中B=I-A,如果A和B的特征值全為正數(shù)，試證：該迭代格式收斂。分析:根據(jù)A，B和單位矩陣I之間的特征值的關系導出()<1,從而說明迭代格式收斂。證:2023/1/1758例10設方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。2023/1/1759例10設方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為

2023/1/1760例10設方程組寫出解方程組的Gauss-Seidel迭代矩陣，并討論迭代收斂的條件。Gauss-Seidel格式，對任意初值x(0)均收斂。解②Gauss-Seidel矩陣為2023/1/1761解：先計算迭代矩陣例11討論用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性。2023/1/1762求特征值雅可比矩陣

(B)=1∴用雅可比迭代法求解時，迭代過程不收斂1=-1，2,3=1/22023/1/1763求特征值高斯-塞德爾迭代矩陣(G1)=0.3536<1∴用高斯-塞德爾迭代法求解時，迭代過程收斂1=0,2023/1/1764解:所給迭代公式的迭代矩陣為2023/1/1765取0<<1/2迭代收斂2023/1/1766例13設求解線性方程組Ax=b的簡單迭代法

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

收斂,求證:對0<<1,迭代法

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

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

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

因為0<<1,(C)是1和(B)的加權平均,

且由迭代法

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