數值分析第三章解線性方程組的迭代法

1、1第三章第三章 解線性方程組的迭代法解線性方程組的迭代法 Jacobi迭代法迭代法 Gauss-Seidel迭代法迭代法 迭代法的收斂條件迭代法的收斂條件(充要條件充要條件, 充分條件充分條件)bAx 求求 迭代法概述迭代法概述23.1 迭代法概述迭代法概述 gMxxbAx 等價線性方程組等價線性方程組取初始向量取初始向量 x(0) Rn, 構造如下構造如下單步定常線性單步定常線性迭代迭代公式公式), 2, 1, 0()()1( kgMxxkk以此來產生近似向量序列以此來產生近似向量序列 x(1), x(2), .當當k充分大時充分大時, .*)(xxk 基本思想基本思想等價變形等價變形如何做

2、如何做收斂性條件收斂性條件M: 迭代矩陣迭代矩陣30|lim)( xxkk0|lim)( AAkkxxkk )(limAAkk )(lim定義定義 對于對于Rn中的向量序列中的向量序列 x(k), 如果如果則稱則稱向量序列向量序列x(k)收斂于收斂于 Rn中的向量中的向量 x.定義定義對于對于n階方陣序列階方陣序列 A(k), 如果如果則稱則稱方陣序列方陣序列A(k)收斂于收斂于n階方陣階方陣A. 上面兩式通常表示成上面兩式通常表示成 向量序列與矩陣序列的收斂概念向量序列與矩陣序列的收斂概念4）（njxxjkjk,.,2 , 1,lim)( ),.,2 , 1,lim)(njiaaijkijk

3、 （定理定理 Rn中的向量序列中的向量序列x(k)收斂于收斂于Rn中的向中的向量量x的充分必要條件是的充分必要條件是其中其中xj(k)和和 xj分別表示分別表示 x(k)和和 x中的第中的第 j個分量個分量.定理定理 n階方陣序列階方陣序列A(k)收斂于收斂于n階方陣階方陣A的充的充分必要條件是分必要條件是 向量序列與矩陣序列收斂的充分必要條件向量序列與矩陣序列收斂的充分必要條件 向量序列和矩陣序列的收斂可歸結為對應分向量序列和矩陣序列的收斂可歸結為對應分量或對應元素序列的收斂性量或對應元素序列的收斂性.5 若由迭代公式若由迭代公式gMxxkk )()1(產生的向量序列產生的向量序列 x(k)

4、 收斂于向量收斂于向量 x, 則則gMxxgMxxkkkk )()1(limlim即向量即向量 x 是是 方程方程 Ax=b 的解的解. 單步定常線性迭代法產生的向量序列若收斂則單步定常線性迭代法產生的向量序列若收斂則必收斂到原線性方程組的解必收斂到原線性方程組的解.6 4444343242141343433323213124243232221211414313212111bxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxa n=4的的Jacobi迭代法迭代法把方程組改寫成如下等價形式把方程組改寫成如下等價形式 4434324214144334342321313322424

5、323121221141431321211/ )(/ )(/ )(/ )(axaxaxabxaxaxaxabxaxaxaxabxaxaxaxabxbAx gMxx 3.2 幾種基本的迭代法幾種基本的迭代法7 44)(343)(242)(1414)1(433)(434)(232)(1313)1(322)(424)(323)(1212)1(211)(414)(313)(2121)1(1/ )(/ )(/ )(/ )(axaxaxabxaxaxaxabxaxaxaxabxaxaxaxabxkkkkkkkkkkkkkkkk n=4的的Jacobi迭代法計算公式迭代法計算公式, 2 , 1 , 0 k已

6、知已知 用上述迭代公式可算得用上述迭代公式可算得 )0(4)0(3)0(2)0(1)0(xxxxx )(4)(3)(2)(1)(kkkkkxxxxx, 2 , 1 k8 n=4的的Jacobi迭代法迭代法矩陣表示矩陣表示 0 00 0444344424441333433323331222422232221111411131112 aaaaaaaaaaaaaaaaaaaaaaaaM )()1(gMxxkk 444333222111ababababg9 Jacobi迭代法迭代法,1)1(1)1(11ininiiiiiiiiiibxaxaxaxaxa ,1)1(1)1(11ininiiiiiiiii

7、ibxaxaxaxaxa ,1)1(1)1(11iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k)(k)(k+1), 2 , 1(ni Tknkkkxxxx)()(2)(1)(, 10 設設D為由為由A的對角線元素構成的對角矩陣的對角線元素構成的對角矩陣Jacobi迭代公式迭代公式bDxADIxbxADDxbAx11)()( bDxADIxkk1)(1)1()( Jacobi迭代法的矩陣表示迭代法的矩陣表示 迭代矩陣迭代矩陣ADIM1 11例例 用用Jacobi迭代法求解線性方程組迭代法求解線性方程組 4258321072210321321321xx

8、xxxxxxx解解 將方程組改寫成如下等價形式將方程組改寫成如下等價形式 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0213312321xxxxxxxxx12Jacobi迭代法計算公式為迭代法計算公式為 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx假設初始向量取假設初始向量取 x(0)=(0, 0, 0)T.第一次迭代第一次迭代Tx)4 . 8, 3 . 8, 2 . 7()1( 第二次迭代第二次迭代71.

9、92 . 74 . 82 . 03 . 81 . 0)2(1 x7 .103 . 84 . 82 . 02 . 71 . 0)2(2 x50.114 . 83 . 82 . 02 . 72 . 0)2(3 x13 實際計算時，迭代法中止條件實際計算時，迭代法中止條件 |max|max)()1(11kikiniinixxx其中其中 為給定的要求精度為給定的要求精度.14 n=4的的Gauss-Seidel迭代法迭代法把方程組改寫成如下等價形式把方程組改寫成如下等價形式 4434324214144334342321313322424323121221141431321211/ )(/ )(/ )(

10、/ )(axaxaxabxaxaxaxabxaxaxaxabxaxaxaxabxbAx )(k)(k)(k)(k)(k)(k)1( k)1( k)1( k)1( k)1( k)1( k)1( k)1( k)1( k)1( k1511)(414)(313)(2121)1(1/ )(axaxaxabxkkkk 22)(424)(323)1(1212)1(2/ )(axaxaxabxkkkk 33)(434)1(232)1(1313)1(3/ )(axaxaxabxkkkk 44)1(343)1(242)1(1414)1(4/ )(axaxaxabxkkkk n=4的的Gauss-Seidel迭代法

11、迭代法16 Gauss-Seidel迭代法迭代法,1)1(1)1(11ininiiiiiiiiiibxaxaxaxaxa ,1)1(1)1(11ininiiiiiiiiiibxaxaxaxaxa ,1)1(1)1(11iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k+1)(k+1)(k+1), 2 , 1(ni 17在迭代的每一步設定計算順序在迭代的每一步設定計算順序并且，在計算迭代值并且，在計算迭代值 充分利用它前面的新信息充分利用它前面的新信息這樣設計出來的迭代公式這樣設計出來的迭代公式稱為稱為高斯高斯塞德爾迭代公式塞德爾迭代公式.)1()1(2

12、)1(1 knkkxxx)1( kix)1(1)1(2)1(1, kikkxxxni, 2 , 1 ,11)(11)1()1( nijkjijijkjijiiikixaxabax Gauss-Seidel迭代法迭代法18 Gauss-Seidel迭代法的矩陣表示迭代法的矩陣表示 設將系數矩陣設將系數矩陣A 分裂為分裂為,UDLA 其中其中D為對角陣為對角陣, L 和和U分別為嚴格下三角和嚴格上三分別為嚴格下三角和嚴格上三角陣角陣.bLDUxLDxkk1)(1)1()()( gMxbLDUxLDxbUxxLD b U)xDL(Ax 11)()()(U LDM1)( 迭代矩陣迭代矩陣GaussSe

13、idel迭代公式迭代公式19例例 用用Gauss-Seidel迭代法求解線性方程組迭代法求解線性方程組 4258321072210321321321xxxxxxxxx解解 將方程組改寫成如下等價形式將方程組改寫成如下等價形式 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0213312321xxxxxxxxx20Gauss-Seidel迭代法計算公式為迭代法計算公式為 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxx

14、xxx假設初始向量取假設初始向量取 x(0)=(0, 0, 0)T.第一次迭代第一次迭代2 . 7)1(1 x02. 93 . 82 . 71 . 0)1(2 x644.114 . 802. 92 . 02 . 72 . 0)2(3 x21第二次迭代第二次迭代4308.102 . 7644.112 . 002. 91 . 0)2(1 x6719.113 . 8644.112 . 04308.101 . 0)2(2 x8205.124 . 86719.112 . 04308.102 . 0)2(3 xGauss-Seidel迭代法計算公式為迭代法計算公式為 4 . 82 . 02 . 03 .

15、82 . 01 . 02 . 72 . 01 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx假設初始向量取假設初始向量取 x(0)=(0, 0, 0)T.22 Jacobi迭代法：迭代法： )1()1(2)1(1)(knkkkxxxx已知已知x(k+1)分量的計算可以分量的計算可以同同時時進行進行, 無先后次序無先后次序 Gauss-Seidel迭代法：迭代法：)1()1()1(2)1(1)( kxknkkkxxxx已知已知x(k+1)分量的計算有分量的計算有先后次序先后次序, 必須先計算必須先計算x(k+1)前前面的分量然后再計算

16、下一分量面的分量然后再計算下一分量.23 Jacobi迭代法與迭代法與Gauss-Seidel迭代法的計算效果迭代法的計算效果哪一種更好哪一種更好? 前例計算結果表明前例計算結果表明, 用用Gauss-Seidel迭代法比用迭代法比用Jacobi迭代法效果好迭代法效果好. 但對一般情形但對一般情形, 有些問題有些問題Gauss-Seidel迭代法確迭代法確實比實比Jacobi迭代法收斂得快迭代法收斂得快, 但也有但也有Gauss-Seidel迭迭代法比代法比Jacobi迭代法收斂得慢迭代法收斂得慢, 甚至還有甚至還有Jacobi迭迭代法收斂代法收斂, 但但Gauss-Seidel迭代法發(fā)散的情

17、形迭代法發(fā)散的情形.243.3 迭代法的收斂條件迭代法的收斂條件|max)(1iniA 定義定義(譜半徑譜半徑) 設設n階方陣階方陣A的特征值為的特征值為 i (i=1,2,n), 則稱則稱為矩陣為矩陣A的的譜半徑譜半徑. Ak 的特征值為的特征值為knkk ,21故故 kkinikinikAA)(|max|max)(11 25|)(AA iiiuAu 矩陣范數和譜半徑有如下關系矩陣范數和譜半徑有如下關系設設A的任一特征值為的任一特征值為 i , 對應的特征向量為對應的特征向量為ui , 則則|iiiiiiuAAuuu |Ai 由由 的任意性可知結論成立的任意性可知結論成立. 矩陣矩陣A的譜半

18、徑不超過它的任何一種由向量范數的譜半徑不超過它的任何一種由向量范數誘導出的范數，即誘導出的范數，即|A|是是A的特征值的上界的特征值的上界.證證故故從而從而26)()(|)1max2AAAAATT )(|)22AAA 為為對對稱稱矩矩陣陣，則則若若 設設A為為n階方陣階方陣, 則則 由于由于2-范數具有上面的關系式范數具有上面的關系式, 所以稱所以稱 |A|2 為為譜范數譜范數.27,.,.,2kAAAI0lim kkA1)( A 定理定理 設設A是任意是任意n階方陣階方陣, 由由A的各次冪所組成的的各次冪所組成的矩陣序列矩陣序列收斂于零矩陣收斂于零矩陣, 即即的充分必要條件是的充分必要條件是

19、28定理定理 對任何初始向量對任何初始向量 x(0)和右端項和右端項g, 由迭代公式由迭代公式 x(k+1) =Mx(k)+g (k=0, 1, 2, )產生的向量序列產生的向量序列x(k)收斂的充分必要條件是收斂的充分必要條件是 (M)1其中其中 (M)是是迭代迭代矩陣矩陣M的譜半徑的譜半徑. 迭代法收斂的充分必要條件迭代法收斂的充分必要條件 迭代法的收斂性只與迭代法的收斂性只與迭代矩陣的譜半徑迭代矩陣的譜半徑有關有關, 而而迭代矩陣是由迭代矩陣是由A演變來的演變來的, 因此迭代法是否收斂只與因此迭代法是否收斂只與系數矩陣系數矩陣A以及演變的方式有關以及演變的方式有關, 與常數項和初始向與常

20、數項和初始向量的選擇無關量的選擇無關.29證明證明 必要性必要性. 設序列設序列x(k)收斂于收斂于 x*, 則有則有 迭代法收斂的充分必要條件迭代法收斂的充分必要條件 )0()()1(,xgMxxkk任意任意收斂收斂. 1)( M *)0()2(2)1()1()(xxMxxMxxMgMxgMxxxkkkkk 故故gMxx *0lim, 0*)(lim)( kkkkMxx必必須須由于由于x(0)為任意為任意n維向量維向量,即即. 1)( M 30 迭代法收斂的充分必要條件迭代法收斂的充分必要條件 )0()()1(,xgMxxkk任意任意收斂收斂. 1)( M 充分性充分性. 若若 (M)1,

21、則則 =1不是不是M的特征值的特征值, 故故0)det( MI方程方程 (IM)x=g有唯一解有唯一解, 記為記為x*, 即即gMxx *又又 *)0()(xxMxxkk 且且0lim kkM. 0*)(lim*)(lim)0()( xxMxxkkkk故對任意初始向量故對任意初始向量x(0), 均有均有證明證明31推論推論1 若迭代矩陣若迭代矩陣M滿足滿足|M|1, 則下列迭代公則下列迭代公式對任意初始向量式對任意初始向量x(0)收斂收斂 gMxxkk )()1(32例例 解方程組解方程組 3222122321321321xxxxxxxxx討論討論Jacobi迭代法與迭代法與Gauss-Sei

22、del迭代法的收斂性迭代法的收斂性.解解迭代法是否收斂等價于迭代矩陣的譜半徑是否小迭代法是否收斂等價于迭代矩陣的譜半徑是否小于于1，故先求迭代矩陣，故先求迭代矩陣33 Jacobi迭代法的迭代矩陣為迭代法的迭代矩陣為 0221012201ADIB其特征方程為其特征方程為 221122| BI03 特征值特征值, 0321 譜半徑譜半徑10)( M 故故Jacobi迭代法迭代法收斂收斂.34 Gauss-Seidel迭代法的迭代矩陣為迭代法的迭代矩陣為ULDM1)( ,122011001)( LD,120011001)(1 LD 000100220120011001)(1ULDM,2003202

23、20 35其特征方程為其特征方程為20032022| MI0)2(2 特征值特征值, 2, 0321 譜半徑譜半徑12)( M 故故Gauss-Seidel迭代法迭代法發(fā)散發(fā)散.36 一般來說一般來說, 計算矩陣的譜半徑比較困難計算矩陣的譜半徑比較困難, 故用迭故用迭代法收斂的充分必要條件來判斷迭代法是否收斂往代法收斂的充分必要條件來判斷迭代法是否收斂往往不太容易往不太容易, 以下介紹用其他方法判別迭代法收斂以下介紹用其他方法判別迭代法收斂的的充分條件充分條件.37定義定義(嚴格對角占優(yōu)陣嚴格對角占優(yōu)陣) 稱稱n 階方陣階方陣 是是嚴格對角占優(yōu)嚴格對角占優(yōu)的，如果其主對角線元素的絕對值大的，如

24、果其主對角線元素的絕對值大于同行其它元素絕對值之和：于同行其它元素絕對值之和：nijaA)( ni, 2 , 1 |, 1iinijjijaa 若線性方程組的系數矩陣為嚴格對角占優(yōu)陣，則稱若線性方程組的系數矩陣為嚴格對角占優(yōu)陣，則稱這個線性方程組為這個線性方程組為嚴格對角占優(yōu)方程組嚴格對角占優(yōu)方程組. 932331261521013218A 93233126152613218B 38 迭代法收斂的充分條件迭代法收斂的充分條件定理定理 若若A為為嚴格對角占優(yōu)陣嚴格對角占優(yōu)陣, 則求解則求解Ax=b 的的Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收斂迭代法均收斂.定理定理 若若A

25、為為對稱正定陣對稱正定陣, 則則求解求解Ax=b的的Gauss-Seidel迭代法收斂迭代法收斂.39例例 方程組方程組Ax=b的系數矩陣為的系數矩陣為 51121012110A嚴格對角占優(yōu)陣嚴格對角占優(yōu)陣.故故Jacobi迭代法與迭代法與Gauss-Sidel迭代法均收斂迭代法均收斂.40例例 方程組方程組Ax=b的系數矩陣為的系數矩陣為 49103A非對角占優(yōu)陣非對角占優(yōu)陣交換交換兩個方程的次序，得原方程組的同解方程組兩個方程的次序，得原方程組的同解方程組 122110349bbxx 它是一個嚴格對角占優(yōu)方程組，對此方程組它是一個嚴格對角占優(yōu)方程組，對此方程組Jacobi迭代法和迭代法和G

26、auss-Seidel迭代法均收斂迭代法均收斂. 當所給的方程組不滿足迭代法的收斂條件時當所給的方程組不滿足迭代法的收斂條件時, 適適當調整方程組中方程的次序當調整方程組中方程的次序, 有時可得到滿足迭代法有時可得到滿足迭代法收斂條件的同解方程組收斂條件的同解方程組.41例例 方程組方程組Ax=b的系數矩陣為的系數矩陣為 210121012A但但A為對稱正定矩陣為對稱正定矩陣, Gauss-Seidel迭代迭代法收斂法收斂.要判別要判別Jacobi迭代法是否收斂迭代法是否收斂, 需要計算其迭代需要計算其迭代矩陣的譜半徑矩陣的譜半徑. 非嚴格對角占優(yōu)非嚴格對角占優(yōu)42例例 設有方程組設有方程組Ax=b, 其中其中 121212112121211A討論用兩種迭代法求解的收斂性討論用兩種迭代法