第六章 線性方程組的迭代法.ppt

1、,我們知道，凡是迭代法都有一個收斂問題，有時某種方法對一類方程組迭代收斂，而對另一類方程組進(jìn)行迭代時就會發(fā)散。一個收斂的迭代法不僅具有程序設(shè)計(jì)簡單，適于自動計(jì)算，而且較直接法更少的計(jì)算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。,第六章 解線性方程組的迭代法,迭代法的基本思想 迭代法的基本思想是將線性方程組轉(zhuǎn)化為便于迭代的等價方程組，對任選一組初始值 ，按某種計(jì)算規(guī)則，不斷地對所得到的值進(jìn)行修正，最終獲得滿足精度要求的方程組的近似解。,6.1 迭代法的基本概念6.1.1 引 言,考慮線性方程組,（1.1）,其中A為非奇異矩陣，當(dāng)A為

2、低階稠密矩陣時，第5章所討 論的選主元消去法是有效方法.,但對于A的階數(shù)n很大，零元素較多的大型稀疏矩陣 方程組，例如求某些偏微分方程數(shù)值解所產(chǎn)生的線性方程 組來說，利用迭代法求解則更為合適.,迭代法通常都可利用A中有大量零元素的特點(diǎn).,例1,（1.2）,記為 ,方程組的精確解是 .,求解方程組,其中,現(xiàn)將(1.2)改寫為,（1.3）,或?qū)憺?,其中,將這些值代入(1.3) 式右邊 (若(1.3)式為等式即求得方程組的解，但一般不滿足).,任取初始值，例如取 .,再將 分量代入(1.3)式右邊得到 ，反復(fù)利用這個計(jì) 算程序，得到一向量序列和一般的計(jì)算公式(迭代公式),得到新的值,（1.4）,簡

3、寫為,其中 表示迭代次數(shù),迭代到第10次有,x1(1)=0;x2(1)=0;x3(1)=0; for k=1:10 x1(k+1)=(3*x2(k)-2*x3(k)+20)/8; x2(k+1)=(-4*x1(k)+x3(k)+33)/11; x3(k+1)=(-6*x1(k)-3*x2(k)+36)/12; end x1 =0 2.50000000000000 2.87500000000000 3.13636363636364 3.02414772727273 3.00032283057851 2.99375322830578 2.99902857344102 3.0002001182733

4、8 3.00028156796144 3.00003181406973 x2 =0 3.00000000000000 2.36363636363636 2.04545454545455 1.94783057851240 1.98398760330578 1.99997065176559 2.00262079733283 2.00063785719469 1.99991182189570 1.99987401861081 x3 =0 3.00000000000000 1.00000000000000 0.97159090909091 0.92045454545455 1.000968491735

5、54 1.00384168388430 1.00313072290571 0.99983051394628 0.99974047656463 0.99988126054535,從此例看出，由迭代法產(chǎn)生的向量序列 逐步逼近,方程組的精確解 .,對于任何由 變形得到的等價方程組 ，,迭代法產(chǎn)生的向量序列 不一定都能逐步逼近方程組 的解 .,如對方程組,構(gòu)造迭代法,則對任何的初始向量，得到的序列都不收斂.,對于給定方程組 ，,設(shè)有唯一解 ，,（1.5）,又設(shè) 為任取的初始向量，,（1.6）,其中 表迭代次數(shù).,則,按下述公式構(gòu)造向量序列,x1(1)=0;x2(1)=0; for k=1:10 x1(

6、k+1)=2*x2(k)+5; x2(k+1)=3*x1(k)+5; end,定義1,(1) 對于給定的方程組,逐步代入求近似解的方法稱為迭代法(或稱為一階定常迭代 法，這里 與 無關(guān)).,(2) 如果 存在(記為 )，,顯然 就是方程組的解，否則稱此迭代法發(fā)散.,，用公式(1.6),稱此迭代法收斂，,研究 的收斂性.,引進(jìn)誤差向量,由(1.6)減去(1.5)式，,得 ，,要考察 的收斂性, 就要研究 在什么條件下有,亦即要研究 滿足什么條件時有,遞推得,6.1.2 向量序列與矩陣序列的極限,設(shè),（3.1）,其中 為非奇異矩陣，,記 為(3.1)精確解，,于是,（3.2）,且設(shè)有等價的方程組,

7、設(shè)有解 的一階定常迭代法,（3.3）,問題是： 迭代矩陣 滿足什么條件時，由迭代法產(chǎn)生 的向量序列 收斂到,引進(jìn)誤差向量,由(3.3)式減(3.2)式得到誤差向量的遞推公式,由6.1節(jié)可知，研究迭代法(3.3)收斂性問題就是要研究,迭代矩陣 滿足什么條件時，有,定義2,設(shè)有矩陣序列 及 ,如果 個數(shù)列極限存在且有,則稱 收斂于 ，,記為,例4,且設(shè) ，考查其極限.,解,由于，當(dāng) 時，有,設(shè)有矩陣序列,所以,矩陣序列極限概念可以用矩陣算子范數(shù)來描述.,定理1,證明,再利用矩陣范數(shù)的等價性，可證定理對其他算子范數(shù)亦對.,其中為矩陣的任意一種算子范數(shù).,顯然有,6.1.3 迭代法及其收斂性,設(shè)有,（

8、2.1）,其中， 為非奇異矩陣.,將 分裂為,（2.2）,其中， 為可選擇的非奇異矩陣，且使 容易求解，,一般選擇為 的某種近似，稱 為分裂矩陣.,于是，求解 轉(zhuǎn)化為求解 ，,即求解,可構(gòu)造一階定常迭代法,（2.3）,其中,稱 為迭代法的迭代矩陣.,選取 陣，就得到解 的各種迭代法.,定理5,（3.4）,(迭代法基本定理),設(shè)有方程組,及一階定常迭代法,（3.5）,對任意選取初始向量 ，,矩陣 的譜半徑,迭代法(3.5)收斂的充要條件是,證明,設(shè) ，,易知,)有唯一解，,記為 ，,充分性.,(其中,則,誤差向量,由設(shè) ，,應(yīng)用定理3，有,于是對任意 ,有 ，,必要性.,設(shè)對任意 有,其中,即,

9、顯然，極限 是方程組(3.4)的解，,且對任意 有,由定理2知,再由定理3，即得,定理5,及一階定常迭代法,如果有 的某種算子范數(shù) ，,(1) 迭代法收斂，,即對任取 有,(迭代法收斂的充分條件),設(shè)有方程組,則,證明, (2) 由關(guān)系式 及,反復(fù)利用(b)即得(2).,(1) 由基本定理4結(jié)論(1)是顯然的.,有,(3) 考查,即,(4) 反復(fù)利用(a), 則得到(4).,收斂速度,第 k 步的誤差：,平均每次迭代后的誤差壓縮率約為：,收斂速度,定義：迭代格式 x(k+1) = Bx(k) + f 的平均收斂速度為,漸進(jìn)收斂速度為,(B) 越小，收斂越快,6.2 雅可比（Jacobi）迭代法

10、 6.2.1 雅可比迭代法算法構(gòu)造,例2 用雅可比迭代法求解方程組,解：從方程組的三個方程中分離出 和,建立迭代公式,考察一般的方程組，將n元線性方程組,寫成,若 ,分離出變量,據(jù)此建立迭代公式,上式稱為解方程組的Jacobi迭代公式。,6.2.2 雅可比迭代法的矩陣表示 設(shè)方程組 的系數(shù)矩陣A非奇異，且主對角元素 ,則可將A分裂成,記作 A = D - L - U,則 等價于,即,因?yàn)?，則,這樣便得到一個迭代公式,令,則有,（k = 0,1,2）,稱為雅可比迭代公式, B稱為雅可比迭代矩陣,雅可比迭代矩陣表示法，主要是用來討論其收斂性，實(shí)際計(jì)算中，要用雅可比迭代法公式的分量形式。即,(k=

11、0,1,2,),6.2.1 雅可比迭代法的算法實(shí)現(xiàn), 6.2.2 高斯-塞德爾（Gauss-Seidel）迭代法 高斯-塞德爾迭代法的基本思想 在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求 時用新分量 代替舊分量 , 就得到高斯-賽德爾迭代法。其迭代法格式為：,(i=1,2,n k=0,1,2,),GaussSeidel 迭代法的矩陣表示 將A分裂成A =D-L-U，則 等價于 (D-L-U )x = b 于是,則高斯塞德爾迭代過程,因?yàn)?,所以,則高斯-塞德爾迭代形式為：,故,令,高斯塞德爾迭代算法實(shí)現(xiàn): 高斯-塞德爾迭代算法的計(jì)算步驟與流

12、程圖與雅可比迭代法大致相同，只是一旦求出變元 的某個新值 ,就改用新值 替代老值 進(jìn)行這一步剩下的計(jì)算。,例2,按高斯-塞德爾迭代公式,迭代7次，得 ，,（1.2）,用高斯-塞德爾迭代法解線性方程組(1.2).,取 ，,由此例可知，用高斯-塞德爾迭代法，雅可比迭代法解 線性方程組(1.2)(且取 )均收斂.,而高斯-塞德爾迭代法比雅可比迭代法收斂較快(即取 相同，達(dá)到同樣精度所需迭代次數(shù)較少).,但這結(jié)論只當(dāng) 滿足一定條件時才是對的.,且, 6.3 超松弛迭代法（SOR方法） 使用迭代法的困難在于難以估計(jì)其計(jì)算 量。有時迭代過程雖然收斂，但由于收斂速 度緩慢，使計(jì)算量變得很大而失去使用價值 。

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

14、弛因子，當(dāng)=1時，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0 2。 當(dāng)0 1時，低松弛法；當(dāng)1 2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。,6.3.2 超松弛迭代法對應(yīng)的矩陣表示,選取分裂矩陣 為帶參數(shù)的下三角陣,其中 為可選擇的松弛因子.,于是，由(2.3)可構(gòu)造一個迭代法，其迭代矩陣為,從而得到解 的逐次超松弛迭代法(Successive Over Relaxation Method, 簡稱SOR方法).,解 的SOR方法為,（2.10）,其中,研究解 的SOR迭代法的分量計(jì)算公式.,記,或,由(2.10)式可得,由此，得到解 的SOR方法的計(jì)算公式,（2.11）,或,（

15、2.12）,關(guān)于SOR迭代法 ， 有,(1) 顯然，當(dāng) 時，SOR方法即為高斯-塞德爾迭 代法.,(2) SOR方法每迭代一次主要運(yùn)算量是計(jì)算一次矩陣與向量的乘法.,(3) 當(dāng) 時，稱為超松弛法；當(dāng) 時，稱為低 松弛法.,(4) 在計(jì)算機(jī)實(shí)現(xiàn)時可用,控制迭代終止，或用 控制迭代 終止.,SOR迭代法是高斯-塞德爾迭代法的一種修正.,設(shè)已知 及已計(jì)算 的分量,(1) 首先用高斯-塞德爾迭代法定義輔助量,（2.13）,(2) 再由 與 加權(quán)平均定義 ，,將(2.13)代入(2.14)得到解 的SOR迭代(2.11)式.,即,（2.14）,例3,它的精確解為,取 ，迭代公式為,用SOR方法解方程組,

16、解,取 ，,取其他 值，迭代次數(shù)如下表.,第11次迭代結(jié)果為,從此例看到，松弛因子選擇得好，會使SOR迭代法的 收斂大大加速. 本例中 是最佳松弛因子., 6.4 迭代法的收斂性 我們知道, 對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。 對于方程組 經(jīng)過等價變換構(gòu)造出的等價方程組,在什么條件下迭代序列 收斂？先引入 如下定理,由此定理可知，不論是雅可比迭代法、高斯 塞德爾迭代法還是超松弛迭代法，它們收斂的 充要條件是其迭代矩陣的譜半徑 。,事實(shí)上, 在例1中, 迭代矩陣G= ， 其特征多項(xiàng)式為 ,特征值為

17、-2，-3， , 所以迭代發(fā)散,定理6 (迭代法收斂的充分條件) 若迭代矩陣G的一種范數(shù) ,則迭代公式 收斂,且有誤差估計(jì)式,且有誤差估計(jì)式,及,由定理知，當(dāng) 時，其值越小，迭代收斂越快，在程序設(shè)計(jì)中通常用相鄰兩次迭代 為給定的精度要求）作為控制迭代結(jié)束的條件,例5 已知線性方程組,考察用Jacobi迭代和G-S迭代求解時的收斂性 解: 雅可比迭代矩陣,故Jacobi迭代收斂, 將系數(shù)矩陣分解,則高斯-塞德爾迭代矩陣,故高斯塞德爾迭代收斂。,定理8 設(shè)n階方陣 為嚴(yán)格對角占優(yōu)陣, 則 非奇異 證: 因A為對角占優(yōu)陣, 其主對角元素的絕對值大 于同行其它元素絕對值之和, 且主對角元素 全不為0,

18、 故對角陣 為非奇異。 作矩陣,利用對角占優(yōu)知,由定理知 非奇異,從而A非奇異,證畢 系數(shù)矩陣為嚴(yán)格對角占優(yōu)陣的線性方程組稱作對角 占優(yōu)方程組。,結(jié)論： 嚴(yán)格對角占優(yōu)線性方程組 的雅可比 迭代公式和高斯-賽德爾迭代公式均收斂。,定理9 若矩陣A按行(或列)嚴(yán)格對角占優(yōu),或按行(或列)弱對角占優(yōu)不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。,證明 若矩陣A按行嚴(yán)格對角占優(yōu)，或按行(或列)弱對角占優(yōu)不可約，則GS迭代收斂。假若不然，(BG)1，即迭代矩陣BG的某一特征值使得|1，并且,類似地，若矩陣A按行嚴(yán)格對角占優(yōu)，或按行(或列)弱對角占優(yōu)不可約，則Jacobi迭代收斂。假若不

19、然，(BJ)1，即迭代矩陣BJ的某一特征值使得|1，并且,定理12 對于線性方程組Ax=b，若A為對稱正定矩陣，則當(dāng)02時，SOR迭代收斂.,證明 只需證明1（其中為L的任一特征值）.,定理13 對于線性代數(shù)方程組Ax=b， 若A按行(或列)嚴(yán)格對角占優(yōu)，或按行(或列)弱對角占優(yōu)不可約；則當(dāng)0w1時，SOR迭代收斂。,例6 設(shè) ,證明, 求解方程組,的Jacobi迭代與G-S迭代同時收斂或發(fā)散,證:雅可比迭代矩陣,其譜半徑,例6設(shè) ,證明, 求解方程組,的Jacobi迭代與G-S迭代同時收斂或發(fā)散,證: G-S迭代矩陣,其譜半徑,顯然, 和 同時小于、等于或大于1,因而Jacobi迭代法與G-

20、S迭代法具有相同的收斂性,例7 設(shè)求解線性方程組的雅可比迭代 x(k+1)=B x(k)+f k=0,1, 求證當(dāng)B 1時, 相應(yīng)的G-S迭代收斂 證 這里以B 為例, B1類似 由于B是雅可比迭代的迭代矩陣，故有, Ax=b 的系數(shù)矩陣按行嚴(yán)格對角占優(yōu), 故高斯-塞德爾迭代收斂,例 8 考察用雅可比迭代法和高斯-塞德爾迭代 法解線性方程組Ax=b的收斂性，其中,解： 先計(jì)算迭代矩陣,求特征值,雅可比矩陣, ( B ) = 0 1 用雅可比迭代法求解時，迭代過程收斂,1=0,2 =2,3 =2 (G1)=21 用高斯-塞德爾迭代法求解時，迭代過程發(fā)散,高斯-塞德爾迭代矩陣,求特征值, Ax=b

21、的系數(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)出(B)1, 從而說明迭代格式收斂。 證: 因?yàn)锽=I-A, 故(B)= (I)- (A)=1 - (A) (A) + (B) = 1 由于已知(A) 和 (B)全為正數(shù)，故 0(B)1 ,從而 (B) 1 所以該迭代格式收斂。,當(dāng)時a1時,Jacobi矩陣GJ1,對初值x(0)均收斂,例10 設(shè) 方程組 寫出解方程組的Jacobi迭代公式和迭代矩陣

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

23、1， 2,3 = 1/2,求特征值,高斯-塞德爾迭代矩陣, (G1) = 0.3536 1 用高斯-塞德爾迭代法求解時，迭代過程收斂,1=0,求解AX=b,當(dāng)取何值時迭代收斂？ 解:所給迭代公式的迭代矩陣為,例12 給定線性方程組 AX= b 用迭代公式 X(K+1)=X(K)+(b-AX(K) (k=0,1,）,即 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迭代收斂,例13 設(shè)求解線性方程組Ax=b的簡單迭代法 x(k+1)=Bx(k)+g ( k=0,1, 2, ) 收斂, 求證: 對01, 迭代法 x(k+1)=(1- )I+ Bx(k)+ g ( k=0,1, 2, ) 收斂。 證: 設(shè)C= (1- )I+ B, (C)和(B)分別為C和B 的特征值，則顯然 (C) =(1- )+ (B) 因?yàn)?1, (C) 是1和(B) 的加權(quán)平均, 且由迭