計(jì)算函數(shù)零點(diǎn)和極值點(diǎn)迭代法

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

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

3、斂收斂(2) 收斂的速度和誤差收斂的速度和誤差(3) 如何加速如何加速6/804.1.1 解一元方程的迭代法解一元方程的迭代法1. 根的隔離根的隔離設(shè)一元方程設(shè)一元方程f(x) = 0，f 連續(xù)，其實(shí)根可能有很多，需將各連續(xù)，其實(shí)根可能有很多，需將各根隔離，即根隔離，即f在某區(qū)間在某區(qū)間a，b內(nèi)有且僅有一根。內(nèi)有且僅有一根。方法：設(shè)方法：設(shè)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=k+1,

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

5、(1) 若若 (a) = a或或 (b) = b，則結(jié)論顯然成立，則結(jié)論顯然成立現(xiàn)設(shè)現(xiàn)設(shè)a (a)， (b) 0， (b) = (b) b 0，故存在故存在x* a，b，使，使 (x*) = 0，即，即 (x*) x* = 0 (x*) = x*(2) 設(shè)設(shè) (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*|矛盾，所以不動(dòng)點(diǎn)唯一。矛盾，所以不動(dòng)點(diǎn)唯

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)中第一式為后驗(yàn)公式中第一式為后驗(yàn)公式迭代停止準(zhǔn)則迭代停止準(zhǔn)則 第二式為先驗(yàn)公式第二式為先驗(yàn)公式預(yù)測(cè)迭代次數(shù)預(yù)測(cè)迭代次數(shù)(3) 定理是以定理是以a，b中任一點(diǎn)作初值，迭代都收斂，稱為中任一點(diǎn)作初值，迭代都收斂，稱為全局收斂。全局收斂。（此要求較難滿足，故考慮在）（此要求較難滿足，故考慮在）x*的某一鄰域內(nèi)的某一鄰域內(nèi)局部收斂性局部收斂性)0()1(*)(1xxLLxxkk13/80定理定理4.1-2 設(shè)設(shè)x*為為 的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)， 在在x*的某鄰域內(nèi)連

8、續(xù)，的某鄰域內(nèi)連續(xù)，且且| (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 設(shè)設(shè)x(k) x*，記，記ek= x(k) - x* 若存在若存在p 1，及，及c

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

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

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

12、f (x)f (x)而而f(x*) = 0，f (x*) 0（單重零點(diǎn)），（單重零點(diǎn)），令令 (x*) = 0，有，有1 r1(x*)f (x*) = 0，即取，即取 ，則有則有 (x*) = 0，此時(shí)有，此時(shí)有 (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) - r1(x)f

13、(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，從而只要同時(shí)取從而只要同時(shí)取迭代法至少具有三階局部收斂性。迭代法至少具有三階局部收斂性。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*之間之間因?yàn)橐驗(yàn)閤(k) x*，所以所以當(dāng)當(dāng)k充分大時(shí)，充分大時(shí)， (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)()1()2(2)1

15、()2()2()2(2)(kkkkkkkxxxxxxx)(kx23/80定理定理4.1-4 設(shè)設(shè)x(k)線性收斂于線性收斂于x*，且，且 k 0，ek = x(k) x* 0 0 | | 1 (線性收線性收斂斂)則則證明：因?yàn)樽C明：因?yàn)樗运詄k+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) = ( 1)

16、 + 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.1-7)稱為稱為

17、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迭代法求函數(shù)迭代法求函數(shù)f(x) = x lnx 2在區(qū)間在區(qū)間(2，+ )內(nèi)的零點(diǎn)，取內(nèi)的零點(diǎn)，取x(0) = 3.解：將解：將f(x) = 0化為等價(jià)的方程化為等價(jià)的方程x = lnx

18、+ 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 解非線性方程組的迭代法解非線性方程組的迭代法設(shè)非線性方程組設(shè)非線

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

20、(222121222111xxxxfxexxfx21|23| ,41|1:|21xxG2)(1)1(2)(2)1(1)(4)1ln(kkkkxxxx33/80例例5 用不動(dòng)點(diǎn)迭代法求非線性方程用不動(dòng)點(diǎn)迭代法求非線性方程在閉域在閉域 內(nèi)的根。內(nèi)的根。解：解：(2) 按迭代公式：按迭代公式： k = 0，1，2，產(chǎn)生的序列未必收斂（見產(chǎn)生的序列未必收斂（見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-(x0*exp(x0)-1)/(

21、1+x0)*exp(x0)end)()()1 (1)()()()1(kkxkxkkkexexxx38/80(2) 若若x*是是f(x)的重根，即有的重根，即有f(x) = (x x*)mg(x)，其中其中g(shù)(x*) 0，m 2因?yàn)橐驗(yàn)閒 (x) = m(x x*)m-1g(x) + (x x*)mg(x)記記x = x* + h，則，則當(dāng)當(dāng)m 2時(shí)，時(shí)， (x*) 0，且，且| (x*)| 0.00001 & k0.00001 & k0.00001 & k 0，使在，使在S = x | |x x*| N上上Df(x)可逆，可逆，且且f (x)二次連續(xù)可微于二次連續(xù)可微于S。又因?yàn)橛忠驗(yàn)閒(x*

22、) = 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(k) - x*)+D2f (x*- t(x(k)-x*

23、)(x(k) - x*)249/80因?yàn)橐驗(yàn)閒 在在S上二次連續(xù)可微，所以上二次連續(xù)可微，所以max|D2f (x* t(x(k) x*)|：0 t 1 MDf (x(k) -1在在S上連續(xù)，所以上連續(xù)，所以|Df (x(k) -1| D，這里這里M、D與與k無關(guān)。無關(guān)。 |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*x0(2); dx=-inv(df)*f x1=x0+dxend5

24、2/80注：雖然注：雖然Newton法收斂較快，但法收斂較快，但(1) 要求要求x(0)充分靠近充分靠近x*才能保證其收斂性才能保證其收斂性(2) 每一次迭代須解方程組每一次迭代須解方程組Df(x(k)x(k) = f(x(k)當(dāng)當(dāng)Df(x(k)不可逆時(shí)無法繼續(xù)不可逆時(shí)無法繼續(xù)53/803. 改進(jìn)改進(jìn)Newton下山法下山法為改善對(duì)初始值的要求，在迭代公式中引入松弛因子為改善對(duì)初始值的要求，在迭代公式中引入松弛因子 k：x(k+1) = x(k) kDf (x(k)-1f (x(k)或或 Df (x(k)x(k) = k f (x(k)其中其中 k的選取滿足：的選取滿足： | | f ( x(

25、 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問題：求函數(shù)問題：求函數(shù)F(x)的最小值，即確定的最小值，即確定x* Rn使使注：注：(1) 該問

26、題為最優(yōu)化理論中無約束化問題該問題為最優(yōu)化理論中無約束化問題(2) 上述最小值點(diǎn)記為上述最小值點(diǎn)記為)(min)(*xFxFnRx)(minarg*xFxnRx4.3 無約束優(yōu)化問題的下降迭代法59/804.3.0 預(yù)備知識(shí)預(yù)備知識(shí)(1) 設(shè)設(shè)F(.)具二階連續(xù)偏導(dǎo)數(shù)，具二階連續(xù)偏導(dǎo)數(shù)，記記 F的的梯度梯度g為多元向量值函數(shù)，故有為多元向量值函數(shù)，故有Jacobi陣：陣：稱為稱為F的的Hesse矩陣矩陣nxxFxxFxFxg)()()()(12222122222212212212212)()(nnnnnxFxxFxxFxxFxFxxFxxFxxFxFxDgxH60/80(2) 多元函數(shù)泰勒展開

27、：多元函數(shù)泰勒展開：(3)(4) 設(shè)二次函數(shù)設(shè)二次函數(shù)其中其中A正定，正定，b為向量，則為向量，則 F(x) = Ax + b 其中其中 .)()(21)()()(.)()(21)()()()(TTTTyxxHyxyxyFyFyxxHyxyxygyFxFptpxFpxtpxFtpxFdtdiniiT1)()()(cxbAxxxFTT21)(bxbAxAxx)(,)21(TT61/80(5) 下降迭代法下降迭代法求求目標(biāo)：構(gòu)造使目標(biāo)：構(gòu)造使F(x)逐步嚴(yán)格下降（遞減）的迭代序列：逐步嚴(yán)格下降（遞減）的迭代序列：F(x(k +1) 0（稱為步長因子）使（稱為步長因子）使 F(x( k + 1 )

28、= F(x( k ) + tkpk) F(x( k ) (4.3-2)若此方法產(chǎn)生的序列若此方法產(chǎn)生的序列x(k)收斂于收斂于x*，則此方法有效，否則，則此方法有效，否則無效。無效。)(minarg*xFxnRx62/80方法：不同規(guī)則對(duì)應(yīng)不同的方法。方法：不同規(guī)則對(duì)應(yīng)不同的方法。注：注：(1) 下降方向下降方向pk的選?。旱倪x?。河商├照故街?dāng)由泰勒展式知，當(dāng)t充分小時(shí)充分小時(shí) F(x(k) + tpk) = F(x(k) + t F(x(k)Tpk +o(t) = F(x(k) + t gkTpk +o(t)其中其中o(t)為為t的高階無窮小，的高階無窮小，gk = F(x(k)由由(4

29、.3-2) F(x(k +1) = F(x(k) + tkpk) F(x(k)知，應(yīng)有知，應(yīng)有 gkTpk 0) 進(jìn)行一維搜索來確定進(jìn)行一維搜索來確定例如，取例如，取 tk = a r g m i n F ( x( k ) + t pk) (4.3-4)稱為最佳步長因子稱為最佳步長因子實(shí)際計(jì)算不易求得，實(shí)際計(jì)算不易求得，通常求不精確最佳步長因子：通常求不精確最佳步長因子：例如，使用例如，使用“成功成功-失敗失敗”試探法試探法先取定一步長因子先取定一步長因子 ，若，若F(x(k) + pk) eps k=k+1, f=2*x(1)2 + 2*x(1)*x(2) + 5*x(2)2 g=4*x(1

30、)+2*x(2);2*x(1)+10*x(2) s=A*g t=(g*g)/(g*s) x=x-t*gend),(min21,21xxFxx70/80注：因?yàn)樽顑?yōu)因子注：因?yàn)樽顑?yōu)因子tk滿足：滿足：gk+1Tgk = 0 (4.3-7)所以方向所以方向pk+1與與pk總是互相垂直的，稱為鋸齒狀下降（圖總是互相垂直的，稱為鋸齒狀下降（圖4.3-1）此方向在接近極小值點(diǎn)時(shí)收斂速度變慢。）此方向在接近極小值點(diǎn)時(shí)收斂速度變慢。71/804.3.2 變尺度法變尺度法1. 思想思想為了改善收斂速度，考慮在為了改善收斂速度，考慮在x*處的泰勒展開：處的泰勒展開：因?yàn)橐驗(yàn)間(x*) = 0 所以所以 F(x)

31、 = g(x) H(x*)(x x*) 設(shè)設(shè)H正定（從而可逆），令正定（從而可逆），令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)變?yōu)橹敝缸優(yōu)橹敝竫* 啟示：用啟示：用Bg(x)作搜索方向。作搜索方向。)()(21)()()()(*xxxHxxxxxgxFxFTT)()(21)()(*xxxHxxxFxFTAxAxx)21(T72/802. 迭代公式迭代公式為了保證為了保證Bg(x)是下降方向，由是下降方向，由(4

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

33、0，1，2，. (4.3-12) = x(k) tkDg(x(k) -1gk (Dg(x(k)為為g的的Jacobi矩陣矩陣)即為即為Newton下山法下山法(3) 由于由于F(x)的的Hesse矩陣矩陣H(x) = Dg(x)之逆可能在某些點(diǎn)之逆可能在某些點(diǎn)不存在，即使存在，計(jì)算量也很大，不存在，即使存在，計(jì)算量也很大，所以考慮從所以考慮從H(x(k) -1的近似方陣出發(fā)，每次迭代進(jìn)行修的近似方陣出發(fā)，每次迭代進(jìn)行修正（下述方法）。正（下述方法）。74/803. DFP方法方法考慮對(duì)考慮對(duì)Bk = H(x(k) -1附加條件附加條件(1) Bk應(yīng)正定應(yīng)正定(2) 從從Bk到到Bk+1應(yīng)簡(jiǎn)單：應(yīng)簡(jiǎn)單：Bk+1= Bk+ Bk(3) Bk滿足擬滿足擬Newdon條件：條件：Bk+1yk = sk，其中，其中yk = gk+1 gk，sk = x(k +1) x(k) 從