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

1、線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,1,我們知道，凡是迭代法都有一個(gè)收斂問題，有時(shí)某種方法對(duì)一類方程組迭代收斂，而對(duì)另一類方程組進(jìn)行迭代時(shí)就會(huì)發(fā)散。一個(gè)收斂的迭代法不僅具有程序設(shè)計(jì)簡(jiǎn)單，適于自動(dòng)計(jì)算，而且較直接法更少的計(jì)算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一,第六章 解線性方程組的迭代法,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,2,6.1 迭代法的基本思想 迭代法的基本思想是將線性方程組轉(zhuǎn)化為便于迭代的等價(jià)方程組，對(duì)任選一組初始值 ，按某種計(jì)算規(guī)則，不斷地 對(duì)所得到的值進(jìn)行修正，最終獲得滿足精度要求的方程組

2、的近似解,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,3,設(shè) 非奇異， ，則線性方程組 有惟一解 ，經(jīng)過變換構(gòu)造出一個(gè)等價(jià)同解方程組 將上式改寫成迭代式,選定初始向量 ,反復(fù)不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,4,如果 存在極限 則稱迭代法是收斂的，否則就是發(fā)散的。 收斂時(shí)，在迭代公式 中當(dāng) 時(shí)， , 則 , 故 是方程組 的解。 對(duì)于給定的方程組可以構(gòu)造各種迭代公式。 并非全部收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,5,例1 用迭代法求解線性方程組,解 構(gòu)造方程組的等價(jià)方程組,據(jù)此

3、建立迭代公式,取 計(jì)算得,迭代解離精確解 越來越遠(yuǎn) 迭代不收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,6,6.2 雅可比與高斯-塞德爾迭代法 6.2.1 雅可比迭代法算法,例2 用雅可比迭代法求解方程組,解：從方程組的三個(gè)方程中分離出 和,建立迭代公式,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,7,取初始向量 進(jìn)行迭代, 可以逐步得出一個(gè)近似解的序列： （k=1, 2, ） 直到求得的近似解能達(dá)到預(yù)先要求的精度， 則迭代過程終止，以最后得到的近似解作為線 性方程組的解。 當(dāng)?shù)降?0次有 計(jì)算結(jié)果表明，此迭代過程收斂于方程組的精 確解x*= (3, 2, 1)T,線性方程組的

4、迭代法雅可比高斯塞德爾和超松弛迭代,8,考察一般的方程組，將n元線性方程組,寫成,若 ,分離出變量,據(jù)此建立迭代公式,上式稱為解方程組的Jacobi迭代公式,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,9,6.2.2 雅可比迭代法的矩陣表示 設(shè)方程組 的系數(shù)矩陣A非奇異，且主對(duì) 角元素 ，則可將A分裂成,記作 A = D - L - U,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,10,則 等價(jià)于,即,因?yàn)?，則,這樣便得到一個(gè)迭代公式,令,則有,k = 0,1,2,稱為雅可比迭代公式, B稱為雅可比迭代矩陣,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,11,雅可比迭代矩陣表示法，

5、主要是用來討論其收斂性，實(shí)際計(jì)算中，要用雅可比迭代法公式的分量形式。即,k=0,1,2,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,12,6.2.1 雅可比迭代法的算法實(shí)現(xiàn),線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,13,6.2.2 高斯-塞德爾（Gauss-Seidel）迭代法 高斯-塞德爾迭代法的基本思想 在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求 時(shí)用新分量 代替舊分量 , 就得到高斯-賽德爾迭代法。其迭代法格式為,i=1,2,n k=0,1,2,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,14,例3 用GaussSei

6、del 迭代格式解方程組,精確要求為=0.005,解 GaussSeidel 迭代格式為,取初始迭代向量 ,迭代結(jié)果為,x*,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,15,GaussSeidel 迭代法的矩陣表示 將A分裂成A =D-L-U，則 等價(jià)于 (D-L-U )x = b 于是,則高斯塞德爾迭代過程,因?yàn)?,所以,則高斯-塞德爾迭代形式為,故,令,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,16,定義：設(shè) 如果A的元素滿足 稱A為嚴(yán)格對(duì)角占優(yōu)陣。 2.如果A的元素滿足 且至少一個(gè)不等式嚴(yán)格成立，稱A為弱對(duì)角占優(yōu)陣,6.2.3 雅可比和高斯-塞德爾迭代收斂性,線性方程組的迭代

7、法雅可比高斯塞德爾和超松弛迭代,17,定義：設(shè) 如果存在置換矩陣P，使得 其中，A11為r階方陣，A22為n-r階方陣（ ）， 則稱A為可約矩陣，否則稱A為不可約矩陣,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,18,定理9：設(shè) 如果 1）A為嚴(yán)格對(duì)角占優(yōu)陣，則雅可比和高斯-塞德爾迭代法均收斂； 2）A為弱對(duì)角占優(yōu)陣，且A為不可約矩陣，則雅可比和高斯-塞德爾迭代法均收斂,定理10：設(shè)矩陣A對(duì)稱，且,1）雅可比迭代法收斂的充要條件：A和2D-A均為正定矩陣，其中D=diag（A）； 2）高斯-塞德爾迭代法收斂的充分條件：A正定,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,19,6.3 超

8、松弛迭代法（SOR方法） 使用迭代法的困難在于難以估計(jì)其計(jì)算 量。有時(shí)迭代過程雖然收斂，但由于收斂速 度緩慢，使計(jì)算量變得很大而失去使用價(jià)值 。因此，迭代過程的加速具有重要意義。逐 次超松弛迭代（Successive Over relaxatic Method，簡(jiǎn)稱SOR方法）法，可以看作是帶參數(shù)的高斯塞德爾迭代法，實(shí)質(zhì)上是高斯-塞德爾迭代的一種加速方法,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,20,6.3.1超松弛迭代法的基本思想 超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯塞德爾迭代公式的基礎(chǔ)上作一些修改。這種方法是將前一步的結(jié)果 與高斯-塞德爾迭代方法的迭代值 適當(dāng)加權(quán)平均

9、，期望獲得更好的近似值 。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應(yīng)用。 其具體計(jì)算公式如下,用高斯塞德爾迭代法定義輔助量,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,21,把 取為 與 的加權(quán)平均，即,合并表示為,式中系數(shù)稱為松弛因子，當(dāng)=1時(shí)，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0 2。 當(dāng)0 1時(shí)，低松弛法；當(dāng)1 2時(shí)稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,22,6.3.2 超松弛迭代法的矩陣表示 設(shè)線性方程組 Ax=b 的系數(shù)矩陣A非奇異,且主對(duì)角元素 , 則將A分裂成A=d-L-U, 則超松弛迭代公式用矩陣

10、表示為,或,故,顯然對(duì)任何一個(gè)值,(D+L)非奇異, (因?yàn)榧僭O(shè) )于是超松弛迭代公式為,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,23,令,則超松弛迭代 公式可寫成,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,24,例4 用SOR法求解線性方程組,取=1.46，要求,解：SOR迭代公式,k = 0,1,2,初值,該方程組的精確解 只需迭代20次便可達(dá)到精度要求,如果取=1(即高斯塞德爾迭代法)和同一初 值 ,要達(dá)到同樣精度, 需要迭代110次,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,25,6.3.2 迭代法的收斂性 我們知道, 對(duì)于給定的方程組可以構(gòu)造成簡(jiǎn)單迭代公式、雅可比

11、迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。 對(duì)于方程組 經(jīng)過等價(jià)變換構(gòu)造出的等價(jià)方程組,在什么條件下迭代序列 收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,26,基本定理5 迭代公式 收斂 的充分必要條件是迭代矩陣G的譜半徑 證:必要性 設(shè)迭代公式收斂,當(dāng)k時(shí), 則在迭代公式兩端同時(shí)取極限得 記 ,則 收斂于0(零向量),且有,于是,由于 可以是任意向量,故 收斂于0當(dāng)且僅 當(dāng) 收斂于零矩陣，即當(dāng) 時(shí),于是,所以必有,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,27,充分性: 設(shè) , 則必存在正數(shù), 使 則存在某種范數(shù) , 使 , ,則

12、, 所以 , 即 。故 收斂于 0, 收斂于 由此定理可知，不論是雅可比迭代法、高斯 塞德爾迭代法還是超松弛迭代法，它們收斂的 充要條件是其迭代矩陣的譜半徑,事實(shí)上, 在例1中, 迭代矩陣G= ， 其特征多項(xiàng)式為 ,特征值為 -2，-3， , 所以迭代發(fā)散,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,28,定理6 (迭代法收斂的充分條件) 若迭代矩陣G的一種范數(shù) ,則迭代公式 收斂,且有誤差估計(jì)式,及,證: 矩陣的譜半徑不超過矩陣的任一種范數(shù),已知 ,因此 ,根據(jù)定理4.9可知迭代公式收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,29,又因?yàn)?, 則det (I-G )0, I-G

13、為非奇異矩陣, 故xGxd有惟一解 , 即 與迭代過程 相比較, 有 兩邊取范數(shù),線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,30,由迭代格式，有,兩邊取范數(shù)，代入上式，得,證畢,由定理知，當(dāng) 時(shí)，其值越小，迭代收斂越快，在程序設(shè)計(jì)中通常用相鄰兩次迭代 （為給定的精度要求）作為 控制迭代結(jié)束的條件,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,31,例5 已知線性方程組,考察用Jacobi迭代和G-S迭代求解時(shí)的收斂性 解: 雅可比迭代矩陣,故Jacobi迭代收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,32,將系數(shù)矩陣分解,則高斯-塞德爾迭代矩陣,故高斯塞德爾迭代收斂,線性方程

14、組的迭代法雅可比高斯塞德爾和超松弛迭代,33,例：給出方程組 其中,問:分別利用Jacobi迭代法和Gauss-Seidel 迭代法是否收斂,解,對(duì),線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,34,而,即,所以，對(duì),Jacobi方法收斂，G-S方法發(fā)散,同理，對(duì)于,其中,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,35,即得,而,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,36,則,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,37,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,38,定理12 對(duì)于線性方程組Ax=b，若A為對(duì)稱正定矩陣，則當(dāng)02時(shí)，SOR迭代收斂,證明 只需

15、證明1（其中為L的任一特征值,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,39,定理13 對(duì)于線性代數(shù)方程組Ax=b， 若A按行(或列)嚴(yán)格對(duì)角占優(yōu)，或按行(或列)弱對(duì)角占優(yōu)不可約；則當(dāng)0w1時(shí)，SOR迭代收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,40,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,41,例6 設(shè) ,證明, 求解方程組,的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散,證:雅可比迭代矩陣,其譜半徑,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,42,例6設(shè) ,證明, 求解方程組,的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散,證: G-S迭代矩陣,其譜半徑,顯然,

16、 和 同時(shí)小于、等于或大于1,因而Jacobi迭代法與G-S迭代法具有相同的收斂性,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,43,例 7 考察用雅可比迭代法和高斯-塞德爾迭代 法解線性方程組Ax=b的收斂性，其中,解： 先計(jì)算迭代矩陣,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,44,求特征值,雅可比矩陣,( B ) = 0 1 用雅可比迭代法求解時(shí)，迭代過程收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,45,1=0,2 =2,3 =2 (G1)=21 用高斯-塞德爾迭代法求解時(shí)，迭代過程發(fā)散,高斯-塞德爾迭代矩陣,求特征值,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,

17、46,Ax=b的系數(shù)矩陣按行嚴(yán)格對(duì)角占優(yōu),故高斯-塞德爾迭代收斂,例9 設(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)出()1, 從而說明迭代格式收斂。 證: 因?yàn)锽=I-A, 故(B)= (I)- (A)=1 - (A) (A) + (B) = 1 由于已知(A) 和 (B)全為正數(shù)，故 0(B)1 ,從而 (B) 1 所以該迭代格式收斂,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,47,當(dāng)a1時(shí),Jacobi矩陣GJ1,對(duì)初值x(0)均收斂,例

18、10 設(shè) 方程組 寫出解方程組的Jacobi迭代公式和迭代矩陣 并討論迭代收斂的條件。 寫出解方程組的Gauss-Seidel迭代矩陣,并討 論迭代收斂的條件。 解 Jacobi迭代公式和Jacobi矩陣分別為,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,48,例 10設(shè) 方程組 寫出解方程組的Gauss-Seidel迭代矩陣，并討論 迭代收斂的條件。 解 Gauss-Seidel矩陣為,當(dāng)時(shí)a1時(shí), Gauss-Seidel矩陣 Gs1, 所以對(duì)任意初值x(0)均收斂,也可用矩陣的譜半徑p(GS)1來討論,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,49,解： 先計(jì)算迭代矩陣,例11

19、 討論用雅可比迭代法和高斯-塞德爾迭代 法解線性方程組Ax=b的收斂性,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,50,求特征值,雅可比矩陣,( B ) = 1 用雅可比迭代法求解時(shí)，迭代過程不收斂,1 = - 1， 2,3 = 1/2,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,51,求特征值,高斯-塞德爾迭代矩陣,(G1) = 0.3536 1 用高斯-塞德爾迭代法求解時(shí)，迭代過程收斂,1=0,線性方程組的迭代法雅可比高斯塞德爾和超松弛迭代,52,求解AX=b,當(dāng)取何值時(shí)迭代收斂？ 解:所給迭代公式的迭代矩陣為,例12 給定線性方程組 AX= b 用迭代公式 X(K+1)=X(K)+(b-AX(K) (k=0