第6章線性方程組的迭代解法

1、2022-2-5第六章 線性方程組的迭代解法1第六章第六章 線性方程組的迭代解法線性方程組的迭代解法1 向量和矩陣的范數(shù)向量和矩陣的范數(shù) 1.1 1.1 向量的范數(shù)向量的范數(shù) 1.2 1.2 矩陣的范數(shù)矩陣的范數(shù)2 迭代解法與收斂性迭代解法與收斂性 2.1 2.1 迭代法的構(gòu)造迭代法的構(gòu)造 2.2 2.2 迭代法的收斂性條件迭代法的收斂性條件3 常用的三種迭代解法常用的三種迭代解法 2.1 Jacobi2.1 Jacobi迭代法迭代法 2.2 Gauss-Seidel2.2 Gauss-Seidel迭代法迭代法 2.2 2.2 超松弛超松弛(SOR)(SOR)迭代法迭代法2022-2-5第六章

2、 線性方程組的迭代解法21 向量和矩陣的范數(shù)向量和矩陣的范數(shù)一、向量的范數(shù)一、向量的范數(shù) 為了對線性方程組數(shù)值解的精確程度，以及方程組為了對線性方程組數(shù)值解的精確程度，以及方程組本身的性態(tài)進(jìn)行分析，需要對向量和矩陣的本身的性態(tài)進(jìn)行分析，需要對向量和矩陣的“大小大小”引引進(jìn)某種度量，進(jìn)某種度量，范數(shù)范數(shù)就是一種度量尺度，就是一種度量尺度，向量和矩陣的范向量和矩陣的范數(shù)數(shù)在線性方程組數(shù)值方法的研究中起著重要的作用。在線性方程組數(shù)值方法的研究中起著重要的作用。 定義定義6.1設(shè)設(shè)|是向量空間是向量空間Rn上的上的實值函數(shù)實值函數(shù)，且滿足條件，且滿足條件 求解線性方程組的數(shù)值解除了使用直接解法，迭代解

3、求解線性方程組的數(shù)值解除了使用直接解法，迭代解法也是經(jīng)常采用的一種方法，這種方法更有利于編程計法也是經(jīng)常采用的一種方法，這種方法更有利于編程計算，本章將介紹這種方法。算，本章將介紹這種方法。2022-2-5第六章 線性方程組的迭代解法3則稱則稱 | 為為 Rn 空間上的范數(shù)空間上的范數(shù)，| x |為向量為向量 x 的范數(shù)的范數(shù)。 理論上存在多種多樣的向量范數(shù)，但最常用的是如下理論上存在多種多樣的向量范數(shù)，但最常用的是如下三種。三種。（2）齊次性齊次性：對任何實數(shù)和向量：對任何實數(shù)和向量x | x| | | x |（3）三角不等式三角不等式：對任何向量：對任何向量x和和y，都有都有 | xy |

4、 x | y |設(shè)向量設(shè)向量x（x1，x2，xn）T，定義定義 （1）非負(fù)性非負(fù)性：對任何向量：對任何向量 x， | x |0，且，且| x |0當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x0可引進(jìn)極限可引進(jìn)極限2022-2-5第六章 線性方程組的迭代解法4向量向量1-范數(shù)范數(shù)： niixx1121122 niixx向量向量2-范數(shù)范數(shù)： 向量向量-范數(shù)范數(shù)： inixx 1max容易驗證，以上容易驗證，以上三種范數(shù)三種范數(shù)都滿足向量范數(shù)的三個條件。都滿足向量范數(shù)的三個條件。 例例6.1 設(shè)設(shè)x（1，3，2，0）T，求向量范數(shù)求向量范數(shù)| x |p，P1，2，。 歐氏范數(shù)歐氏范數(shù)最大范數(shù)最大范數(shù)(0,0)O12( ,)

5、A x xB2xx 2022-2-5第六章 線性方程組的迭代解法5 解解: :對于對于 向量向量 x(1，3，2，0)T ，根據(jù)定義，根據(jù)定義可以計算出：可以計算出： | x|1| 1 |3 | 2 | 0 |6 1402312122222 x 30,2,3,1max x 由此例可見，向量不同范數(shù)的值不一定相同，但這并不由此例可見，向量不同范數(shù)的值不一定相同，但這并不影響對向量大小做定性的描述，因為不同范數(shù)之間存在如影響對向量大小做定性的描述，因為不同范數(shù)之間存在如下等價關(guān)系下等價關(guān)系。 2022-2-5第六章 線性方程組的迭代解法6定義定義（范數(shù)的等價性）（范數(shù)的等價性） Rn上兩種范數(shù)上兩

6、種范數(shù)| 和和| 稱為等價稱為等價的的，如果存在著正數(shù)如果存在著正數(shù) m，M，使得使得： nRxxMxxm , 范數(shù)的等價性表明，范數(shù)的等價性表明，一個向量若按某種范數(shù)是一個小一個向量若按某種范數(shù)是一個小量，則它按任何一種范數(shù)也將是一個小量量，則它按任何一種范數(shù)也將是一個小量。（等價有傳遞。（等價有傳遞性）容易證明，常用的三種向量范數(shù)滿足下述等價關(guān)系。性）容易證明，常用的三種向量范數(shù)滿足下述等價關(guān)系。 | x | | x |1 n| x | x | | x |2 | x | x | 2| x |1 n| x |2 niixx11例如例如：inixn 1max xnnn1定理定理6.2 n維向量

7、維向量x的的一切范數(shù)都等價一切范數(shù)都等價2022-2-5第六章 線性方程組的迭代解法7定義定義6.2 對于向量序列對于向量序列 , 2 , 1,),()()(2)(1)( kxxxxTknkkk*)(limxxkk *)(xxk 向量序列向量序列 x(k) 收斂于向量收斂于向量 x*，當(dāng)且僅當(dāng)它的當(dāng)且僅當(dāng)它的每一每一個分量序列個分量序列收斂于收斂于xi*的對應(yīng)分量，即的對應(yīng)分量，即 nixxxxikik, 2 , 1,*)(*)( Tnxxxx),(*2*1* 及向量及向量0lim*)( xxkk如果如果則稱向量序列則稱向量序列 x(k) 收斂于收斂于向量向量 x* 。記作記作 或或收斂與取哪

8、種范數(shù)無關(guān)收斂與取哪種范數(shù)無關(guān)1()*()*|m ax |inkkiixxxx 2022-2-5第六章 線性方程組的迭代解法8二、矩陣的范數(shù)二、矩陣的范數(shù) 矩陣范數(shù)是反映矩陣范數(shù)是反映矩陣矩陣“大小大小”的一種度量，具體定義如下。的一種度量，具體定義如下。 定義定義6.3 設(shè)設(shè)|是以是以n階矩陣為變量階矩陣為變量的的實值函數(shù)實值函數(shù)，且滿足，且滿足條件：條件： （1）| A |0，且，且| A |0時，當(dāng)且僅當(dāng)時，當(dāng)且僅當(dāng)A0 （2）|A| | A|，R （3）|AB| | A | B | （4）| AB | A | | B |則稱則稱| A |為矩陣為矩陣A的的范數(shù)范數(shù)。可定義矩可定義矩陣極

9、限陣極限2022-2-5第六章 線性方程組的迭代解法9設(shè)設(shè) n 階矩陣階矩陣 A（aij），常用的矩陣范數(shù)有：），常用的矩陣范數(shù)有： 矩陣矩陣1-范數(shù)范數(shù)： niijnjaA111|max( () )122TAA A= =的的最最大大特特征征值值矩陣矩陣2-范數(shù)范數(shù)： njijniaA11|max矩陣矩陣-范數(shù)范數(shù)： 以上三種范數(shù)都滿足矩陣范數(shù)的條件，通常將這三種以上三種范數(shù)都滿足矩陣范數(shù)的條件，通常將這三種矩陣范數(shù)統(tǒng)一表示為矩陣范數(shù)統(tǒng)一表示為| A |p，P1，2，。 列和列和行和行和譜范數(shù)譜范數(shù). 不好不好算理論上重要算理論上重要2022-2-5第六章 線性方程組的迭代解法10例例6.2

10、設(shè)矩陣設(shè)矩陣 4321A求矩陣求矩陣A的范數(shù)的范數(shù)| A |p，P1，2，。 解解 根據(jù)定義根據(jù)定義 6|4|2|,3|1|max1 A 43214231AAT由于由于 7|4|3|,2|1|max A 20141410則它的特征方程為則它的特征方程為: 0430201414102 AAIT2022-2-5第六章 線性方程組的迭代解法11此方程的根為矩陣此方程的根為矩陣ATA的特征值，解得的特征值，解得 221151 221152 因此因此 46522115212.A 在線性方程組的研究中，經(jīng)常遇到矩陣與向量的乘積在線性方程組的研究中，經(jīng)常遇到矩陣與向量的乘積運算，若將運算，若將矩陣范數(shù)矩陣范

11、數(shù)與與向量范數(shù)向量范數(shù)關(guān)聯(lián)起來，將給問題的分關(guān)聯(lián)起來，將給問題的分析帶來許多方便。設(shè)析帶來許多方便。設(shè)|是一種向量范數(shù)，由此范數(shù)派生是一種向量范數(shù)，由此范數(shù)派生的的矩陣范數(shù)定義矩陣范數(shù)定義為為 xAxAx0max (也稱為也稱為A的的算子范數(shù)算子范數(shù)) 此式左端此式左端|A|表示矩陣范數(shù)，而右端表示矩陣范數(shù)，而右端是向量是向量Ax 和和 x 的范數(shù)，利用向量范數(shù)所具有的性質(zhì)不難的范數(shù)，利用向量范數(shù)所具有的性質(zhì)不難驗證，由上式定義的驗證，由上式定義的矩陣范數(shù)矩陣范數(shù)滿足滿足矩陣范數(shù)的條件矩陣范數(shù)的條件。2022-2-5第六章 線性方程組的迭代解法12,nA xAxxR 通常將滿足上式的矩陣范數(shù)稱

12、為與向量范數(shù)通常將滿足上式的矩陣范數(shù)稱為與向量范數(shù)相容的相容的矩陣范矩陣范數(shù)。數(shù)。 可以證明，前述的三種矩陣范數(shù)可以證明，前述的三種矩陣范數(shù)| A |p，P1，2，就是由就是由向量范數(shù)向量范數(shù)| x |p派生出的矩陣范數(shù)，即派生出的矩陣范數(shù)，即 ,2,1,max0pxAxAppxp通過向量范數(shù)定義的矩陣范數(shù)，滿足不等式關(guān)系：通過向量范數(shù)定義的矩陣范數(shù)，滿足不等式關(guān)系：均為均為相容范數(shù)相容范數(shù)，即，即 ,2,1,pxAAxppp 可以證明可以證明, ,對方陣對方陣 和和 有有: nnRAnxR22|FAxAx2,1|nFiji jAa ( (向量向量2- -范數(shù)直接推廣范數(shù)直接推廣) )Frob

13、enius范數(shù)范數(shù): :2022-2-5第六章 線性方程組的迭代解法13三、矩陣的譜半徑三、矩陣的譜半徑 矩陣范數(shù)同矩陣特征值之間有密切的聯(lián)系，設(shè)矩陣范數(shù)同矩陣特征值之間有密切的聯(lián)系，設(shè)是矩是矩陣陣A相應(yīng)于相應(yīng)于特征向量特征向量x的特征值，即的特征值，即 Axx,于是利用于是利用向量向量-矩陣范數(shù)的相容性，得到矩陣范數(shù)的相容性，得到| | x |x|從而，對從而，對A的的任何特征值任何特征值均成立均成立=| Ax| | A | |x| A | （6.1） 設(shè)設(shè)n階矩陣階矩陣A的的n個特征值為個特征值為1,2，n。稱。稱iniA 1max)(為矩陣為矩陣A的的譜半徑譜半徑，從（，從（6.1）式得

14、知，對矩陣）式得知，對矩陣A的任何一的任何一種相容范數(shù)都有種相容范數(shù)都有 (A)|A| （6.2）特征值上界特征值上界2022-2-5第六章 線性方程組的迭代解法14 另一個更深刻的結(jié)果另一個更深刻的結(jié)果,對于任意的對于任意的0，必存在一種相，必存在一種相容的矩陣范數(shù)，使容的矩陣范數(shù)，使| A | (A) （6.3） 式（式（6.2）和（）和（6.3）表明，矩陣）表明，矩陣A的的譜半徑譜半徑是它所有相是它所有相容范數(shù)的容范數(shù)的下確界下確界。定義定義6.4 設(shè)有設(shè)有nn矩陣序列矩陣序列 和和n階階方陣方陣A（aij）, 如果如果 ()()(),1,2,kkijAak 0|lim)( AAkk記作

15、記作 A（k）A，或，或 A（k）A。 klim稱稱 A（k）收斂于收斂于A， 定理：定理：設(shè)有設(shè)有nn矩陣序列矩陣序列 收斂于收斂于nn矩陣矩陣A（aij）的充要條件為）的充要條件為 ()()(),1,2,kkijAak n,j, i,aalimij)k(ijk21 2022-2-5第六章 線性方程組的迭代解法15121221.00012xxxx 121221.00012.0001xxxx 中擾動對結(jié)果的影響方程組bAx 0, 221xx1, 121xx擾動擾動( (改變量改變量) )解對原始數(shù)解對原始數(shù)據(jù)變化敏感據(jù)變化敏感四、矩陣的條件數(shù)四、矩陣的條件數(shù)如何定量描述這種現(xiàn)象？擾動（誤差）對

16、解的影響如何定量描述這種現(xiàn)象？擾動（誤差）對解的影響有多大？有多大？2022-2-5第六章 線性方程組的迭代解法16 引進(jìn)了矩陣的度量標(biāo)準(zhǔn)引進(jìn)了矩陣的度量標(biāo)準(zhǔn)范數(shù)范數(shù)，就可以對方程組求，就可以對方程組求解進(jìn)行誤差分析，對于方程組解進(jìn)行誤差分析，對于方程組Ax =b如果常數(shù)項產(chǎn)生了誤差如果常數(shù)項產(chǎn)生了誤差b, 并設(shè)求解時產(chǎn)生的誤差為并設(shè)求解時產(chǎn)生的誤差為x，則有則有A(x + x) =b+ b兩式相減得到兩式相減得到 A x = b當(dāng)系數(shù)矩陣可逆時當(dāng)系數(shù)矩陣可逆時x = A-1b取范數(shù)取范數(shù)|x| = |A-1b| |A-1 | |b|再由再由 Ax =b，得到，得到| b|= | Ax |A

17、| |x|絕對誤差絕對誤差2022-2-5第六章 線性方程組的迭代解法17于是，由于是，由 | x |A-1 | |b|得到解的得到解的相對誤差相對誤差為為bAx 11xbAAxb 及及 |b | |A | |x|令令 Cond(A)=|A | |A-1 | ,并稱其為矩陣并稱其為矩陣A的的條件數(shù)條件數(shù)。這時這時bbACondxx )(可見，求解線性方程組所產(chǎn)生的可見，求解線性方程組所產(chǎn)生的誤差誤差與系數(shù)矩陣的與系數(shù)矩陣的條件數(shù)條件數(shù)有關(guān)。有關(guān)。2022-2-5第六章 線性方程組的迭代解法18 對于線性方程組對于線性方程組 Ax=b，如果系數(shù)矩陣的條件數(shù)如果系數(shù)矩陣的條件數(shù)Cond(A)=|A

18、 | |A-1 | 太大，則稱該方程組為太大，則稱該方程組為病態(tài)方程組。病態(tài)方程組。 病態(tài)現(xiàn)象是方程組的固有屬性，病態(tài)現(xiàn)象是方程組的固有屬性，無法改變無法改變，因此在求，因此在求解時為了不至于產(chǎn)生太大的誤差，應(yīng)該盡量減少原始數(shù)據(jù)解時為了不至于產(chǎn)生太大的誤差，應(yīng)該盡量減少原始數(shù)據(jù) A、b 的誤差，或者用高精度的計算機(jī)計算。的誤差，或者用高精度的計算機(jī)計算。例如：對于方程組例如：對于方程組121221.00012xxxx 系數(shù)矩陣和逆矩陣分別為系數(shù)矩陣和逆矩陣分別為 44441101010101,0001.1111AA可以求得可以求得 1)(AAACond442.0001(1210 )410 條件

19、數(shù)比較大，可見該方程組為條件數(shù)比較大，可見該方程組為病態(tài)方程組病態(tài)方程組。多大算病態(tài)沒有標(biāo)準(zhǔn)。如果主元很小或者元素數(shù)量級相差大，可能是病態(tài)多大算病態(tài)沒有標(biāo)準(zhǔn)。如果主元很小或者元素數(shù)量級相差大，可能是病態(tài)1)(11AAAAAcond2022-2-5第六章 線性方程組的迭代解法192 2 迭代解法與收斂性迭代解法與收斂性一、迭代解法一、迭代解法設(shè)有線性方程組設(shè)有線性方程組 Ax=b (1) ARnn, bRn .對對A 進(jìn)行進(jìn)行， A=A1+A2 , 其中其中 A1 可逆可逆，則則 (A1+A2)x=b A1x = - A2x+b令令 B= - A1-1 A2 , F =A1-1 b則則 x= B

20、x+F (2) x = - A1-1 A2 x + A1-1 b2022-2-5第六章 線性方程組的迭代解法20得到得到 x(1)= Bx(0)+F 稱稱(3)為求解為求解(1)的近似解的的近似解的，稱，稱x(k)為為(1)的的近似解序列，稱近似解序列，稱B為為迭代矩陣迭代矩陣。如果如果*)(limxxkk則有則有 x(2)= Bx(1)+F x(k+1)= Bx(k)+F , k=0 ,1 , , （3）x*= Bx*+F （4）我們稱迭代法我們稱迭代法(3)收斂收斂，否則為，否則為發(fā)散發(fā)散。下面分析迭代格。下面分析迭代格式式(3)收斂的條件收斂的條件. 由由 x= Bx+Fx(0)Rn確定

21、迭代格式確定迭代格式不動點不動點2022-2-5第六章 線性方程組的迭代解法21由由(3) (4)得得 x(k+1) - x* = B(x(k)- x* ) 令令 e(k)= x(k)- x* , 則有則有(1)( )2 (1)1 (0)kkkkeBeB eBe+ +- -+ += = = = =L L若若 x(k+1) x* ,則則 e(k+1) 0。這時只有這時只有 Bk+1 0 （k ）。）。x(k+1)= Bx(k)+F , k=0 ,1 , , （3）x*= Bx*+F （4）而而 Bk+1 0 (B)1，由此可得如下的收斂性條件。，由此可得如下的收斂性條件。2022-2-5第六章

22、線性方程組的迭代解法22二、迭代法收斂性條件二、迭代法收斂性條件 x(k+1)= Bx(k)+F , k=0 ,1 , , （3）定理定理6.3 若若 |B|1 ，則迭代格式，則迭代格式(3)(3)收斂收斂. . 定理定理6.4 若若 |B|1 ，則有估計式，則有估計式 定理定理6.2 迭代法格式迭代法格式(3)(3)收斂的收斂的充要條件充要條件是是(B)1. .（不好算）（不好算） 這是一個這是一個，根據(jù)范數(shù)與譜半徑的關(guān)系式，根據(jù)范數(shù)與譜半徑的關(guān)系式 (B)|B| ，容易推出該充分條件，容易推出該充分條件.()(1)(0)*1 kkBxxxxB)1()()(1* kkkxxBBxx迭代法基迭

23、代法基本定理本定理收斂只與收斂只與B有關(guān)，且有關(guān)，且(B)越小收斂越快越小收斂越快后驗誤后驗誤差估計差估計先驗誤先驗誤差估計差估計( )(0)(0)(0)*()(2)11kkkBBxxBxFxFxBB 2022-2-5第六章 線性方程組的迭代解法233 3 常用的三種迭代解法常用的三種迭代解法一、一、Jacobi迭代法迭代法對于線性方程組對于線性方程組 Ax=b (1) A=L+D+U (2)設(shè)設(shè) det(A) 0 ，aii 0, i=0,1,2,n ，按照如下方式對，按照如下方式對A進(jìn)行分裂：進(jìn)行分裂： 0000002121nnaaaL nnaaaD0000002211 0000002112

24、nnaaaUL ,U稱為嚴(yán)稱為嚴(yán)格下（上）格下（上）三角陣三角陣2022-2-5第六章 線性方程組的迭代解法24則由則由 Ax=b 得到得到令令 BJ=-D-1(L+U) ， FJ= D-1 b.(L+D+U) x=b D x=-(L+U)x+b x=-D-1(L+U)x+ D-1 b則有則有 x= BJ x+ FJ (3)任取初始向量任取初始向量 x(0)Rn , 則可以由上式得到如下的迭代則可以由上式得到如下的迭代格式：格式：并稱其為并稱其為Jacobi迭代格式迭代格式（簡單迭代法（簡單迭代法/ /同步迭代法）同步迭代法），迭，迭代矩陣為代矩陣為 x(k+1)= BJ x(k)+ FJ (

25、4)BJ=-D-1(L+U) = -D-1(A - D)= E - D-1 A2022-2-5第六章 線性方程組的迭代解法25例如例如, 對于三元線性方程組對于三元線性方程組 232131333332312122223132121111xaxabxaxaxabxaxaxabxa 333323213123232221211313212111bxaxaxabxaxaxabxaxaxa )(1)(1)(1232131333332312122223132121111xaxabaxxaxabaxxaxabax2022-2-5第六章 線性方程組的迭代解法26 得到具體的迭代格式得到具體的迭代格式由定理由定

26、理6.4的結(jié)論的結(jié)論, ,可以通過可以通過| x(k+1)-x(k)|控制迭代次數(shù)。控制迭代次數(shù)。x(0)Rn(1)( )( )1112213311(1)( )( )2221123322(1)( )( )33311322331()1()1()kkkkkkkkkxba xa xaxba xa xaxba xa xa ,k210 2022-2-5第六章 線性方程組的迭代解法27對于對于 n 元線性方程組元線性方程組其一般式為：其一般式為：從中解出：從中解出： 得得Jacobi迭代格式迭代格式通過通過 | x(k+1)-x(k)| 控制迭代次數(shù)。控制迭代次數(shù)。)(1111 nijjijijjijii

27、iixaxabax)(11)(11)()1( nijkjijijkjijiiikixaxabaxininiiiiiiiiiibxaxaxaxaxa 111111 nnnnnnnnnbxaxaxabxaxaxabxaxaxa322112222212111212111n,i21 n,i21 n,i21 ,k210 分量形式分量形式2022-2-5第六章 線性方程組的迭代解法28二二、 Gauss-Seidel迭代法迭代法對于三元方程組對于三元方程組，將，將Jacobi迭代格式迭代格式改進(jìn)為改進(jìn)為(1)()()11122133111()kkkxbaxaxa+ += =- - -(1)(1)()222

28、11233221()kkkxbaxaxa+ + += =- - -(1)(1)(1)33311322331()kkkxbaxaxa+ + + += =- - -并稱其為并稱其為Gauss-Seidel迭代格式迭代格式（異步迭代法異步迭代法）。 )(1)(1)(1)(232)(131333)1(3)(323)(121222)1(2)(313)(212111)1(1kkkkkkkkkxaxabaxxaxabaxxaxabax,k210 2022-2-5第六章 線性方程組的迭代解法29對于對于n元方程元方程 先寫出先寫出Jacobi迭代格式迭代格式同樣可以用同樣可以用 | x(k+1)-x(k)|

29、控制迭代次數(shù)?？刂频螖?shù)。 再寫出再寫出Gauss-Seidel迭代格式迭代格式ininiiiiiiiiiibxaxaxaxaxa 111111)(11)(11)()1( nijkjijijkjijiiikixaxabax)(11)(11)1()1( nijkjijijkjijiiikixaxabaxn,i21 ,k210 n,i21 2022-2-5第六章 線性方程組的迭代解法30 為討論為討論收斂性收斂性方便，下面再寫出方便，下面再寫出Gauss-Seidel迭代格迭代格式的式的矩陣表示式矩陣表示式。首先將。首先將Gauss-Seidel迭代格式迭代格式改寫為：改寫為：(1)()()kk

30、LD xUxb+ + += = - -+ +(1)1( )1()()kkxLDUxLDb+ +- - -= = - -+ + + +)(11)(11)1()1( nijkjijijkjijiiikixaxabax nij)k(jiji)k(iiiij)k(jijxabxaxa11111ikninkiiikiiikiiikibxaxaxaxaxa )()(11) 1() 1(11) 1(11n,i21 nnnnaaaaaaDL21222111000(1)1(1)(1)2(1)kkkknxxxx 2022-2-5第六章 線性方程組的迭代解法31令令 11(),()GGBLDU FLD- - -=

31、= - -+ += =+ +則有則有 (1)(),kkGGxB xF+ += =+ +其中其中 BG 為迭代矩陣。為迭代矩陣。(1)1( )1()()kkxLDUxLDb+ +- - -= = - -+ + + + 例例6.3 用用Jacobi迭代法和迭代法和Gauss-Seidel迭代法解下列方迭代法解下列方程組程組,已知方程組得精確解為已知方程組得精確解為 x*=(1，1，1)T 。 141035310214310321321321xxxxxxxxx,k210 2022-2-5第六章 線性方程組的迭代解法32解：先改寫方程如下解：先改寫方程如下再寫出再寫出Jacobi迭代格式迭代格式取初值

32、為取初值為: x(0)=(0，0，0)T , 求得求得:x(1)=(1.4，0.5，1.4)Tx(6)=(1.00025，1.00580，1.00251)T誤差為由誤差為由x*=(1，1，1)T 得到得到 |x(6)-x*|=0.00580 。 123213312114310152310114310 xxxxxxxxx (1)( )( )123(1)( )( )213(1)( )( )312114310152310114310kkkkkkkkkxxxxxxxxx ,k210 2022-2-5第六章 線性方程組的迭代解法33初值也取為初值也取為: x(0)=(0，0，0)T , 求得近似解：求得

33、近似解：Gauss-Seidel迭代格式為迭代格式為誤差為由誤差為由x*=(1，1，1)T 得到得到 |x(4)-x*|=0.00846 。 Jacobi迭代法迭代迭代法迭代6次與次與Gauss-Seidel迭代法迭代迭代法迭代4次的次的精度一致，說明精度一致，說明Gauss-Seidel迭代法收斂較快（迭代法收斂較快（一定條件一定條件下下）,求出求出 后后 不用保存不用保存。x(1)=(1.4，0.78，1.026)Tx(4)=(0.99154，0.99578，1.00210)T (1)( )( )123(1)(1)( )213(1)(1)(1)312114310152310114310kk

34、kkkkkkkxxxxxxxxx ,k210 )1( kjx)(kjx2022-2-5第六章 線性方程組的迭代解法34三三.超松弛超松弛(SOR)迭代法迭代法 (Successive Over Relaxation Method)對對Gauss-Seidel迭代進(jìn)行改寫迭代進(jìn)行改寫令令 nijkjijijkjijiiikixaxabax1)(11)1()1(1 nijkjijkiiiijkjijiiixaxaxaba)()(11)1(1 nijkjijijkjijiiikixaxabax)(11)1()(1 nijkjijijkjijiiikikikixaxabaxxr)(11)1()()1(

35、)(1 即為在即為在第第 k次迭代次迭代時的改變量時的改變量(增量增量)。2022-2-5第六章 線性方程組的迭代解法35再通過再通過加權(quán)加速收斂加權(quán)加速收斂： (1)()()kkkiiixxr+ += =+ +1()(1)()1inkkkiiijjijjjjiiixba xa xa 并稱其為并稱其為超松弛迭代法超松弛迭代法，稱為稱為松弛因子松弛因子。當(dāng)當(dāng) 0 1 時，稱為時，稱為低松弛低松弛； 當(dāng)當(dāng) =1 時，為時，為Gauss-Seidel 迭代格式迭代格式 ；當(dāng)當(dāng) 1 2 時，稱為時，稱為高松弛高松弛。 ,k210 n,i21 )1()()()1()()1(1kikikikikikixx

36、xxxx加權(quán)平均加權(quán)平均2022-2-5第六章 線性方程組的迭代解法36超松弛迭代法超松弛迭代法(SOR)也可以用也可以用矩陣的形式矩陣的形式來表示來表示 (1)1( )1()()()kkxDLD DU x DLb+ +- - -= =+ +- -+ + + +令令 B =(D+ L)-1D- (D+U)則有則有 x(k+1)=B x(k)+F , k=0,1, 2 , 。1(1)()(1)()1inkkkkiiiijjijjjjiiixxba xa xa 1(1)()(1)()1inkkkkiiiiiiiijjijjjjia xa x ba xa x 改寫改寫SOR為為或者或者 (1)()(

37、)()kkDL xD DUxb+ + += =- -+ + +F = (D+L)-1 bn,i21 2022-2-5第六章 線性方程組的迭代解法37(1)11 1( 1)111(1)(1)22 221 1(1)2122(1)21(1)(1)(1)121000()kkkkkknkkknnnnnn nijjnja xaxa xa xaaxL Dxaaaa xa xx F說明：說明： (1)()()()kkDL xD DUxb+ + += =- -+ + +( )11111211( )22222( )2( )00000()0000knknkknnnnnaaaaxaaaxDD U xaax n,i21

38、 2022-2-5第六章 線性方程組的迭代解法38( )11111211( )22222( )2( )( )111( )222( )00000()0000000000knknkknnnnnkkknnnaaaaxaaaxDD U xaaxaxaxax ( )111211( )2222( )( )1( )1111( )( )22222( )( )000knknknnnnkjjkjknkjjjknnnknnnaaaxaaxaxa xa xa xa xa xa x n,i21 2022-2-5第六章 線性方程組的迭代解法39 定理定理6.6 Gauss-Seidel 迭代法迭代法 收斂的收斂的充要條件

39、充要條件是是(BG)1 ，收斂的，收斂的充分條件充分條件是是 |BG|1 。 定理定理6.7 對于對于 線性方程組線性方程組 Ax=b ，如果系數(shù)矩陣，如果系數(shù)矩陣A嚴(yán)格嚴(yán)格對角占優(yōu)對角占優(yōu)，則，則Jacobi、G-S迭代法都收斂。迭代法都收斂。定理定理6.8 SOR迭代法收斂的迭代法收斂的必要條件必要條件是是 0 2 。 定理定理6.9 如果系數(shù)矩陣如果系數(shù)矩陣A對稱對稱正定正定，且，且 0 2 ，則，則SOR 法收斂法收斂定理定理6.10 如果系數(shù)矩陣如果系數(shù)矩陣A對稱正定對稱正定，則，則G-S迭代法收斂。迭代法收斂。四、收斂性條件四、收斂性條件 定理定理6.5 Jacobi迭代法收斂的迭

40、代法收斂的充要條件充要條件是是(BJ)1 ，收斂的收斂的充分條件充分條件是是 |BJ |111/30010010/3()3/41/4 00015/2GBDLU- -輊輊輊輊輊輊- - -犏犏犏犏犏犏= = - -+ += = - -= =犏犏犏犏犏犏- - -臌臌臌臌臌臌10/315det()()0015/22GIB - -= = =+ += =+ +解得特征值解得特征值12150,2= -= -譜半徑譜半徑 (BG)1故故Jacobi迭代法迭代法和和Gauss-Seidel迭代法均發(fā)散迭代法均發(fā)散.但可以交換兩個方程的次序，將原方程變?yōu)橥夥匠探M但可以交換兩個方程的次序，將原方程變?yōu)橥夥匠?/p>

41、組 71035492121xxxx這時方程組得系數(shù)矩陣嚴(yán)格這時方程組得系數(shù)矩陣嚴(yán)格對角占優(yōu)，對角占優(yōu)，兩種迭代法都收斂兩種迭代法都收斂。2022-2-5第六章 線性方程組的迭代解法42例例6.5 用用Jacobi迭代法解下列方程組，問是否收斂？迭代法解下列方程組，問是否收斂？ 解：方程組的系數(shù)矩陣為解：方程組的系數(shù)矩陣為 112130207A 非嚴(yán)格對角占優(yōu)，非嚴(yán)格對角占優(yōu)，無法判斷迭代法是否收斂無法判斷迭代法是否收斂。需要通過譜。需要通過譜半徑判斷，先寫出半徑判斷，先寫出Jacobi迭代法的迭代矩陣：迭代法的迭代矩陣：1()JBDLU- -= = - -+ +1()DAD- -= = - -

42、 -1EDA- -= =- 由于無窮范數(shù)由于無窮范數(shù) |BJ |=31,還無法判斷迭代法是否收斂。還無法判斷迭代法是否收斂。 27213523121321xxxxxxx2022-2-5第六章 線性方程組的迭代解法43這時只能通過求迭代矩陣的譜半徑來判斷，由迭代矩陣這時只能通過求迭代矩陣的譜半徑來判斷，由迭代矩B 132712det()000JIB- - -= = - -= =解得特征值解得特征值12319190,2121= = = = - -譜半徑譜半徑 (BJ)1故故Jacobi迭代法收斂迭代法收斂.2022-2-5第六章 線性方程組的迭代

43、解法44 例例6.6 分別用分別用Jacobi迭代法和迭代法和Gauss-Seidel迭代法解下迭代法解下列方程組，問是否收斂？列方程組，問是否收斂？ 由于該矩陣非嚴(yán)格對角占優(yōu)，由于該矩陣非嚴(yán)格對角占優(yōu)，無法判斷無法判斷；但由于對稱，再；但由于對稱，再看是否正定?？词欠裾ā＝猓合禂?shù)矩陣為解：系數(shù)矩陣為 各階順序主子式各階順序主子式 |A1|=1, |A2|=3/4, |A3|=1/2, 說明矩陣對稱正定說明矩陣對稱正定所以所以Gauss-Seidel迭代法收斂迭代法收斂。但無法判斷。但無法判斷Jacobi迭代法是迭代法是否收斂，再利用迭代矩陣的范數(shù)或者譜半徑進(jìn)行判斷。否收斂，再利用迭代矩陣的

44、范數(shù)或者譜半徑進(jìn)行判斷。 111212121212121A 221211212152121321321321xxxxxxxxx2022-2-5第六章 線性方程組的迭代解法45由系數(shù)矩陣由系數(shù)矩陣寫出寫出Jacobi迭代矩陣迭代矩陣其其-范數(shù)范數(shù) |BJ |=1 和和 1-范數(shù)范數(shù)|BJ |1=1，不小于，不小于1，還無還無法判斷是否收斂法判斷是否收斂。再求其譜半徑進(jìn)行判斷。再求其譜半徑進(jìn)行判斷。由由 det(I-BJ)=0 求得特征值求得特征值1 = -1，2= 3=0.5 譜半徑譜半徑 (BJ)=|1| = 1，由此可知由此可知Jacobi迭代法發(fā)散。迭代法發(fā)散。 1112121212121

45、21A 000212121212121JB2022-2-5第六章 線性方程組的迭代解法46 例例6.7 取初值取初值 x(0)=(0，0，0)T 用用Jacobi迭代法解下列迭代法解下列方程組，如果要保證各分量的誤差的絕對值小于方程組，如果要保證各分量的誤差的絕對值小于10-6,問需問需要迭代多少次？要迭代多少次？ 解：由于方程組得系數(shù)矩陣嚴(yán)格對角占優(yōu)，所以解：由于方程組得系數(shù)矩陣嚴(yán)格對角占優(yōu)，所以Jacobi迭代法收斂。要確定迭代次數(shù)需要用到估計式迭代法收斂。要確定迭代次數(shù)需要用到估計式其中其中 BJ=E-D-1A ， FJ= D-1 b，范數(shù)用范數(shù)用-范數(shù)范數(shù) 。( )(0)*(2)1kkBxxFxB 30153212814322032132