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

,我們知道，凡是迭代法都有一個(gè)收斂問題，有時(shí)某種方法對一類方程組迭代收斂，而對另一類方程組進(jìn)行迭代時(shí)就會(huì)發(fā)散。一個(gè)收斂的迭代法不僅具有程序設(shè)計(jì)簡單，適于自動(dòng)計(jì)算，而且較直接法更少的計(jì)算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。,第六章 解線性方程組的迭代法,1,§6.1 迭代法的基本思想 迭代法的基本思想是將線性方程組轉(zhuǎn)化為便于迭代的等價(jià)方程組，對任選一組初始值 ，按某種計(jì)算規(guī)則，不斷地 對所得到的值進(jìn)行修正，最終獲得滿足精度要求的方程組的近似解。,2,設(shè) 非奇異， ，則線性方程組 有惟一解 ，經(jīng)過變換構(gòu)造出一個(gè)等價(jià)同解方程組 將上式改寫成迭代式,選定初始向量 ,反復(fù)不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法,3,如果 存在極限 則稱迭代法是收斂的，否則就是發(fā)散的。 收斂時(shí)，在迭代公式 中當(dāng) 時(shí)， , 則 , 故 是方程組 的解。 對于給定的方程組可以構(gòu)造各種迭代公式。 并非全部收斂,4,例1 用迭代法求解線性方程組,解 構(gòu)造方程組的等價(jià)方程組,據(jù)此建立迭代公式,取 計(jì)算得,迭代解離精確解 越來越遠(yuǎn) 迭代不收斂,5,§6.2 雅可比與高斯-塞德爾迭代法 §6.2.1 雅可比迭代法算法,例2 用雅可比迭代法求解方程組,解：從方程組的三個(gè)方程中分離出 和,建立迭代公式,6,取初始向量 進(jìn)行迭代, 可以逐步得出一個(gè)近似解的序列： （k=1, 2, ） 直到求得的近似解能達(dá)到預(yù)先要求的精度， 則迭代過程終止，以最后得到的近似解作為線 性方程組的解。 當(dāng)?shù)降?0次有 計(jì)算結(jié)果表明，此迭代過程收斂于方程組的精 確解x*= (3, 2, 1)T。,7,考察一般的方程組，將n元線性方程組,寫成,若 ,分離出變量,據(jù)此建立迭代公式,上式稱為解方程組的Jacobi迭代公式。,8,§6.2.2 雅可比迭代法的矩陣表示 設(shè)方程組 的系數(shù)矩陣A非奇異，且主對 角元素 ，則可將A分裂成,記作 A = D - L - U,9,則 等價(jià)于,即,因?yàn)?，則,這樣便得到一個(gè)迭代公式,令,則有,（k = 0,1,2）,稱為雅可比迭代公式, B稱為雅可比迭代矩陣,10,雅可比迭代矩陣表示法，主要是用來討論其收斂性，實(shí)際計(jì)算中，要用雅可比迭代法公式的分量形式。即,(k=0,1,2,),11,6.2.1 雅可比迭代法的算法實(shí)現(xiàn),12,§ 6.2.2 高斯-塞德爾（Gauss-Seidel）迭代法 高斯-塞德爾迭代法的基本思想 在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求 時(shí)用新分量 代替舊分量 , 就得到高斯-賽德爾迭代法。其迭代法格式為：,(i=1,2,n k=0,1,2,),13,例3 用GaussSeidel 迭代格式解方程組,精確要求為=0.005,解 GaussSeidel 迭代格式為,取初始迭代向量 ,迭代結(jié)果為：,x* ,14,GaussSeidel 迭代法的矩陣表示 將A分裂成A =D-L-U，則 等價(jià)于 (D-L-U )x = b 于是,則高斯塞德爾迭代過程,因?yàn)?,所以,則高斯-塞德爾迭代形式為：,故,令,15,定義：設(shè) 如果A的元素滿足 稱A為嚴(yán)格對角占優(yōu)陣。 2.如果A的元素滿足 且至少一個(gè)不等式嚴(yán)格成立，稱A為弱對角占優(yōu)陣。,§ 6.2.3 雅可比和高斯-塞德爾迭代收斂性,16,定義：設(shè) 如果存在置換矩陣P，使得 其中，A11為r階方陣，A22為n-r階方陣（ ）， 則稱A為可約矩陣，否則稱A為不可約矩陣。,17,定理9：設(shè) 如果 1）A為嚴(yán)格對角占優(yōu)陣，則雅可比和高斯-塞德爾迭代法均收斂； 2）A為弱對角占優(yōu)陣，且A為不可約矩陣，則雅可比和高斯-塞德爾迭代法均收斂。,定理10：設(shè)矩陣A對稱，且,1）雅可比迭代法收斂的充要條件：A和2D-A均為正定矩陣，其中D=diag（A）； 2）高斯-塞德爾迭代法收斂的充分條件：A正定。,18,§ 6.3 超松弛迭代法（SOR方法） 使用迭代法的困難在于難以估計(jì)其計(jì)算 量。有時(shí)迭代過程雖然收斂，但由于收斂速 度緩慢，使計(jì)算量變得很大而失去使用價(jià)值 。因此，迭代過程的加速具有重要意義。逐 次超松弛迭代（Successive Over relaxatic Method，簡稱SOR方法）法，可以看作是帶參數(shù)的高斯塞德爾迭代法，實(shí)質(zhì)上是高斯-塞德爾迭代的一種加速方法。,19,§ 6.3.1超松弛迭代法的基本思想 超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯塞德爾迭代公式的基礎(chǔ)上作一些修改。這種方法是將前一步的結(jié)果 與高斯-塞德爾迭代方法的迭代值 適當(dāng)加權(quán)平均，期望獲得更好的近似值 。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應(yīng)用。 其具體計(jì)算公式如下：, 用高斯塞德爾迭代法定義輔助量。,20, 把 取為 與 的加權(quán)平均，即,合并表示為：,式中系數(shù)稱為松弛因子，當(dāng)=1時(shí)，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0 2。 當(dāng)0 1時(shí)，低松弛法；當(dāng)1 2時(shí)稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。,21,§ 6.3.2 超松弛迭代法的矩陣表示 設(shè)線性方程組 Ax=b 的系數(shù)矩陣A非奇異,且主對角元素 , 則將A分裂成A=d-L-U, 則超松弛迭代公式用矩陣表示為,或,故,顯然對任何一個(gè)值,(D+L)非奇異, (因?yàn)榧僭O(shè) )于是超松弛迭代公式為,22,令,則超松弛迭代 公式可寫成,23,例4 用SOR法求解線性方程組,取=1.46，要求,解：SOR迭代公式,k = 0,1,2,，,初值,該方程組的精確解 只需迭代20次便可達(dá)到精度要求,如果取=1(即高斯塞德爾迭代法)和同一初 值 ,要達(dá)到同樣精度, 需要迭代110次,24,§ 6.3.2 迭代法的收斂性 我們知道, 對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。 對于方程組 經(jīng)過等價(jià)變換構(gòu)造出的等價(jià)方程組,在什么條件下迭代序列 收斂？,25,基本定理5 迭代公式 收斂 的充分必要條件是迭代矩陣G的譜半徑 證:必要性 設(shè)迭代公式收斂,當(dāng)k時(shí), 則在迭代公式兩端同時(shí)取極限得 記 ,則 收斂于0(零向量),且有,于是,由于 可以是任意向量,故 收斂于0當(dāng)且僅 當(dāng) 收斂于零矩陣，即當(dāng) 時(shí),于是,所以必有,26,充分性: 設(shè) , 則必存在正數(shù), 使 則存在某種范數(shù) , 使 , ,則 , 所以 , 即 。故 收斂于 0, 收斂于 由此定理可知，不論是雅可比迭代法、高斯 塞德爾迭代法還是超松弛迭代法，它們收斂的 充要條件是其迭代矩陣的譜半徑 。,事實(shí)上, 在例1中, 迭代矩陣G= ， 其特征多項(xiàng)式為 ,特征值為 -2，-3， , 所以迭代發(fā)散,27,定理6 (迭代法收斂的充分條件) 若迭代矩陣G的一種范數(shù) ,則迭代公式 收斂,且有誤差估計(jì)式,及,證: 矩陣的譜半徑不超過矩陣的任一種范數(shù),已知 ,因此 ,根據(jù)定理4.9可知迭代公式收斂,28,又因?yàn)?, 則det (I-G )0, I-G為非奇異矩陣, 故xGxd有惟一解 , 即 與迭代過程 相比較, 有 兩邊取范數(shù),29,由迭代格式，有,兩邊取范數(shù)，代入上式，得,證畢,由定理知，當(dāng) 時(shí)，其值越小，迭代收斂越快，在程序設(shè)計(jì)中通常用相鄰兩次迭代 （為給定的精度要求）作為 控制迭代結(jié)束的條件,30,例5 已知線性方程組,考察用Jacobi迭代和G-S迭代求解時(shí)的收斂性 解: 雅可比迭代矩陣,故Jacobi迭代收斂,31, 將系數(shù)矩陣分解,則高斯-塞德爾迭代矩陣,故高斯塞德爾迭代收斂。,32,例：給出方程組 其中,問:分別利用Jacobi迭代法和Gauss-Seidel 迭代法是否收斂.,解：,對,33,而,即,所以，對,Jacobi方法收斂，G-S方法發(fā)散,同理，對于,其中,34,即得,而,35,則,36,37,定理12 對于線性方程組Ax=b，若A為對稱正定矩陣，則當(dāng)02時(shí)，SOR迭代收斂.,證明 只需證明1（其中為L的任一特征值）.,38,定理13 對于線性代數(shù)方程組Ax=b， 若A按行(或列)嚴(yán)格對角占優(yōu)，或按行(或列)弱對角占優(yōu)不可約；則當(dāng)0w1時(shí)，SOR迭代收斂。,39,40,例6 設(shè) ,證明, 求解方程組,的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散,證:雅可比迭代矩陣,其譜半徑,41,例6設(shè) ,證明, 求解方程組,的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散,證: G-S迭代矩陣,其譜半徑,顯然, 和 同時(shí)小于、等于或大于1,因而Jacobi迭代法與G-S迭代法具有相同的收斂性,42,例 7 考察用雅可比迭代法和高斯-塞德爾迭代 法解線性方程組Ax=b的收斂性，其中,解： 先計(jì)算迭代矩陣,43,求特征值,雅可比矩陣, ( B ) = 0 1 用雅可比迭代法求解時(shí)，迭代過程收斂,44,1=0,2 =2,3 =2 (G1)=21 用高斯-塞德爾迭代法求解時(shí)，迭代過程發(fā)散,高斯-塞德爾迭代矩陣,求特征值,45, Ax=b的系數(shù)矩陣按行嚴(yán)格對角占優(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 所以該迭代格式收斂。,46,當(dāng)a1時(shí),Jacobi矩陣GJ1,對初值x(0)均收斂,例10 設(shè) 方程組 寫出解方程組的Jacobi迭代公式和迭代矩陣 并討論迭代收斂的條件。 寫出解方程組的Gauss-Seidel迭代矩陣,并討 論迭代收斂的條件。 解 Jacobi迭代公式和Jacobi矩陣分別為,47,例 10設(shè) 方程組 寫出解方程組的Gauss-Seidel迭代矩陣，并討論 迭代收斂的條件。 解 Gauss-Seidel矩陣為,當(dāng)時(shí)a1時(shí), Gauss-Seidel矩陣 Gs1, 所以對任意初值x(0)均收斂。,也可用矩陣的譜半徑p(GS)1來討論,48,解： 先計(jì)算迭代矩陣,例11 討論用雅可比迭代法和高斯-塞德爾迭代 法解線性方程組Ax=b的收斂性。,49,求特征值,雅可比矩陣, ( B ) = 1 用雅可比迭代法求解時(shí)，迭代過程不收斂,1 = - 1， 2,3 = 1/2,50,求特征值,高斯-塞德爾迭代矩陣, (G1) = 0.3536 1 用高斯-塞德爾迭代法求解時(shí)，迭代過程收斂,1=0,51,求解AX=b,當(dāng)取何值時(shí)迭代收斂？ 解:所給迭代公式的迭代矩陣為,例12 給定線性方程組 AX= b 用迭代公式 X(K+1)=X(K)+(b-AX(K) (k=0,1,）,52,即 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迭代收斂,53,本章小結(jié) 本章介紹了解線性方程組 迭代法的 一些基本理論和具體方法。迭代法是一種逐次逼 近的方法，即對任意給定的初始近似解向量，按 照某種方法逐步生成近似解序列，使解序列的極 限為方程組的解。注意到在使用迭代法 解方程組時(shí)，其迭代矩陣B和迭代向量f在計(jì)算過 程中始終不變,迭代法具有循環(huán)的計(jì)算公式,方法 簡單，程序?qū)崿F(xiàn)方便，它的優(yōu)點(diǎn)是能充分利用系 數(shù)的稀疏性,適宜解大型稀疏系數(shù)矩陣的方程組。,54,迭代法不存在誤差累積問題。使用迭代法的 關(guān)鍵問題是其收斂性與收斂速度，收斂性與迭代 初值的選取無關(guān)，這是比一般非線性方程求根的 優(yōu)越之處。在實(shí)際計(jì)算中，判斷一種迭代格式收 斂性較麻煩，由于求迭代的譜半徑時(shí)需要求特征 值，當(dāng)矩陣的階數(shù)較大時(shí)，特征值不易求出，通 常采用矩陣的任一種范數(shù)都小于1或?qū)钦純?yōu)來判 斷收斂性。有時(shí)也可邊計(jì)算邊觀察其收斂性。如 何加快迭代過程的收斂速度是一個(gè)很重要的問題 ，實(shí)用中更多的采用SOR法，選擇適當(dāng)?shù)乃神Y因子 有賴于實(shí)際經(jīng)驗(yàn)。我們應(yīng)針對不同的實(shí)際問題 ，采用適當(dāng)?shù)臄?shù)值算法。,55,