1、數值計算方法數值計算方法【第二版】電子教案【第二版】電子教案科學出版社科學出版社2121世紀高等院校教材電子教案系列世紀高等院校教材電子教案系列南京大學數學系南京大學數學系 林成森教授林成森教授授課教材授課教材數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森3 迭代法適用于求解大型稀疏的線性方程組，其迭代法適用于求解大型稀疏的線性方程組，其基本思想是通過構造迭代格式產生迭代序列，由迭代基本思想是通過構造迭代格式產生迭代序列，由迭代序列來逼近原方程組的解，因此，要解決的基本問題序列來逼近原方程組的解，因此，要解決的基本問題是：是：1. 如何構造迭代格式如

2、何構造迭代格式 2.迭代序列是否收斂迭代序列是否收斂第六章第六章 解線性方程組的迭代法解線性方程組的迭代法數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森4一、基本迭代法的格式及收斂性一、基本迭代法的格式及收斂性設有線性代數方程組設有線性代數方程組A=M+N M的逆好求。的逆好求。Ax =b (M+N)x=b Mx=-Nx+b x=-M-1Nx+M-1b 用矩陣表示：用矩陣表示： Ax =b A 為系數矩陣，非奇異且設為系數矩陣，非奇異且設aii0；b為右端，為右端，x為解向量為解向量11,AxbxBxgBMN gM b nnnn2n21n12n2n2

3、221211n1n212111bxa. .xaxa. bxa.xaxabxa.xaxa數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森5 1(11)(),(0,1,2,)nkknxBAxbxBxxgBMN gMbkBRgng 基基其其中中稱稱為為迭迭代代矩矩本本迭迭代代法法的的陣陣， 是是已已知知迭迭格格式式的的代代維維向向量量，(0)(1)( )( ),kkkxxBxgx 給給定定由由迭迭代代格格式式即即可可產產生生迭迭代代序序列列。( )(1)( )limkkkkxxxBxgxBxgAxb 當當對對取取極極限限得得注：分解注：分解A是一個重要問題是

4、一個重要問題數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森620,3336,AxbAbAAMNMN例例：解解：8-328-32對對線線性性方方程程組組，其其中中 = 411-1= 411-1631263128000-328000-32將將 分分解解為為, ,其其中中= 0110= 40-1= 0110= 40-100126300012630231312()20323343663AxbxMNxM bMbNxxxxxxx -1-1-1-1-1-11 100008 81 1000011111 100001212231312(2032)/8(334)/11(

5、3663)/12xxxxxxxxx 1 12 23 3數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森7( )( )23( )( )13( )( )12(2032)/8(33 4)/11(36 63)/120,1,2,.kkkkkkxxxxxxxxxk ( (k k+ +1 1) )1 1( (k k+ +1 1) )2 2( (k k+ +1 1) )3 3迭迭代代格格式式的的分分量量形形式式為為(3.000032,1.999838,0.9998813)(3,2,1)TTxx (10)(10)迭迭代代到到第第1010次次, ,得得到到已已知知精精確確

6、解解為為數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森8(1)( ),kkxBxgBg 迭迭代代格格式式322032200-0-88888841334133迭迭代代矩矩陣陣 = -0= -011111111111163366336-0-0121212121212數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森9(1)( )( )(0)( )kkkkxBxgxxxx k k基基本本迭迭代代法法產產生生的的迭迭代代序序列列，如如果果對對任任取取初初始始向向量量都都有有l li im m，則則稱稱此此迭迭代代法法是

7、是收收斂斂的的，否否則則是是定定義義發發散散的的。( )( )( )( )1212( )( )(,) ,(,),limlim,(1,2, )kkkkTnTnnkkiikkxxxxxxxxRxxxxin 對對則則在在R Rn n中，點列的收斂等價于每個分量的收斂。即中，點列的收斂等價于每個分量的收斂。即 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森10 ( )( )( )( )( )(),(),limlim,( ,1,2, )kkkijijkkijijkkAAaAaAAaai jn同同理理，的的收收斂斂與與所所選選擇擇的的范范數數無無關關。若若則則l

8、im0kkB 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森11( )(1)( )( )(1)(1)(0)(0)(0)()kkkkkkkxAxbxBxgxBxgxxB xxBBxx 是是精精確確解解迭迭代代格格式式為為誤誤差差向向量量其其中中是是初初始始誤誤差差向向量量，是是一一個個確確定定的的值值收斂性分析收斂性分析 (0)( )0()kkxxBk 由由此此，得得到到結結論論: :對對任任意意初初值值，迭迭代代序序列列收收斂斂數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森12121rJordanPJJP

9、BPJJ 由由矩矩陣陣的的標標準準型型知知存存在在非非奇奇異異陣陣 使使(1)( )(0)()( )1.kkxBxgxB 迭迭代代法法收收斂斂的的充充要要條條件件迭迭代代格格式式對對任任意意初初始始向向量量都都收收斂斂的的充充分分必必要要條條件件是是定定理理1 1( )(0):0().0()( )1.kkkkBBkBkB 由由知知迭迭代代法法收收斂斂以以下下證證明明的的充充分分必必要要條條件件是是證證明明數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森13(),11(1,2, )1iiiiiiiinnJJir 為為若若當當塊塊 且且1111111,ri

10、ikknnBPJPJP BPJP BPP BPP BPP B P 于于是是數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森141200(1,2, )( )( )max(,),01,(1,2, )kkirkiiJJirBJJir 為為此此 只只需需證證明明112,(1,2,)kkkkkrJJP B PJkJ 1,00kkkkBP JPkBJ 故故顯顯 然然當當時時數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森152222121102101 ,02,0000(1)2000kkkkkkkJJk kkJk 例例: :

11、數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森161(1)112(2)1111()!(1)(1),!()!iiiiiinknkkikikinknkkikikikikkikinnjkccccJckk kkjCjkjj 其中其中數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森1701 ()0 ()1 (1,2, )0 ()()1jkjkkiikCkJkirBkB 由由極極限限運運算算知知：所所以以即即此此結結論論數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森1821,2

12、det()60,6,( )2.4491.1.IBB 由得由得由定理 迭代格式不收斂由定理 迭代格式不收斂12122535xxxx 用用迭迭代代法法求求程程組組例例：解解方方(1)( )(1)( )12(1)( )21:,52(1,2,)35025,305kkkkkkxBxgxxkxxBg 構造迭代格構造迭代格解解式式，迭代矩陣迭代矩陣數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森19,.,(1,2,)( )n nppARpAA （特特征征值值上上界界定定理理）設設對對于于有有引引理理:,.pppppAUAUUUUAUAUAA 設設 是是 的的任任一一

13、特特征征值值為為相相應應的的特特征征向向量量則則有有因因 是是證證的的任任一一特特征征值值 故故定定理理得得證證明明數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森20( )(1)()12,.kkxBxgBB 迭迭代代法法收收斂斂的的充充分分條條件件如如果果迭迭代代格格式式的的迭迭代代矩矩陣陣 的的某某一一種種范范數數則則此此迭迭定定代代格格式式收收斂斂理理數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森21( )(1)( )( )(1)( )(1)(0)1,.113kkkkkkkxBxgBBBxxxxBBxx

14、xxB 如如果果迭迭代代格格式式的的迭迭代代矩矩陣陣 滿滿足足則則有有如如下下的的誤誤差差估估計計式式定定理理( )(1)( )(1)(1)( )( ):()()()kkkkkkkxBxgxBxgxxB xxB xxB xx 由由和和證證明明有有數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森22()(1)()()()()(1)1kkkkkkkxxBxxBxxBxxxxB 從從而而( )(1)(1)(2)( )(1)(1)(2)()kkkkkkkkxBxgxBxgxxB xx又又因因為為，數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南

15、京大學林成森南京大學林成森23:(1),.(2)1,.BB注注越越小小 收收斂斂越越快快接接近近 時時 收收斂斂慢慢( )(1)(1)(2)1(1)(2)(1)(0)()()()kkkkkkkxxB xxBxxBxx ( )( )(1)(1)(0)11kkkkBBxxxxxxBB 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森24( )(1)( )( )(1)( )(1)|1,2,.,|(|ma |1)x|kkpkkkkkiiixxpxxpxxxx 絕絕對對誤誤差差標標準準。給給出出容容許許誤誤差差界界當當時時，終終止止迭迭代代，解解取取為為常常取取

16、( )(1)( )|(2)kkkxxx 相相對對誤誤差差標標準準。給給出出容容許許誤誤差差界界迭迭代代終終止止標標準準數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森25( )(1)(0)1kkBxxxxB 由誤差估計式估計迭代次數由誤差估計式估計迭代次數( )(1)(0)(1)(0)1ln1()lnkkBxxkBxxxxBB 估估計計迭迭代代次次數數maxmax(3)kkk 給給出出最最大大迭迭代代次次數數當當迭迭代代終終止止，給給出出失失敗敗信信息息。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森26(

17、)(0)( )(0)(0)( )(0)| | | ( ( ) |( ( )01|.( ( ).kkkkkkkkBBBBB 由由說說明明表表示示迭迭代代誤誤差差的的縮縮減減因因子子，若若希希望望實實際際的的縮縮減減因因子子為為（），即即則則可可令令漸漸近近收收斂斂速速度度數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森276106ln10ln(ln( )ln( ( )kBkB 由由此此，可可估估計計出出所所需需的的迭迭代代次次數數相相當當于于相相對對誤誤差差限限，如如取取，則則有有ln( ( )RB 為為迭迭代代格格式式的的漸漸定定義義近近收收斂斂速速度

18、度。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森28(1)( )( )323121(),(0,1,.)kkkAbxxAxbkAxb 已已知知，, ,用用迭迭代代公公式式求求解解。問問 取取什什么么實實數數可可使使迭迭代代收收斂斂，且且 為為何何值值時時，例例：收收斂斂最最快快。23254(1)(4)12IA BIA (1)(1)迭迭代代矩矩陣陣解解：數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森291,14 ,BIA 1212迭迭代代矩矩陣陣的的特特征征值值為為1111120,114111410,2 1,

19、4,A1212的的特特征征值值為為數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森302114(1)1452,525 當當時時，收收斂斂最最快快。14 14 1 1 12 25 102 當當時時，迭迭代代格格式式收收斂斂。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森31()()xBxgIB xgIB 實際計算中，存在舍入誤差實際計算中，存在舍入誤差當呈病態時，迭代當呈病態時，迭代舍入誤差分析舍入誤差分析解會失真。解會失真。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林

20、成森32二、幾種實用的基本迭代法二、幾種實用的基本迭代法l1、Jacobi迭代法迭代法l2、Gauss-Seidel迭代法迭代法l3、超松弛迭代法（、超松弛迭代法（SOR)l4、對稱超松弛迭代法（、對稱超松弛迭代法（SSOR)l5、塊超松弛迭代法（、塊超松弛迭代法（BSOR法）法）數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森331 1、Jacobi Jacobi 迭代迭代12121211,12,112nnnnnnnnnaaADaaaUaLaaaa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森344221

21、42114400000022040 ,100 ,002004110000ADLUDLU 例：例：數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森351111()(),JJAxbxDLU xD bB xgBDLUgD b于是于是其中其中11()()()AxbDLU xbDxLU xbxDLU xD b數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森36(1)( )kkJJacoxxgiBb 迭迭代代的的矩矩陣陣格格式式Jacobi迭代矩陣迭代矩陣數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大

22、學林成森南京大學林成森37推導其分量形式推導其分量形式1111221331122221123322112211nnnnnnnnnnnnna xa xa xa xba xa xa xa xba xa xa xaxb ()()AxbDLU xbDxLU xb由由得得數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森38第第i個方程除以個方程除以aii( (i = =1,2,1,2,n),n),得得1311211231111111123221221322222222121121nnnnnnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaa

23、aaaabxxxxaaaa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森391311211231111111123221221322222222121121nnnnnnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森40JacobiJacobi迭代的分量形式迭代的分量形式(1)( )( )( )13112121311111111(1)( )( )( )23221213222222222(1)( )( )( )

24、121121kkkknnkkkknnkkkknnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森411121111111()12221()()2222222()1200,0nknkkJknnnnnnnnnnaabaaaxabaxaaaBxgxbaaaaa 令令：，則則 x x( (k k+1)+1)= =B BJ Jx x( (k k) )+g+g ，這里這里 B BJ J=D=D-1-1(L+U) , g=D(L+U) , g=D-1-1b b 數值計

25、算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森42(1)()1()/,1,2,nkkiiijjiijj ixba xain (1)( )kkJJacoxxgiBb 迭迭代代的的矩矩陣陣格格式式Jacobi迭代公式（分量形式）迭代公式（分量形式） 給出初始向量給出初始向量 x(0), 即可得到向量序列：即可得到向量序列： x(1),x(2),x(k),若若 x(k) x*, 則則x*是解。是解。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森43例例1：設方程組為：設方程組為 31032202412253213213

26、21xxxxxxxxx解：解：Jacobi迭代格式為迭代格式為試寫出其試寫出其Jacobi分量迭代格式以及相應的迭代矩陣，并求解。分量迭代格式以及相應的迭代矩陣，并求解。10310351)323(10152141)220(415125152)212(51)(2)(1)(2)(1)1(3)(3)(1)(3)(1)1(2)(3)(2)(3)(2)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森44故故Jacobi迭代矩陣為迭代矩陣為 2105511042310510JB取取 x(0)=(0,

27、0,0)t, e=10-3,終止準則：終止準則：x(k)-x(k-1)ex(14)=-3.99972.99981.9998數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森45例例2：設方程組為設方程組為 1231231235212422023103xxxxxxxxx 解：解： Gauss-Seidel迭代格式為迭代格式為試寫出試寫出Gauss-Seidel迭代格式迭代格式.(1)( )( )( )( )12323(1)(1)( )(1)( )21313(1)(1)(1)(1)(1)3121212112( 12 2)5555111(202)5442331

28、1(3 23)1051010kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx 2、Gauss-Seidel迭代法迭代法數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森46(1)( )( )( )13112121311111111(1)(1)( )( )23221213222222222(1)(1)(1)(1)121121kkkknnkkkknnkkkknnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa Gauss-Seidel迭代的迭代的分量形式分量形式1(1)(1)( )11()/,1,

29、2,inkkkiiijjijjiijj ixba xa xain 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森47(1)( )( )13121213111111(1)(1)( )23212132222222(1)(1)(1)31323312333333kkkkkkkkkaabxxxaaaaabxxxaaaaabxxxaaa 由由(1)( )( )11 11221331(1)(1)( )22221 12332(1)(1)(1)33331 13223kkkkkkkkka xa xa xba xa xa xba xa xa xb 得得(1)(1)( )k

30、kkDxbLxUx213132121323000000000000LaaaaaUa 推導推導Gauss-Seidel迭代法的迭代法的矩陣形式矩陣形式數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森48(1)( )( )( )13112121311111111(1)(1)( )( )23221213222222222(1)(1)(1)(1)121121kkkknnkkkknnkkkknnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa 由由數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京

31、大學林成森南京大學林成森49(1)( )( )( )11112213311(1)(1)( )( )22221123322(1)(1)(1)(1)112211kkkknnkkkknnkkkknnnnnnnnna xa xa xa xba xa xa xa xba xa xa xaxb 得得(1)(1)( )kkkDxbLxUx數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森50()AxbDL xbUx(1)(1)( )(1)( )(1)1( )1()()()kkkkkkkDxbLxUxDL xbUxxDLUxDLb (1)( )kkGxB xg G Ga

32、 au us ss s- -S Se ei id de el l迭迭代代的的矩矩陣陣格格式式Gauss-Seidel迭代矩陣迭代矩陣11(),()GBDLUgDLb其其中中數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森511(1)(1)( )11()/,1,2,inkkkiiijjijjiijj ixba xa xain (1)( )11(),()kkGGxB xgBDLUgDLg G Ga au us ss s- -S Se ei id de el l迭迭代代中中的的矩矩陣陣格格式式其其Gauss-Seidel迭代公式迭代公式給出初始向量給出初始向

33、量 x(0), 即可得到向量序列：即可得到向量序列： x(1),x(2),x(k),若若 x(k) x*, 則則x*是解。是解。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森52maxmax,:( )0,(1,2, )1,1:0A bKx iinkGaussSeidelxbKERA 給給出出和和允允許許誤誤差差界界表表示示最最大大迭迭代代次次數數計計算算步步驟驟如如下下置置對對循循環環執執行行到到第第步步置置算算法法迭迭代代法法求求解解( )(1)( )( , , ),( , , ),kkkJacobik i jxxk i jx 程程序序實實現現：G

34、 Ga au us s迭迭代代法法：三三套套循循環環，兩兩套套數數組組s s- -s se ei id d迭迭代代法法：三三套套循循環環，一一套套數數組組e el l數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森531, 2,( )0( )( ,),(1, 2,;)( )( ( ) /( , )( ),inSAx isumsumsumxja ijjnjix ib isuma i iPRx iSAPRERERPRERx ER k 對對循循 環環 執執 行行 到到 第第 步步 如如 果果則則 如如 果果停停 機機 。 輸輸 出出 結結 果果數值計算方法【

35、第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森54123123123111112024343211111045435111115355333xxxxxxxxx 用用G Ga au us ss s- -s se ei id de el l迭迭代代法法求求解解線線性性方方程程組組（）（）（）例例：Ab.ma(1,1)=1/2+1/4+1/3;a(1,2)=-1/4;a(1,3)=-1/3;a(2,1)=a(1,2);a(2,2)=1/4+1/3+1/5;a(2,3)=-1/5;a(3,1)=a(1,3);a(3,2)=a(2,3);a(3,3)=1/3+1/5+1/3

36、;b(1)=20/2;b(2)=0;b(3)=5/3;數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森55function x,k=gs(A,b)n n=size(A);x=zeros(1,n);for k=1:1000 error=0; for i=1:n s=0;xb=x(i); for j=1:n if i=j,s=s+A(i,j)*x(j);end end x(i)=(b(i)-s)/A(i,i); error=error+abs(x(i)-xb); end if error/n0.0001,break;endendfprintf(k.no.=

37、%3.0f,error=%7.2en,k,error)數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森56()1,| 1()1| 1JJGGBJacobiBBB 收收斂斂G Ga au us ss s- -S Se ei i一一d d般般收收斂斂原原則則e el l收收斂斂收收斂斂準準則則數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森57234AADAJacobi 對對稱稱正正定定G Ga au us ss s- -S Se ei id de el l迭迭代代法法收收斂斂若若是是 對對稱稱正正定定的的準準則則

38、 ：準準則則，則則是是 對對稱稱正正定定迭迭：代代法法收收斂斂,|11,2JAAJacobiBJacobi 由由 來來直直接接判判斷斷（充充分分準準則則）嚴嚴格格對對角角占占優優迭迭代代法法 G Ga au us ss s- -S Se ei id de el l迭迭代代法法收收斂斂迭迭代代法法 G Ga au us ss s- -S Se e實實用用準準則則：準準則則 ：準準i id de el l迭迭則則 ：代代法法收收斂斂. .數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森58111,()max1.niiijjjinijJJinjiijiAaa

39、aBBaJacobi 嚴嚴 格格 對對 角角 占占 優優 即即由由所所 以以迭迭 代代 法法 收收 斂斂1AJacobi證證明明準準則則 ： 嚴嚴格格對對角角占占優優迭迭代代法法收收斂斂Gauss-SeidelGauss-Seidel迭迭代代法法收收斂斂1,0,:JJijijiiBID ABijabJacobijai 且且 的的元元素素為為證證明明 迭迭代代法法數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森59111det()det()0,1det()0det()0DLDLUAADLDLU 上上式式可可改改寫寫為為已已知知 嚴嚴格格對對角角占占優優的

40、的對對角角元元非非零零故故，只只有有1().GGaussSeidelBDLUGaussSeidel 迭迭代代法法的的迭迭代代矩矩陣陣為為迭迭代代法法11,()0,det()det()0,GGGGBB xxIBxIBIDLU 設設有有特特征征值值由由方方程程組組有有非非零零解解 于于是是有有反反證證1(),ADLU 由 嚴格對角占優可推出也嚴格對角占優由 嚴格對角占優可推出也嚴格對角占優數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森601()ADLU 由由 嚴嚴格格對對角角占占優優可可推推出出也也嚴嚴格格對對角角占占優優1,det()0,1,()1,.

41、GGDLUBBGS 是非奇異陣 應有，與所設矛盾是非奇異陣 應有，與所設矛盾故的特征值即收斂故的特征值即收斂數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森61522152115225121()15115A DLUDLU = =嚴嚴格格對對角角占占優優當當時時，也也嚴嚴例例：格格對對角角占占優優數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森62,2,1.2.3.JacobiGaussSeidelAGaussSeidelDAJacobi 對對一一個個任任意意給給定定的的系系數數矩矩陣陣迭迭代代法法和和迭迭代代法

42、法可可能能同同時時收收斂斂，或或同同時時不不收收斂斂，或或者者一一個個收收斂斂而而另另一一個個不不收收斂斂。在在都都收收斂斂的的情情況況下下，其其收收斂斂的的速速度度也也不不一一定定是是哪哪一一種種一一定定快快。對對稱稱正正定定一一定定收收斂斂 但但不不一一注注：定定也也是是對對稱稱正正定定 所所以以法法未未必必收收斂斂。例例如如數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森63|A|=12+4-15=1, |2D-A|=12-4-15=-7121121261,2261112112ADA 正正定定不不正正定定數值計算方法【第二版】電子教案數值計算方法

43、【第二版】電子教案 南京大學林成森南京大學林成森64例例: :討論用討論用Gauss-SeidelGauss-Seidel迭代法求解方程組迭代法求解方程組Ax=bAx=b時的收時的收斂性，已知斂性，已知312041102A 解解:(1)對對A：不是嚴格對角占優的矩陣，無法用充分：不是嚴格對角占優的矩陣，無法用充分準則準則I， (2)考慮充分準則考慮充分準則II，計算，計算Jacobi迭代矩陣迭代矩陣BJ=D-1（L+U）=I-D-1A數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森65300001240000012100100DLU ，12033100

44、,141002JJ 可可求求出出不滿足充分準則不滿足充分準則II II，故無法判斷。，故無法判斷。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森66先求出先求出Gauss-SeidelGauss-Seidel迭代矩陣迭代矩陣 B BG G=(D-L)=(D-L)-1 -1U U(3)(3)考慮用定理考慮用定理2 2的充分條件的充分條件12033100411063G 1G 154G不滿足定理不滿足定理2 2的充分條件，故無法判斷。的充分條件，故無法判斷。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森67，故收

45、斂，故收斂易知易知）（，得到得到，1)(2212100)241)31()-det(max321G Gi(4)(4)再用定理再用定理1 1的充要條件的充要條件12033100411063G 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森68例例: :討論用討論用JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法求解迭代法求解方程組方程組Ax=b時的收斂性，如果收斂，并比較哪種方法時的收斂性，如果收斂，并比較哪種方法收斂較快，其中收斂較快，其中302021212A 數值計算方法【第二版】電子教案數值計算方法【第

46、二版】電子教案 南京大學林成森南京大學林成森69解解: (1)對對Jacobi方法，迭代矩陣方法，迭代矩陣200310021102JB 11112J （），故故方方法法收收斂斂。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森70(2)對對Gauss-SeidelGauss-Seidel方法，迭代矩陣方法，迭代矩陣120031011000211100220031002110012GB 11112G （），故故方方法法收收斂斂。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森711111(3)1212GJ（）（）

47、Gauss-SeidelGauss-Seidel方法比方法比Jacobi方法收斂快。方法收斂快。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森723、超松弛迭代法（、超松弛迭代法（SOR法）法）(1)( )( )( )13112121311111111(1)(1)( )( )23221213222222222(1)(1)(1)(1)121121kkkknnkkkknnkkkknnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa (1)(1)kx 用用G Ga au us ss s- -s se ei

48、id de el l迭迭代代法法計計算算數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森73(1)(1)( )(2)(1),1,2,.,kkkiiixxxin 引引入入松松弛弛因因子子 ，數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森74以三階方程為例，推導超松弛迭代法（以三階方程為例，推導超松弛迭代法（SORSOR法）的分量形式法）的分量形式(1)( )( )13121213111111(1)(1)( )23212132222222(1)(1)(1)31323312333333kkkkkkkkkaabxxx

49、aaaaabxxxaaaaabxxxaaa (1)(1)kx 用用G Ga au us ss s- -s se ei id de el l迭迭代代法法計計算算數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森75(1)(1)( )(1),1,2,3(2)kkkiiixxxi 引引入入松松弛弛因因子子 ，(1)( )( )( )1312111211311111111(1)(1)( )( )2321222132222222222(1)(1)(1)( )3132333312333333333()(1)()(1)()(1)kkkkkkkkkkkkaabaxxxx

50、aaaaaabaxxxxaaaaaabaxxxxaaaa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森76(1)( )( )( )1312111211311111111(1)(1)( )( )2321222132222222222(1)(1)(1)( )3132333312333333333() (1)() (1)() (1)kkkkkkkkkkkkaabaxxxxaaaaaabaxxxxaaaaaabaxxxxaaaa (1)( )( )( )( )11111122131311(1)( )(1)( )( )22211222233222(1)( )

51、(1)(1)( )33331132233333()()()kkkkkkkkkkkkkkkxxba xa xa xaxxba xa xa xaxxba xa xa xa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森77(1)( )( )( )( )1311211121131111111111(1)(1)( )( )( )2322122213222222222222(1)(1)(1)121121() (1)() (1)(kkkkknnkkkkknnkkknnnnnnnnnnnnaaabaxxxxxaaaaaaaabaxxxxxaaaaaaaaxxxxa

52、aa (1)( ) (1)kknnnnnnnnbaxaa (1)( )( )( )111111111(1)( )(1)( )( )222112222222(1)( )(1)(1)( )1111()()()kkkknnkkkkknnkkkkknnnnnnnnnnnnxxba xa xaxxba xa xa xaxxba xaxa xa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森781(1)( )(1)( )11,2,inkkkkiiiijjijjjj iiixxba xa xain （）SOR迭代公式（分量形式）迭代公式（分量形式）1,1,1,Ga

53、ussseidel 為為迭迭代代法法，超超松松弛弛迭迭代代法法，低低松松弛弛迭迭代代法法。數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森79 推導推導SOR迭代格式的矩陣形式（以三階方程為例）迭代格式的矩陣形式（以三階方程為例）(1)( )( )( )1312111211311111111(1)(1)( )( )2321222132222222222(1)(1)(1)( )3132333312333333333()(1)()(1)()(1)kkkkkkkkkkkkaabaxxxxaaaaaabaxxxxaaaaaabaxxxxaaaa 數值計算方法【

54、第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森80(1)( )( )( )1112213111113(1)(1)( )( )2221123322222(1)(1)(1)( )3333113223333()(1)()(1)()(1)kkkkkkkkkkkka xa xa xba xa xa xa xba xa xa xa xba x )()()1()1()1()(kkkkDxUxLxbDx 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森81 推導推導SOR迭代格式的矩陣形式迭代格式的矩陣形式(1)( )( )( )( )1

55、311211121131111111111(1)(1)( )( )( )2322122213222222222222(1)(1)(1)121121() (1)() (1)(kkkkknnkkkkknnkkknnnnnnnnnnnnaaabaxxxxxaaaaaaaabaxxxxxaaaaaaaaxxxxaaa (1)( ) (1)kknnnnnnnnbaxaa 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森82(1)( )( )( )11 11221111 1(1)(1)( )( )( )22221 123322222(1)(1)(1)(1)( )1

56、 12211() (1)() (1)() (1)kkkknnkkkkknnkkkkknnnnnnnnnnnna xa xa xba xa xa xa xa xba xa xa xa xaxba x )()()1()1()1()(kkkkDxUxLxbDx (1)(1)( )( )(1)( )()(1)()(1)kkkkkkDxbLxUxDxDL xUD xb 數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森83(1)( )11() (1)()kkxB xgBDSORLUDgDLb 迭迭代代法法的的矩矩陣陣形形式式迭迭代代矩矩陣陣右右端端向向量量收收斂斂

57、準準則則()1| 1BSORB 一一般般準準則則收收斂斂 用用加加速速，收收斂斂性性與與直直接接有有關關，因因此此，要要研研究究如如實實準準則則：何何選選擇擇用用數值計算方法【第二版】電子教案數值計算方法【第二版】電子教案 南京大學林成森南京大學林成森84111det()det() ) det(1)1(1)(1)nnniiniiiiBDLUDaa 02SOR ：方法收斂的必要條件是：方法收斂的必要條件是定理定理1() (1)BDLUD 證證：明明121det()nniiBB 又又設設的的特特征征值值為為 ， ， ， ，則則又又有有11nnii 于是有（）于是有（）數值計算方法【第二版】電子教案數值計算方法【第二