1、數值計算方法第四章 計算函數零點和極值點的迭代法本章討論非線性方程（組）的求解問題本章討論非線性方程（組）的求解問題2/801不動點不動點設非線性方程組設非線性方程組 f(x) = 0 (4.1-1)0),.,(0),.,(0),.,(21212211nnnnxxxfxxxfxxxf4.1 不動點迭代法及其收斂性3/801不動點不動點設非線性方程組設非線性方程組 f(x) = 0 (4.1-1)等價：等價： x = (x) (4.1-2)則有迭代格式：則有迭代格式：x(k+1) = (x(k)，k = 0，1，2，若若 連續，且迭代序列連續，且迭代序列x(k)收斂到收斂到x*，則兩邊取極限得，

2、則兩邊取極限得x* = (x*)，即即x*滿足滿足(4.1-2)，從而滿足，從而滿足(4.1-1)，即，即x*為為f 的零點。稱的零點。稱x*為為 (x)的不動點。的不動點。0),.,(0),.,(0),.,(21212211nnnnxxxfxxxfxxxf4/80注：注：(1) 求零點求零點求不動點求不動點(2) (.)稱為迭代函數，稱為迭代函數，x(k)稱為迭代序列稱為迭代序列(3) 不同方法構造迭代函數，得不同的迭代序列不同方法構造迭代函數，得不同的迭代序列5/802迭代法的基本問題迭代法的基本問題(1) 如何構造適當的迭代函數如何構造適當的迭代函數 (.)使迭代序列使迭代序列x(k)收

3、斂收斂(2) 收斂的速度和誤差收斂的速度和誤差(3) 如何加速如何加速6/804.1.1 解一元方程的迭代法解一元方程的迭代法1. 根的隔離根的隔離設一元方程設一元方程f(x) = 0，f 連續，其實根可能有很多，需將各連續，其實根可能有很多，需將各根隔離，即根隔離，即f在某區間在某區間a，b內有且僅有一根。內有且僅有一根。方法：設方法：設f Ca，b，f(a)f(b) 0.00001 k=k+1, x0=x1; x1=(1+x0)(1/3)end取取 (x) = x3 1 不收斂不收斂k=1, x0=1.5x1=x03-1while abs(x1-x0)0.00001 & k5 k=

4、k+1, x0=x1; x1=x03-1end31)(xx9/80定理定理4.1-1 (1) 設設 (x) Ca，b，且對于任意，且對于任意x a，b有有 (x) a，b，則，則 在在a，b上必有不動點。上必有不動點。(2) 進一步，若進一步，若 (x) C1a，b，且存在，且存在L 1，使對于任，使對于任意的意的x a，b有有 | ( x ) | L 1 (4.1-4)則對于任意的則對于任意的x(0) a，b，x(k+1) = (x(k)收斂于唯一不收斂于唯一不動點動點x* a，b。且有。且有 (4.1-5)0()1(*)()1()(*)(11xxLLxxxxLLxxkkkkk10/80證明

5、：證明：(1) 若若 (a) = a或或 (b) = b，則結論顯然成立，則結論顯然成立現設現設a (a)， (b) 0， (b) = (b) b 0，故存在故存在x* a，b，使，使 (x*) = 0，即，即 (x*) x* = 0 (x*) = x*(2) 設設 (x) C1a，b，且滿足，且滿足(4.1-4)，若有若有x1*，x2* a，b，x1* x2*， (xi*) = xi* i = 1，2由微分中值定理，由微分中值定理，|x1* x2*| = | (x1*) (x2*)| = | ()| |x1* x2*| L|x1* x2*| |x1* x2*|矛盾，所以不動點唯一。矛盾，所以

6、不動點唯一。11/80由由|x(k) x*| = | ( x(k-1) (x*)| L|x(k-1) x*| L k|x(0) x*|及及0 L 1知知即即x(k)收斂于收斂于x*。并且由并且由 |x(k) x*| L|x(k-1) x*| 得得 |x(k) x*| L|x(k-1) x(k) + x(k) x*| L|x(k-1) x(k)| + L|x(k) x*|從而有從而有0|lim*)(xxkk)1()(*)(1kkkxxLLxx12/80又因又因|x(k) x(k-1)| = | (x(k-1) (x(k-2)| L| x(k-1) x(k-2)| L k-1| x(1) x(0)

7、|，代入上式的右邊，即得，代入上式的右邊，即得注：注：(1) 若若L 1，則收斂很慢，須考慮加速問題，則收斂很慢，須考慮加速問題(2) (4.1-5)中第一式為后驗公式中第一式為后驗公式迭代停止準則迭代停止準則 第二式為先驗公式第二式為先驗公式預測迭代次數預測迭代次數(3) 定理是以定理是以a，b中任一點作初值，迭代都收斂，稱為中任一點作初值，迭代都收斂，稱為全局收斂。全局收斂。（此要求較難滿足，故考慮在）（此要求較難滿足，故考慮在）x*的某一鄰域內的某一鄰域內局部收斂性局部收斂性)0()1(*)(1xxLLxxkk13/80定理定理4.1-2 設設x*為為 的不動點，的不動點， 在在x*的某

8、鄰域內連續，的某鄰域內連續，且且| (x*)| 0，只要，只要x(0) x* ，x* + ，就有迭代法就有迭代法x(k+1) = (x(k)收斂。收斂。證明：證明：| (x*)| 0，使，使x* ，x* + U(x*)，且且 x x* ，x* + 有有| (x)| q 1 x x* ，x* + ，| (x) x*| = | (x) (x*)| = | ()| |x x*| q|x x*| 0.00001 & k25 k=k+1, x0=x1; x1=exp(-x0)end15/803. 收斂階收斂階定義定義4.1-1 設設x(k) x*，記，記ek= x(k) - x* 若存在若存在p

9、 1，及，及c 0，使，使則稱則稱x(k)是是p階收斂的，或稱收斂階為階收斂的，或稱收斂階為p（p越高收斂越快）越高收斂越快）注：注：(1) p = 1，0 c 1，稱超線性收斂，稱超線性收斂(3) p = 2，稱平方收斂，稱平方收斂ceepkkk|lim116/80因為因為| x(k+1) x*| = | (x(k) (x*)| = | ()| |x(k) x*|，其中其中在在x(k)和和x*之間。之間。則則所以若所以若 (x*) 0，則為線性收斂，則為線性收斂想得到更高階的收斂性，須想得到更高階的收斂性，須 (x*) = 0，通常可考慮泰勒展，通常可考慮泰勒展式。式。| )( |lim*1

10、xeekkk17/80定理定理4.1-3 設設x*為為 的不動點，正整數的不動點，正整數p 2，若，若 (p)在在x*的的某鄰域內連續，且滿足某鄰域內連續，且滿足 (4.1.6)則則x(k)p階局部收斂。階局部收斂。證明：證明： (x*) = 0(1)，x(k)局部收斂。局部收斂。設設 (x)在在x*處展開為處展開為0)(1,.,2 , 1, 0)(*)(*)(xpkxpkpkppkpkkkxxpxxpxxxxxxxxx)(!)()()!1()(.)(! 2)()( )()(*)()(1*)(*)1(2*)(*)(*)(18/80由由(4.1-6)知，知，所以所以即即x(k)p階局部收斂。階局

11、部收斂。pkpkkxxpxxxx)(!)()()(*)()(*)(*)1(0!)(!)()(*)()(*)(*)1(pxpxxxxpppkk19/80例例3 設設f C2a，b， (x) = x r1(x)f(x) r2(x)f 2(x)，x*為為f的單重零點。試確定未知函數的單重零點。試確定未知函數r1(x)、r2(x)，使迭代法使迭代法x(k+1) = (x(k)至少是三階局部收斂的。至少是三階局部收斂的。解：由定理解：由定理4.1-3知，應有知，應有 (x*) = (x*) = 0，因為，因為 (x) = 1 - r1(x)f(x) - r1(x)f (x) - r2(x)f 2(x)

12、- 2r2(x)f (x)f (x)而而f(x*) = 0，f (x*) 0（單重零點），（單重零點），令令 (x*) = 0，有，有1 r1(x*)f (x*) = 0，即取，即取 ，則有則有 (x*) = 0，此時有，此時有 (x) = - r1(x)f(x) - r2(x)f 2(x) - 2r2(x)f (x)f (x) (x) = - r1(x)f (x) - r1(x)f (x) - r2(x)f 2(x) - 4r2(x)f (x)f (x) - 2r2(x)f (x)2 - 2r2(x)f (x)f (x)( 1)(1xfxr20/80 (x) = - r1(x)f (x) -

13、 r1(x)f (x) - r2(x)f 2(x) - 4r2(x)f (x)f (x) - 2r2(x)f (x)2- 2r2(x)f (x)f (x)其中其中令令 (x*) = 0，有有即取即取則有則有 (x*) = 0，從而只要同時取從而只要同時取迭代法至少具有三階局部收斂性。迭代法至少具有三階局部收斂性。21)( )()( xfxfxr0)( )(2)( )(2*2*xfxrxfxf32)( 2)()(xfxfxr32)( 2)()(xfxfxr)( 1)(1xfxr21/804. 加速加速冪法中曾有冪法中曾有Aitken加速，這里使用相同的思想加速，這里使用相同的思想若若x(k) x

14、*，由中值定理，由中值定理，x(k+1) x* = (x(k) (x*) = (1)(x(k) x*) 1在在x(k)和和x*之間之間x(k+2) x* = (x(k+1) (x*) = (2)(x(k+1) x*) 2在在x(k+1)和和x*之間之間因為因為x(k) x*，所以所以當當k充分大時，充分大時， (1) (2) )( 1*)(*)1(xxxxkk)( 2*)1(*)2(xxxxkk22/80即即 (4.1-7)記記則則 比比x(k)收斂得快。收斂得快。*)(*)1(*)1(*)2(xxxxxxxxkkkk)()1()2(2)1()2()2(*2)(kkkkkkxxxxxxx)()

15、1()2(2)1()2()2()2(2)(kkkkkkkxxxxxxx)(kx23/80定理定理4.1-4 設設x(k)線性收斂于線性收斂于x*，且，且 k 0，ek = x(k) x* 0 0 | | 1 (線性收線性收斂斂)則則證明：因為證明：因為所以所以ek+1 = ( +k)ek，其中，其中k 0 x(k+1) x(k) = x(k+1) x* (x(k) x*) = ek+1 ek =( 1)+kekkkkee1lim0lim*)(*)(xxxxkkkkkkee1lim24/80又又 x(k+2) 2x(k+1) + x(k) = (x(k+2) x(k+1) (x(k+1) x(k

16、) = ( 1) + k+1ek+1 ( 1) + kek = ( 1) + k+1( + k)ek ( 1) + kek = ( 1)2 + kek.其中其中 k = k+1 +( 2 )k +k+1k 0所以所以 )()1()2(2)()1()()()1()2(2)1()()2()()1()2(2)1()2()2()2(2)(2)(2)(kkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxx) 1() 1() 1() 1(2)(22222)()1()2(2)()1(*)(*)2(kkkkkkkkkkkkkkkkeeeeexxxxxxxx25/80注：注：(1) (4.

17、1-7)稱為稱為Aitken加速加速(2) k = 1 ，2，稱為史蒂文生迭代法。稱為史蒂文生迭代法。0) 1() 1(1 (limlim21*)2(*)2(kkkkkkkkeexxxx)()()(2)()()()1()()()()(2)()()(kkkkkkkkkkkxyzyzzxyzxy)()1()2(2)1()2()2()2(2)(kkkkkkkxxxxxxx26/80例例4 用迭代法和用迭代法和Steffensen迭代法求函數迭代法求函數f(x) = x lnx 2在區間在區間(2，+ )內的零點，取內的零點，取x(0) = 3.解：將解：將f(x) = 0化為等價的方程化為等價的方程

18、x = lnx + 2 = (x)，由于由于 (x) = 1/x在在2，+ )上滿足上滿足| (x)| 1/2 1，且，且2 (x) 0.0000001) x0=x1; k=k+1 x1=log(x0)+2end28/80Steffensen迭代法迭代法x0=3k=1y=log(x0)+2z=log(y)+2x1=z-(z-y)2/(z-2*y+x0)while (abs(x1-x0)0.0000001) x0=x1;k=k+1 y=log(x0)+2 z=log(y)+2 x1=z-(z-y)2/(z-2*y+x0)end29/804.1.2 解非線性方程組的迭代法解非線性方程組的迭代法設非

19、線性方程組設非線性方程組 f(x) = 0 (4.1-1)考 慮 等 價 形 式考 慮 等 價 形 式 x = ( x ) (4.1-2)迭代公式迭代公式 x( k + 1 ) = (x( k ) k = 0，1，2， (4.1-3)其收斂性有下述壓縮映射（不動點）原理其收斂性有下述壓縮映射（不動點）原理0),.,(0),.,(0),.,(21212211nnnnxxxfxxxfxxxf30/80定理定理4.1-5 設設在閉區域在閉區域 上滿足條件上滿足條件(1) 存在存在q，0 q 0.0001 k=k+1, x0=x1; x1=log(1-x0(2),-sqrt(4-x0(1)2)end0

20、4),(01),(222121222111xxxxfxexxfx21|23| ,41|1:|21xxG2)(1)1(2)(2)1(1)(4)1ln(kkkkxxxx33/80例例5 用不動點迭代法求非線性方程用不動點迭代法求非線性方程在閉域在閉域 內的根。內的根。解：解：(2) 按迭代公式：按迭代公式： k = 0，1，2，產生的序列未必收斂（見產生的序列未必收斂（見p340）k=1,x0=1,-1.5x1=sqrt(4-x0(2)2),1-exp(x0(1)while abs(x1-x0)0.0001 & k0.00001 & k10 k=k+1, x0=x1; x1=x0-

21、(x0*exp(x0)-1)/(1+x0)*exp(x0)end)()()1 (1)()()()1(kkxkxkkkexexxx38/80(2) 若若x*是是f(x)的重根，即有的重根，即有f(x) = (x x*)mg(x)，其中其中g(x*) 0，m 2因為因為f (x) = m(x x*)m-1g(x) + (x x*)mg(x)記記x = x* + h，則，則當當m 2時，時， (x*) 0，且，且| (x*)| 0.00001 & k0.00001 & k0.00001 & k 0，使在，使在S = x | |x x*| N上上Df(x)可逆，可逆，且且f (

22、x)二次連續可微于二次連續可微于S。又因為又因為f(x*) = 0，所以若，所以若x(k) S，就有，就有x(k+1) x* = x(k) x* Df (x(k)-1f(x(k) f(x*) （f (x*) = 0） = Df (x(k) -1f(x*) f(x(k) + Df (x(k)(x(k) x*) |x(k+1) x*| |Df (x(k) -1| | f(x*) f(x(k) + Df (x(k)(x(k) x*)| |Df (x(k) -1|max|D2f (x*-t(x(k)-x*)|:0t1|x(k) - x*|2其中其中f(x(k) = f(x*) + Df (x(k)(x

23、(k) - x*)+D2f (x*- t(x(k)-x*)(x(k) - x*)249/80因為因為f 在在S上二次連續可微，所以上二次連續可微，所以max|D2f (x* t(x(k) x*)|：0 t 1 MDf (x(k) -1在在S上連續，所以上連續，所以|Df (x(k) -1| D，這里這里M、D與與k無關。無關。 |x(k+1) x*| D M |x(k) x*|2 = C|x(k) x*|2 .只要只要C 0.00001 & k10 k=k+1, x0=x1; f=x0(1)+2*x0(2)-3;2*x0(1)2+x0(2)2-5; df=1,2;4*x0(1),2*x

24、0(2); dx=-inv(df)*f x1=x0+dxend52/80注：雖然注：雖然Newton法收斂較快，但法收斂較快，但(1) 要求要求x(0)充分靠近充分靠近x*才能保證其收斂性才能保證其收斂性(2) 每一次迭代須解方程組每一次迭代須解方程組Df(x(k)x(k) = f(x(k)當當Df(x(k)不可逆時無法繼續不可逆時無法繼續53/803. 改進改進Newton下山法下山法為改善對初始值的要求，在迭代公式中引入松弛因子為改善對初始值的要求，在迭代公式中引入松弛因子 k：x(k+1) = x(k) kDf (x(k)-1f (x(k)或或 Df (x(k)x(k) = k f (x

25、(k)其中其中 k的選取滿足：的選取滿足： | | f ( x( k + 1 ) | | 0.00001 & k0.00001 & k10 k=k+1, x0=x1; f=x0(1)3-x0(2)2-1;x0(1)*x0(2)3-x0(2)-4 norm(f) df=3*x0(1)2,-2*x0(2);x0(2)3,3*x0(1)*x0(2)2-1; dx=-inv(df)*f; x1=x0+dxend1323)(,41)(2213222123212231xxxxxxDfxxxxxxf)()()1()()()()()(kkkkkkkxxxxfxxDf58/80問題：求函數問題：

26、求函數F(x)的最小值，即確定的最小值，即確定x* Rn使使注：注：(1) 該問題為最優化理論中無約束化問題該問題為最優化理論中無約束化問題(2) 上述最小值點記為上述最小值點記為)(min)(*xFxFnRx)(minarg*xFxnRx4.3 無約束優化問題的下降迭代法59/804.3.0 預備知識預備知識(1) 設設F(.)具二階連續偏導數，具二階連續偏導數，記記 F的的梯度梯度g為多元向量值函數，故有為多元向量值函數，故有Jacobi陣：陣：稱為稱為F的的Hesse矩陣矩陣nxxFxxFxFxg)()()()(12222122222212212212212)()(nnnnnxFxxFx

27、xFxxFxFxxFxxFxxFxFxDgxH60/80(2) 多元函數泰勒展開：多元函數泰勒展開：(3)(4) 設二次函數設二次函數其中其中A正定，正定，b為向量，則為向量，則 F(x) = Ax + b 其中其中 .)()(21)()()(.)()(21)()()()(TTTTyxxHyxyxyFyFyxxHyxyxygyFxFptpxFpxtpxFtpxFdtdiniiT1)()()(cxbAxxxFTT21)(bxbAxAxx)(,)21(TT61/80(5) 下降迭代法下降迭代法求求目標：構造使目標：構造使F(x)逐步嚴格下降（遞減）的迭代序列：逐步嚴格下降（遞減）的迭代序列：F(x

28、(k +1) 0（稱為步長因子）使（稱為步長因子）使 F(x( k + 1 ) = F(x( k ) + tkpk) F(x( k ) (4.3-2)若此方法產生的序列若此方法產生的序列x(k)收斂于收斂于x*，則此方法有效，否則，則此方法有效，否則無效。無效。)(minarg*xFxnRx62/80方法：不同規則對應不同的方法。方法：不同規則對應不同的方法。注注：(1) 下降方向下降方向pk的選取：的選取：由泰勒展式知，當由泰勒展式知，當t充分小時充分小時 F(x(k) + tpk) = F(x(k) + t F(x(k)Tpk +o(t) = F(x(k) + t gkTpk +o(t)其

29、中其中o(t)為為t的高階無窮小，的高階無窮小，gk = F(x(k)由由(4.3-2) F(x(k +1) = F(x(k) + tkpk) F(x(k)知，應有知，應有 gkTpk 0) 進行一維搜索來確定進行一維搜索來確定例如，取例如，取 tk = a r g m i n F ( x( k ) + t pk) (4.3-4)稱為最佳步長因子稱為最佳步長因子實際計算不易求得，實際計算不易求得，通常求不精確最佳步長因子：通常求不精確最佳步長因子：例如，使用例如，使用“成功成功-失敗失敗”試探法試探法先取定一步長因子先取定一步長因子 ，若，若F(x(k) + pk) epst = argmin

30、F(x t*g(x)x = x t*g(x)計算F(x)，g(x)= F(x)輸出x，F(x)68/80例例1 用最速下降法求解極值問題用最速下降法求解極值問題 ，其中其中F(x1，x2) = 2x12 + 2x1x2 + 5x22，取取x(0) = 1，-1T出發。出發。解：解：F(x)是二次函數，且是二次函數，且見見p350212110224)()(,10224xxxxxFxgA),(min21,21xxFxx21212121212121211022410224102 ,2410224102 ,24)()(/ )()(xxxxxxxxxxxxxxxxxAgxgxgxgt69/80例例1 用

31、最速下降法求解極值問題用最速下降法求解極值問題 ，其中其中F(x1，x2) = 2x12 + 2x1x2+5x22，取，取x(0) = 1，-1T出發。出發。Matlab代碼：代碼：k=0,x=1;-1,eps=0.001;A=4,2;2,10f=2*x(1)2 + 2*x(1)*x(2) + 5*x(2)2g=4*x(1)+2*x(2);2*x(1)+10*x(2)s=A*gt=(g*g)/(g*s)x=x-t*gwhile norm(g)eps k=k+1, f=2*x(1)2 + 2*x(1)*x(2) + 5*x(2)2 g=4*x(1)+2*x(2);2*x(1)+10*x(2) s

32、=A*g t=(g*g)/(g*s) x=x-t*gend),(min21,21xxFxx70/80注：因為最優因子注：因為最優因子tk滿足：滿足：gk+1Tgk = 0 (4.3-7)所以方向所以方向pk+1與與pk總是互相垂直的，稱為鋸齒狀下降（圖總是互相垂直的，稱為鋸齒狀下降（圖4.3-1）此方向在接近極小值點時收斂速度變慢。）此方向在接近極小值點時收斂速度變慢。71/804.3.2 變尺度法變尺度法1. 思想思想為了改善收斂速度，考慮在為了改善收斂速度，考慮在x*處的泰勒展開：處的泰勒展開：因為因為g(x*) = 0 所以所以 F(x) = g(x) H(x*)(x x*) 設設H正定

33、（從而可逆），令正定（從而可逆），令H(x*)(x x*) = g(x) x* = x H(x*)-1g(x) = x Bg(x) (4.3-10)上式表明：用上式表明：用B = H(x*)-1作用于作用于 g(x)，將使最速下降方，將使最速下降方向向 g(x)變為直指變為直指x* 啟示：用啟示：用Bg(x)作搜索方向。作搜索方向。)()(21)()()()(*xxxHxxxxxgxFxFTT)()(21)()(*xxxHxxxFxFTAxAxx)21(T72/802. 迭代公式迭代公式為了保證為了保證Bg(x)是下降方向，由是下降方向，由(4.3-3)知，只須知，只須 g(x)T(Bg(x)

34、 0。所以當所以當B正定時（正定時（g(x)TBg(x) 0），必有），必有Bg(x)為下降為下降方向，從而迭代公式為方向，從而迭代公式為 x(k +1) = x(k) tkBkgk k = 0，1，2，. (4.3-11)其中其中tk為步長因子，可通過一維搜索來確定為步長因子，可通過一維搜索來確定73/80注：注：(1) 當當 Bk = I時，時，(4.3-11)即為最速下降法的迭代公式即為最速下降法的迭代公式(2) 當當Bk = H(x(k)-1時，迭代公式為時，迭代公式為 x(k +1) = x(k) tkH(x(k) -1gk k = 0，1，2，. (4.3-12) = x(k) t

35、kDg(x(k) -1gk (Dg(x(k)為為g的的Jacobi矩陣矩陣)即為即為Newton下山法下山法(3) 由于由于F(x)的的Hesse矩陣矩陣H(x) = Dg(x)之逆可能在某些點之逆可能在某些點不存在，即使存在，計算量也很大，不存在，即使存在，計算量也很大，所以考慮從所以考慮從H(x(k) -1的近似方陣出發，每次迭代進行修的近似方陣出發，每次迭代進行修正（下述方法）。正（下述方法）。74/803. DFP方法方法考慮對考慮對Bk = H(x(k) -1附加條件附加條件(1) Bk應正定應正定(2) 從從Bk到到Bk+1應簡單：應簡單：Bk+1= Bk+ Bk(3) Bk滿足擬滿足擬New