線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代

我們知道，但凡迭代法都有一個收斂問題，有時某種方法對一類方程組迭代收斂，而對另一類方程組進行迭代時就會發(fā)散。一個收斂的迭代法不僅具有程序設計簡單，適于自動計算，而且較直接法更少的計算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。第六章解線性方程組的迭代法1精選課件§6.1迭代法的根本思想迭代法的根本思想是將線性方程組轉化為便于迭代的等價方程組，對任選一組初始值，按某種計算規(guī)那么，不斷地對所得到的值進行修正，最終獲得滿足精度要求的方程組的近似解。

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

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

5精選課件§6.2雅可比與高斯-塞德爾迭代法§6.2.1

雅可比迭代法算法例2用雅可比迭代法求解方程組解：從方程組的三個方程中別離出和建立迭代公式6精選課件取初始向量進行迭代,可以逐步得出一個近似解的序列：〔k=1,2,…〕直到求得的近似解能到達預先要求的精度，那么迭代過程終止，以最后得到的近似解作為線性方程組的解。當?shù)降?0次有計算結果說明，此迭代過程收斂于方程組的精確解x*=(3,2,1)T。7精選課件考察一般的方程組，將n元線性方程組寫成假設,別離出變量據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式。8精選課件§6.2.2雅可比迭代法的矩陣表示設方程組的系數(shù)矩陣A非奇異，且主對角元素，那么可將A分裂成記作A=D-L-U9精選課件那么等價于即因為，那么這樣便得到一個迭代公式令那么有〔k=0,1,2…〕稱為雅可比迭代公式,B稱為雅可比迭代矩陣10精選課件雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，要用雅可比迭代法公式的分量形式。即(k=0,1,2,…)11精選課件6.2.1雅可比迭代法的算法實現(xiàn)12精選課件§6.2.2高斯-塞德爾〔Gauss-Seidel〕迭代法高斯-塞德爾迭代法的根本思想在Jacobi迭代法中，每次迭代只用到前一次的迭代值，假設每次迭代充分利用當前最新的迭代值，即在求時用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：(i=1,2,…,nk=0,1,2,…)13精選課件例3用Gauss

Seidel迭代格式解方程組

精確要求為ε=0.005

解Gauss

Seidel迭代格式為取初始迭代向量,迭代結果為：x*≈14精選課件Gauss—Seidel迭代法的矩陣表示將A分裂成A=D-L-U，那么等價于(D-L-U)x=b于是,那么高斯—塞德爾迭代過程因為,所以

那么高斯-塞德爾迭代形式為：故

令15精選課件定義：設

如果A的元素滿足稱A為嚴格對角占優(yōu)陣。2.如果A的元素滿足且至少一個不等式嚴格成立，稱A為弱對角占優(yōu)陣。§

6.2.3雅可比和高斯-塞德爾迭代收斂性16精選課件定義：設

如果存在置換矩陣P，使得其中，A11為r階方陣，A22為n-r階方陣〔〕，那么稱A為可約矩陣，否那么稱A為不可約矩陣。17精選課件定理9：設如果1〕A為嚴格對角占優(yōu)陣，那么雅可比和高斯-塞德爾迭代法均收斂；2〕A為弱對角占優(yōu)陣，且A為不可約矩陣，那么雅可比和高斯-塞德爾迭代法均收斂。定理10：設矩陣A對稱，且1〕雅可比迭代法收斂的充要條件：A和2D-A均為正定矩陣，其中D=diag〔A〕；2〕高斯-塞德爾迭代法收斂的充分條件：A正定。18精選課件§6.3超松弛迭代法〔SOR方法〕使用迭代法的困難在于難以估計其計算量。有時迭代過程雖然收斂，但由于收斂速度緩慢，使計算量變得很大而失去使用價值。因此，迭代過程的加速具有重要意義。逐次超松弛迭代〔SuccessiveOverrelaxaticMethod，簡稱SOR方法〕法，可以看作是帶參數(shù)的高斯—塞德爾迭代法，實質上是高斯-塞德爾迭代的一種加速方法。19精選課件§6.3.1超松弛迭代法的根本思想超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯—塞德爾迭代公式的根底上作一些修改。這種方法是將前一步的結果與高斯-塞德爾迭代方法的迭代值適當加權平均，期望獲得更好的近似值。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應用。其具體計算公式如下：⑴用高斯—塞德爾迭代法定義輔助量。20精選課件⑵把取為與的加權平均，即

合并表示為：式中系數(shù)ω稱為松弛因子，當ω=1時，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0<ω<2。當0<ω<1時，低松弛法；當1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。21精選課件§6.3.2超松弛迭代法的矩陣表示設線性方程組Ax=b的系數(shù)矩陣A非奇異,且主對角元素,那么將A分裂成A=d-L-U,那么超松弛迭代公式用矩陣表示為或故

顯然對任何一個ω值,(D+ωL)非奇異,(因為假設)于是超松弛迭代公式為22精選課件令那么超松弛迭代公式可寫成23精選課件例4用SOR法求解線性方程組

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

k=0,1,2,…，

初值該方程組的精確解只需迭代20次便可到達精度要求如果取ω=1(即高斯—塞德爾迭代法)和同一初值,要到達同樣精度,需要迭代110次24精選課件

§

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

在什么條件下迭代序列收斂？25精選課件根本定理5迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑證:必要性設迭代公式收斂,當k→∞時,那么在迭代公式兩端同時取極限得記,那么收斂于0(零向量),且有于是由于可以是任意向量,故收斂于0當且僅當收斂于零矩陣，即當時于是所以必有

26精選課件充分性:設,那么必存在正數(shù)ε,使那么存在某種范數(shù),使,,那么,所以,即。故收斂于0,收斂于由此定理可知，不管是雅可比迭代法、高斯—塞德爾迭代法還是超松弛迭代法，它們收斂的充要條件是其迭代矩陣的譜半徑。

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

27精選課件定理6(迭代法收斂的充分條件)假設迭代矩陣G的一種范數(shù),那么迭代公式收斂,且有誤差估計式及證:矩陣的譜半徑不超過矩陣的任一種范數(shù),,因此,根據(jù)定理4.9可知迭代公式收斂28精選課件又因為,那么det(I-G)≠0,I-G為非奇異矩陣,故x＝Gx＋d有惟一解,即與迭代過程相比較,有兩邊取范數(shù)∴

29精選課件由迭代格式，有

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

31精選課件⑵

將系數(shù)矩陣分解

那么高斯-塞德爾迭代矩陣故高斯—塞德爾迭代收斂。

32精選課件例：給出方程組其中問:分別利用Jacobi迭代法和Gauss-Seidel迭代法是否收斂.解：對33精選課件而即所以，對Jacobi方法收斂，G-S方法發(fā)散同理，對于其中34精選課件即得而35精選課件則所以，對Jacobi方法發(fā)散，G-S方法收斂.說明，Jacobi方法和G-S方法的收斂條件大多數(shù)是互不包含的.36精選課件37精選課件定理12對于線性方程組Ax=b，假設A為對稱正定矩陣，那么當0<ω<2時，SOR迭代收斂.

證明只需證明λ<1〔其中λ為Lω的任一特征值〕.38精選課件定理13對于線性代數(shù)方程組Ax=b，假設A按行(或列)嚴格對角占優(yōu)，或按行(或列)弱對角占優(yōu)不可約；那么當0<w≤1時，SOR迭代收斂。39精選課件40精選課件例6設,證明,求解方程組

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

的Jacobi迭代與G-S迭代同時收斂或發(fā)散證:G-S迭代矩陣其譜半徑顯然,和同時小于、等于或大于1,因而Jacobi迭代法與G-S迭代法具有相同的收斂性42精選課件例7考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性，其中解：先計算迭代矩陣43精選課件求特征值雅可比矩陣

(B)=0<1∴用雅可比迭代法求解時，迭代過程收斂44精選課件

1=0,2=2,3=2(G1)=2>1

∴用高斯-塞德爾迭代法求解時，迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值45精選課件∴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,從而說明迭代格式收斂。證:因為B=I-A,故(B)=(I)-(A)=1-(A)(A)+(B)=1由于(A)和(B)全為正數(shù)，故0<(B)<1,從而(B)<1所以該迭代格式收斂。46精選課件當a<1時,Jacobi矩陣GJ

∞<1,對初值x(0)均收斂例10設方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為

47精選課件例10設方程組寫出解方程組的Gauss-Seidel迭代矩陣，并討論迭代收斂的條件。解②Gauss-Seidel矩陣為

當時a<1時,Gauss-Seidel矩陣Gs

∞<1,所以對任意初值x(0)均收斂。也可用矩陣的譜半徑p(GS)<1來討論48精選課件解：先計算迭代矩陣例11討論用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性。49精選課件求特征值雅可比矩陣

(B)=1∴用雅可比迭代法求解時，迭代過程不收斂

1=-1，2,3=1/250精選課件求特征值高斯-塞德爾迭代矩陣(G1)=0.3536<1∴用高斯-塞德爾迭代法求解時，迭代過程收斂

1=0,51精選課件求解AX=b,當取何值時迭代收斂？解:所給迭代公式的迭代矩陣為例12給定線性方程組AX=b

用迭代公式X(K+1)=X(K)+(b-AX(K))(k=0,1