《線性方程組的迭代法雅可比高斯塞德?tīng)柡统沙诘鷓pt課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《線性方程組的迭代法雅可比高斯塞德?tīng)柡统沙诘鷓pt課件（55頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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