《現(xiàn)代數(shù)值計(jì)算》課件6.2-6.4線性方程組的迭代方法(上課用)

1、6.2 基本迭代方法6.1.2 Jacobi 迭代法和 Gauss-Seidel迭代法6.2.1 迭代公式的構(gòu)造第六章 線性方程組的迭代解法教學(xué)目的 1. 掌握J(rèn)acobi迭代法，G-S迭代法解大型線性方程組的方法及其收斂性的判別方法；2. 掌握SOR迭代法及收斂的必要條件(02 )；3. 了解三種迭代法之間的改進(jìn)關(guān)系從而掌握該思想方法；4. 理解迭代法基本定理。教學(xué)重點(diǎn)及難點(diǎn) 重點(diǎn)是三種迭代法及收斂性的判別方法；難點(diǎn)是迭代法基本定理及三種迭代法收斂定理的證明。 迭代法是一種不斷套用一個(gè)迭代公式，逐步逼近方程組的精確迭代法優(yōu)點(diǎn)：計(jì)算量小，近似解精度高?？紤]問題：如何構(gòu)造解 的有效迭代法？計(jì)算量

2、： 直接法：解低階稠密線性方程組，解（真解）的方法。適合解大型稀疏線性方程組。 用差分法或有限元法解偏微分方程邊值問題時(shí)得到的方程組。 電工學(xué)中的網(wǎng)絡(luò)問題；大型稀疏線性方程組占用內(nèi)存單元較少。設(shè)計(jì)程序簡單（適合計(jì)算機(jī)計(jì)算）。收斂性與收斂速度怎樣？第6章 線性方程組的迭代解法迭代法在計(jì)算機(jī)內(nèi)存和運(yùn)算兩方面，通常都可利用A中有大量零元素的特點(diǎn)。6.2.1. 迭代法的基本思想 迭代法的基本思想是將線性方程組 Ax=b (6.2.1)轉(zhuǎn)化為便于迭代的等價(jià)方程組，對任選一組初始值 ，按某種計(jì)算規(guī)則，不斷地對所得到的值進(jìn)行修正，最終獲得滿足精度要求的方程組的近似解。 設(shè) 非奇異， ，則線性方程組 有惟一解

3、 ，經(jīng)過變換構(gòu)造出一個(gè)等價(jià)同解方程組將上式改寫成單步定常迭代式選定初始向量 ,反復(fù)不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為單步定常迭代法（B, f都與k無關(guān)）. 如果 存在極限則稱迭代法是收斂的，否則就是發(fā)散的。收斂時(shí)，在迭代公式中當(dāng) 時(shí)， ,則 , 故 是方程組 的解。由前而可得： ，從而遞推得：為討論 收斂性，引進(jìn)誤差向量：亦即B滿足什么條件使 （零矩陣） 。 要 收斂于 。則須考察B在什么條件下 ，例6.1先將Ax=b轉(zhuǎn)化為等價(jià)方程組迭代公式：選取初始向量經(jīng)10次迭代解：對于給定的方程組可以構(gòu)造各種迭代公式,但并非全部收斂 。例6.2 用迭代法求解線性方

4、程組 解 構(gòu)造方程組的等價(jià)方程組據(jù)此建立迭代公式 取 計(jì)算得 迭代解離精確解 越來越遠(yuǎn)迭代不收斂 6.1.2 雅可比（Jacobi）迭代法1雅可比迭代法算法構(gòu)造 例6. 用雅可比迭代法求解方程組 解：從方程組的三個(gè)方程中分離出 和 建立迭代公式 取初始向量進(jìn)行迭代, 可以逐步得出一個(gè)近似解的序列： （k=1, 2, ）直到求得的近似解能達(dá)到預(yù)先要求的精度，則迭代過程終止，以最后得到的近似解作為線性方程組的解。 當(dāng)?shù)降?0次有計(jì)算結(jié)果表明，此迭代過程收斂于方程組的精確解x*= (3, 2, 1)T。 考察一般的方程組，將n元線性方程組 寫成 若 ,分離出變量 據(jù)此建立迭代公式 上式稱為解方程

5、組的Jacobi迭代公式。 2 雅可比迭代法的矩陣表示 設(shè)方程組 的系數(shù)矩陣A非奇異，且主對角元素 ，則可將A分裂成 記作 A = -L + D -U 即因?yàn)?，則 這樣便得到一個(gè)迭代公式令則有（k = 0,1,2）稱為雅可比迭代公式, BJ稱為雅可比迭代矩陣則 等價(jià)于其中 在例5.3中,由迭代公式寫出雅可比迭代矩陣為 雅可比迭代矩陣表示法，主要是用來討論其收斂性，實(shí)際計(jì)算中，要用雅可比迭代法公式的分量形式。即 (k=0,1,2,) J 稱為Jacobi迭代法的迭代陣Jacobi迭代法：若記Jacobi迭代法的分量形式：稱（6.2.2）為解（6.2.1）的Jacobi 迭代法，簡稱 J 法。(

6、6.2.2)當(dāng) 時(shí)，得到由（6.2.2）有 ，即 求解 的Jacobi迭代法計(jì)算公式： (6.2.3) 注：(1)Jacobi迭代法,每迭代一次主要是計(jì)算一次矩陣乘向量 。 （2)計(jì)算過程中，原始數(shù)據(jù)A始終不變。(3)計(jì)算中需要兩組工作單元 用來保存 及 。 前一例6.3即為Jacobi法求解，在此不再舉例。 Algorithm: Jacobi Iterative Method Solve given an initial approximation .Input: the number of equations and unknowns n; the matrix entries a ; t

7、he entries b ; the initial approximation X0 ; tolerance TOL; maximum number of iterations Mmax.Output: approximate solution X or a message of failure.Step 1 Set k = 1;Step 2 While ( k Mmax) do steps 3-6Step 3 For i = 1, , n Set ; /* compute xk */Step 4 If then Output (X ); STOP; /* successful */Step

8、 5 For i = 1, , n Set X 0 = X ; /* update X0 */ Step 6 Set k +;Step 7 Output (Maximum number of iterations exceeded); STOP. /* unsuccessful */What if aii = 0?迭代過程中，A 的元素不改變，故可以事先調(diào)整好 A 使得aii 0，否則 A不可逆。必須等X(k)完全計(jì)算好了才能計(jì)算X(k+1)，因此需要兩組向量存儲(chǔ)。A bit wasteful, isnt it?6.2.3高斯-塞德爾(Gauss-Seidel)迭代法(G-S) (i=1,2,

9、n k=0,1,2,)1 高斯-塞德爾迭代法的基本思想 在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求 時(shí)用新分量代替舊分量 , 就得到高斯-賽德爾迭代法。其迭代法格式為： 只存一組向量即可。例6.4 用GaussSeidel 迭代格式解方程組 精確要求為=0.005 解 GaussSeidel 迭代格式為取初始迭代向量 ,迭代結(jié)果為：x* 2. GaussSeidel 迭代法的矩陣表示 將A分裂成A =D-L-U，則 等價(jià)于 (D-L-U )x = b 于是,則高斯塞德爾迭代過程 因?yàn)?,所以 則高斯-塞德爾迭代形式為： 故 令 于是得到解

10、的G-S迭代法： (6.2.3)其中BGS 稱為G-S迭代法的迭代陣 從上面的分析可以看出, G-S迭代法是改進(jìn)的J迭代法. 即 在J 法中，計(jì)算 時(shí)，分量 已經(jīng)算出，因此可考慮對J 法進(jìn)行修改。在每個(gè)分量計(jì)算出來之后，下一個(gè)分量的計(jì)算就利用最 新的計(jì)算結(jié)果。這樣，在整個(gè)迭代過程中只要使用一組單元存放迭代向量，其分量形式的計(jì)算結(jié)果為（6.2.10）這就是Gauss-Seidel 迭代法，簡稱 GS 法(1)由(6.2.10)可知,計(jì)算 第i個(gè)分量時(shí),利用已經(jīng)計(jì)算出的最新G-S法的優(yōu)點(diǎn)：(2)G-S迭代法每迭代一次主要計(jì)算一次矩陣乘向量。計(jì)算量小，(3)當(dāng)J-迭代與G-S迭代都收斂時(shí)， G-S迭

11、代的收斂速度快。 G-S迭代法可看作J迭代法的一種修正或改進(jìn)。用G-S迭代法解只需要一組工作單元，用來保存 或 分量。分量 ，因此，計(jì)算 就可沖掉 ,于是利G-S迭代存貯少。例6. 5用法和法分別求解方程組其準(zhǔn)確解為 。解 用 J 法計(jì)算，按（6.2.8）有用 GS 法計(jì)算，按（6.2.9）有 取 ，J 法迭代4次的計(jì)算結(jié)果是GS 法迭代4次的計(jì)算結(jié)果是從計(jì)算結(jié)果看，本例用 GS 法顯然比用 J 法收斂快。 例6.6 用Jacobi迭代法，G-S迭代法解下述方程組精確解 （1） 迭代公式：其中， ，計(jì)算結(jié)果見表6-1。 表6-1 且有 其中， ,（2）G-S迭代公式且有由此例看出，用 G-S迭

12、代法解此方程組比用Jacobi方法解此Ax=b收斂快（即在初始向量 相同，達(dá)到同樣精度，所需迭代次數(shù)較少），這個(gè)結(jié)論只當(dāng)A滿足一定條件時(shí)才是對的。有些方程組,用J-迭代法收斂，而用G-S迭代法卻是發(fā)散的。例如P李259習(xí)題6中2（b）。注：計(jì)算結(jié)果見:表6-2 Jacobi 迭代法和 Gauss-Seidel 迭代法的分量形式供計(jì)算編程用，它們的矩陣形式供研究迭代序列是否收斂等理論分析用。小結(jié)：Jacobi 迭代法Gauss-Seidel 迭代法矩陣形式分量形式矩陣形式分量形式6. 4 超松弛迭代法（SOR方法） 使用迭代法的困難在于難以估計(jì)其計(jì)算量。有時(shí)迭代過程雖然收斂，但由于收斂速度緩慢，

13、使計(jì)算量變得很大而失去使用價(jià)值。因此，迭代過程的加速具有重要意義。逐次超松弛迭代（Successive Over Relaxatic Method，簡稱SOR方法）法，可以看作是帶參數(shù)的高斯塞德爾迭代法，實(shí)質(zhì)上是高斯-塞德爾迭代的一種加速方法。 1超松弛迭代法的基本思想 超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯塞德爾迭代公式的基礎(chǔ)上作一些修改。這種方法是將前一步的結(jié)果 與高斯-塞德爾迭代方法的迭代值 適當(dāng)加權(quán)平均，期望獲得更好的近似值 。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應(yīng)用。 其具體計(jì)算公式如下： 用高斯塞德爾迭代法定義輔助量。 把 取為 與 的加權(quán)平均，即 合并表示

14、為： 式中系數(shù)稱為松弛因子，當(dāng)=1時(shí)，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0 2。 當(dāng)0 1時(shí)，低松弛法；當(dāng)1 2時(shí)稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR) 2 超松弛迭代法的矩陣表示設(shè)線性方程組 的系數(shù)矩陣A非奇異,且主對角元素 ,則將A分裂成A=D-L-U, 則超松弛迭代公式用矩陣表示為或 故 顯然對任何一個(gè)值,(D+L)非奇異,(因?yàn)榧僭O(shè) )于是超松弛迭代公式為 例* 用SOR法求解線性方程組 取=1.46，要求 解：SOR迭代公式 k = 0,1,2,， 初值 該方程組的精確解只需迭代20次便可達(dá)到精度要求. 如果取=1(即高斯塞德爾迭代法)和同一初值 ,要達(dá)到同樣精

15、度, 需要迭代110次.6.3 迭代法的收斂性 我們知道, 對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂。現(xiàn)在分析它們的收斂性。 對于方程組 經(jīng)過等價(jià)變換構(gòu)造出的等價(jià)方程組 在什么條件下迭代序列 收斂？如果，當(dāng) 時(shí) 存在極限 則稱迭代法是收斂的，否則就是發(fā)散的。收斂時(shí)，在迭代公式中當(dāng) 時(shí)， ,則 , 故 是方程組 的解。從而由此可見當(dāng)時(shí)，如果，那么，從而反過來，如果()，那么由的任意性，定理1 對任意的初始向量迭代公式 收斂的充分必要條件是 .不過，對過判別是否趨于零，運(yùn)算量很大實(shí)際上，利用的約當(dāng)標(biāo)準(zhǔn)型，可以證明下面的定理定理2

16、迭代公式 收斂的充分必要條件是迭代矩陣B的譜半徑由此定理可知，不論是雅可比迭代法、高斯塞德爾迭代法還是超松弛迭代法，它們收斂的充要條件是其迭代矩陣的譜半徑 。 有時(shí)實(shí)際判別一個(gè)迭代法是否收斂，條件 是很難檢驗(yàn)的。而一些矩陣范數(shù) 可以用 B 的元素表示，所以用 作為收斂的充分條件較為方便。定理3 (迭代法收斂的充分條件)若迭代矩陣B的一種范數(shù) ,則迭代公式收斂,且有誤差估計(jì)式,且有誤差估計(jì)式 及 證: 矩陣的譜半徑不超過矩陣的任一種范數(shù),已知 ,因此 ,根據(jù)定理2可知迭代公式收斂又因?yàn)?, 則det (I-B)0, I-B為非奇異矩陣,故xBxf 有惟一解 , 即與迭代過程 相比較, 有兩邊取范

17、數(shù) 由迭代格式，有 兩邊取范數(shù)，代入上式，得 證畢 由定理知，當(dāng) 時(shí)，其值越小，迭代收斂越快，在程序設(shè)計(jì)中通常用相鄰兩次迭代 （為給定的精度要求）作為控制迭代結(jié)束的條件. 例6.8 已知線性方程組 考察用Jacobi迭代和G-S迭代求解時(shí)的收斂性解: 雅可比迭代矩陣 故Jacobi迭代收斂 將系數(shù)矩陣分解 則高斯-塞德爾迭代矩陣 故高斯塞德爾迭代收斂。 定理嚴(yán)格對角占優(yōu)線性方程組 的雅可比迭代公式、高斯-賽德爾迭代公式均收斂。定理5 的系數(shù)矩陣A是對稱正定矩陣，則雅可比迭代公式收斂的充要條件是2D-A也是對稱正定矩陣，SQR法收斂的充要條件是02 。定理6 設(shè)A是不可約對角占優(yōu)矩陣， 那么Ja

18、cobi迭代法與GS迭代法都收斂.定理7 設(shè)A是n階正定矩陣，那么，GS迭代法收斂.下面補(bǔ)充幾個(gè)常用結(jié)論注意的問題（2）Jacobi迭代法和Gauss-Seidel迭代法的收斂性沒有必然的聯(lián)系： 即當(dāng)Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)， Gauss-Seidel法也可能不收斂。（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩陣不同：BJ =D-1(L+U), B G-S = (D-L) -1U舉例用Jacobi迭代法求解不收斂，但用 Gauss-Seidel法收斂。用Jacobi迭代法求解收斂，但用 Gauss-Seidel法不收

19、斂。 BJ的特征值為0，0，0， 而BGS的特征值為 0，2，2本章小結(jié) 本章介紹了解線性方程組 迭代法的一些基本理論和具體方法。迭代法是一種逐次逼近的方法，即對任意給定的初始近似解向量，按照某種方法逐步生成近似解序列，使解序列的極限為方程組的解。注意到在使用迭代法解方程組時(shí)，其迭代矩陣B和迭代向量f在計(jì)算過程中始終不變,迭代法具有循環(huán)的計(jì)算公式,方法簡單，程序?qū)崿F(xiàn)方便，它的優(yōu)點(diǎn)是能充分利用系數(shù)的稀疏性,適宜解大型稀疏系數(shù)矩陣的方程組。 迭代法不存在誤差累積問題。使用迭代法的關(guān)鍵問題是其收斂性與收斂速度，收斂性與迭代初值的選取無關(guān)，這是比一般非線性方程求根的優(yōu)越之處。在實(shí)際計(jì)算中，判斷一種迭代

20、格式收斂性較麻煩，由于求迭代的譜半徑時(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ù)值算法。補(bǔ)例 考察用雅可比迭代法和高斯-塞德爾迭代 法解線性方程組Ax=b的收斂性，其中解： 先計(jì)算迭代矩陣求特征值雅可比矩陣 ( BJ) = 0 1 用高斯-塞德爾迭代法求解時(shí)，迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值 Ax=b的系數(shù)矩陣按行嚴(yán)格對角占優(yōu),故高斯-塞德爾迭代收斂補(bǔ)

21、例設(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 所以該迭代格式收斂。當(dāng)時(shí)a1時(shí),Jacobi矩陣BJ1,對初值x(0)均收斂補(bǔ)例3 設(shè) 方程組 寫出解方程組的Jacobi迭代公式和迭代矩陣 并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討 論迭代收斂的條件。解 Jacobi迭代公式和Jacobi矩陣分別為 也可用矩陣的譜半徑p(GS)1來討論補(bǔ)例3 設(shè) 方程組 寫出解方程組的Gauss-Seidel迭代矩陣，并討論 迭代收斂的條件。解 Gauss-Seidel矩陣為 當(dāng)時(shí) a 1時(shí), Ga