第三章一維搜索(線性搜索)

1、第三章第三章 一維搜索方一維搜索方法法3.1 概述概述3.2 確定初始區(qū)間確定初始區(qū)間3.3 縮小區(qū)間縮小區(qū)間3.4 黃金分割法（黃金分割法（0.618法）法）3.5 一維搜索的插值方法一維搜索的插值方法2()0f X12(,)TnXx xx第3章 一維搜索方法3.1 概述3.1.1 一維問題是多維問題的基礎 求目標函數(shù) f (X)的極小點，從理論上說需要求解方程：其中那么如何來求 f (X)的極小點呢？基本思想:011,kkXXXX011()() ,()()kkf Xf Xf Xf X 這種方法是逐次迭代的方法，在電子計算機上很容易實現(xiàn)，這種方法是逐次迭代的方法，在電子計算機上很容易實現(xiàn)，因

2、此它在優(yōu)化設計中被廣泛地采用。因此它在優(yōu)化設計中被廣泛地采用。3kkkSXfkkkSXfmin:kkkkSaXX1()f X這個過程稱為一維搜索過程。kkkSXf52128)(212221xxxxXF如：如：52202521282212221xxxxF則則000 0 ,1 1TTXd1100X當當Sk方向上的任何一點可以表示為其中是步長因子，為實系數(shù)，此時 Sk 方向上任何一點的目標函數(shù)值為 ，它是參數(shù)的一元函數(shù)。那么在沿 Sk 方向求的極小點，這就是求一元函數(shù) 的極小問題，它可表示為：)2 , 1 , 0(1kSXXkkk一維搜索示意圖一維搜索示意圖 求多元函數(shù)極值點，需要進行一系列的一維搜

3、索?？梢娗蠖嘣瘮?shù)極值點，需要進行一系列的一維搜索?？梢娨灰痪S搜索是優(yōu)化搜索方法的基礎維搜索是優(yōu)化搜索方法的基礎。 求解一元函數(shù)求解一元函數(shù) 的極小點的極小點 ，可采用，可采用解析解法解析解法，即利用一元函數(shù)的極值條件即利用一元函數(shù)的極值條件 求求n在用函數(shù)在用函數(shù) 的導數(shù)求的導數(shù)求 時，所用的函數(shù)時，所用的函數(shù) 是僅以步長因子是僅以步長因子 為變量的一元函數(shù)，而不是以為變量的一元函數(shù)，而不是以設計點設計點 x x 為變量的多元函數(shù)為變量的多元函數(shù) 。)(*0)(*)(*)()(xf3.1.2 的確定方法的確定方法為了直接利用為了直接利用 的函數(shù)式求解最佳步長因子的函數(shù)式求解最佳步長因子 。把

4、把 或它的簡寫形式或它的簡寫形式 進行泰勒展開，進行泰勒展開，取到二階項，即取到二階項，即 將上式對將上式對 進行微分并令其等于零，給出進行微分并令其等于零，給出 極值點極值點 應滿足的條件應滿足的條件 從而求得從而求得這里是直接利用函數(shù)這里是直接利用函數(shù) 而不需要把它化成步長因而不需要把它化成步長因子子 。的函數(shù)。的函數(shù) 。不過，此時需要計算。不過，此時需要計算 點處點處梯度梯度 和海賽矩陣和海賽矩陣 H H 。n 解析解法的缺點解析解法的缺點需要進行求導計算。需要進行求導計算。o 對于函數(shù)關系復雜、求導困難或無法求導的情況，使用對于函數(shù)關系復雜、求導困難或無法求導的情況，使用解析法將是非常

5、不便的。解析法將是非常不便的。 因此，在優(yōu)化設計中，求解最佳步長因子因此，在優(yōu)化設計中，求解最佳步長因子 主要采用主要采用數(shù)數(shù)值解法值解法，利用計算機通過反復迭代計算求得最佳步長因子，利用計算機通過反復迭代計算求得最佳步長因子的近似值。的近似值。n 數(shù)值解法的基本思路是：首先確定數(shù)值解法的基本思路是：首先確定 所在的搜索區(qū)間，所在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得 的數(shù)的數(shù) 值近似解。值近似解。 解析法解析法: : f(X f(X(k)(k) + S + S(k) (k) ) ) 沿沿S S(k)(k) 方向在方向在x x(

6、k)(k) 點泰勒展開；點泰勒展開； 取二次近似：取二次近似： ( )( )( )( )( )2( )( )( )1()()()2kkkkTkkTkkf xSf xf xSSG xS 0)()()(kkSxfdd對對求導，令其為零。求導，令其為零。 ()()()()()()()0kTkkTkkfxSSG xS()()()()()()()()kTkkkTkkfxSSGxS 求得最優(yōu)步長求得最優(yōu)步長1()()()kkkkkffs xx數(shù)值解法數(shù)值解法基本思路：基本思路： kk 解析解法對于函數(shù)關系復雜、求導困難等情況難以解析解法對于函數(shù)關系復雜、求導困難等情況難以實現(xiàn)。在實際優(yōu)化設計中，數(shù)值解法的

7、應用更為有效，實現(xiàn)。在實際優(yōu)化設計中，數(shù)值解法的應用更為有效，且適合計算機的運算特點。且適合計算機的運算特點。 一維搜索也稱一維搜索也稱直線搜索直線搜索。這種方法不僅對于解決。這種方法不僅對于解決一維最優(yōu)化問題具有實際意義，而且也是求解多維最優(yōu)一維最優(yōu)化問題具有實際意義，而且也是求解多維最優(yōu)化問題的重要支柱?；瘑栴}的重要支柱。一維搜索一般分為兩大步驟：一維搜索一般分為兩大步驟：(1)(1)確定初始搜索區(qū)間確定初始搜索區(qū)間aa，bb，該區(qū)間應是包括一維函數(shù)，該區(qū)間應是包括一維函數(shù)極小點在內(nèi)的極小點在內(nèi)的單谷區(qū)間單谷區(qū)間。(2)(2)在單谷區(qū)間在單谷區(qū)間a,ba,b內(nèi)通過縮小區(qū)間尋找極小點。內(nèi)通過

8、縮小區(qū)間尋找極小點。 先確定先確定 在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間所，從而獲得不斷縮小此區(qū)間所，從而獲得 的數(shù)值近似解。的數(shù)值近似解。1、確定搜索區(qū)間的外推法 在給定區(qū)間內(nèi)僅有一個谷值（或有唯一的極小點）的函數(shù)稱為單谷函數(shù)，其區(qū)間稱為單谷區(qū)間。函數(shù)值：“大小大”圖形：“高低高”單谷區(qū)間中一定能求得一個極小點。3.2 確定初始區(qū)間確定初始區(qū)間o 從從 開始，以初始步長開始，以初始步長 向前試探。向前試探。n 如果函數(shù)值上升，則步長變號，即改變試探方向。如果函數(shù)值上升，則步長變號，即改變試探方向。n 如果函數(shù)值下降，則維持原來的試探方向，并將

9、步長加倍。如果函數(shù)值下降，則維持原來的試探方向，并將步長加倍。n 區(qū)間的始點、中間點依次沿試探方向移動一步。區(qū)間的始點、中間點依次沿試探方向移動一步。n 此過程一直進行到函數(shù)值再次上升時為止，即可找到搜索此過程一直進行到函數(shù)值再次上升時為止，即可找到搜索區(qū)間的終點。區(qū)間的終點。n 最后得到的三點即為搜索區(qū)間的始點、中間三點和終點，最后得到的三點即為搜索區(qū)間的始點、中間三點和終點，形成函數(shù)值的形成函數(shù)值的“高低高高低高”趨勢。趨勢。單谷區(qū)間單谷區(qū)間f (x)0130f (x)31說明：單谷區(qū)間內(nèi)，函數(shù)可以有不可微點，也可以是不連續(xù)函數(shù)；基本思想：基本思想：對對 任選一個初始點任選一個初始點 及初

10、始步長及初始步長 ，通過比較這兩點函數(shù)值的大小，確定第三點位置，比較這通過比較這兩點函數(shù)值的大小，確定第三點位置，比較這三點的函數(shù)值大小，確定是否為三點的函數(shù)值大小，確定是否為“高高低低高高”形態(tài)。形態(tài)。)(xf1ah步驟：步驟： 1 1）選定初始點）選定初始點a a1 1，初始步長，初始步長h=hh=h0 0，計算，計算y y1 1=f(a=f(a1 1) )和和y y2 2=f(a=f(a1 1+h)+h)2 2）比較）比較y y1 1和和y y2 2；a a）如果）如果y y1 1yy2 2，向右前進，加大步長，向右前進，加大步長h=2hh=2h0 0，轉(zhuǎn)（，轉(zhuǎn)（3 3）向前；）向前；b

11、 b）如果）如果y y1 1yyy3 3 ，加大步長，加大步長h=2hh=2h，a a1 1=a=a2 2,a,a2 2=a=a3 3, ,轉(zhuǎn)（轉(zhuǎn)（3 3）繼）繼續(xù)探測；續(xù)探測；b b）如果）如果y y2 2y0h0否否初始進退距初始進退距3xf2x1xx1x2x3x前進計算1x2x3xfx1x2x3x后退計算1x2x1y2y3y ,a b11,a b， 搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點的數(shù)值近似解。 假定在搜索區(qū)間 內(nèi)任取兩點 ，且 )(2)(111bffaff3.3 區(qū)間消去方法區(qū)間消去方法(1)(1)f f（a a1 1） f f（b b1 1）, , 則

12、極小點必在區(qū)間則極小點必在區(qū)間aa，b b1 1 內(nèi)內(nèi); ;)(2)(111bffaff(1)(1)f f（a a1 1） f f（b b1 1）, , 則極小點必在區(qū)間則極小點必在區(qū)間 1 1，bb內(nèi)內(nèi); ;)(2)(111bffaff(1)(1)f f（a a1 1） f f（b b1 1）, , 則極小點必在區(qū)間則極小點必在區(qū)間 1 1，bb內(nèi)內(nèi); ;(3)(3)f f（a a1 1）= =f f（b b1 1）, , 則極小點必在區(qū)間則極小點必在區(qū)間 1 1，b b1 1 內(nèi)內(nèi))(2)(111bffaff可以總結(jié)為兩種情況：若 ， 則取a,b1為縮小后的搜索區(qū)間。若 ，則取a1,b為縮

13、小后的搜索區(qū)間。)()(11bfaf)()(11bfaf試探法 黃金分割法插值法 二次插值法3 一維搜索方法分類 從前面的分析可知，每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點并計算其函數(shù)值。 而插入點的位置，可以由不同的方法來確定。就形成了不同的一維搜索方法。一維搜索方法分類3.4 黃金分割法（0.618法）黃金分割法黃金分割法的搜索過程 概述概述n 在實際計算中，最常用的在實際計算中，最常用的一維搜索試探方法是黃金分割法一維搜索試探方法是黃金分割法，又稱作又稱作0.6180.618法法。我們可以通過學習黃金分割法來了解一。我們可以通過學習黃金分割法來了解一維搜索試探方法的基本思想。維搜索試探方法

14、的基本思想。n 在搜索區(qū)間在搜索區(qū)間 a,ba,b內(nèi)適當插入兩點內(nèi)適當插入兩點1 1、2 2，并計算其函，并計算其函數(shù)值。數(shù)值。1 1、2 2將區(qū)間分成三段。應用函數(shù)的單谷性質(zhì)，將區(qū)間分成三段。應用函數(shù)的單谷性質(zhì)，通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。然后再在保留下來的區(qū)間上作同樣的處置，如此迭縮短。然后再在保留下來的區(qū)間上作同樣的處置，如此迭代下去，使搜索區(qū)間無限縮小，從而得到極小點的數(shù)值近代下去，使搜索區(qū)間無限縮小，從而得到極小點的數(shù)值近似解。似解。3.4 黃金分割法（0.618法）黃金分割法是建立在區(qū)間消去法原理基礎上的

15、試探方法。黃金分割法是建立在區(qū)間消去法原理基礎上的試探方法。o 適用于適用于a,ba,b區(qū)間上的任何單谷函數(shù)求極小值問題。區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求對函數(shù)除要求“單谷單谷”外不作其它要求，甚至可以不連外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應面相當廣。續(xù)。因此，這種方法的適應面相當廣。n 黃金分割法對插入點的要求：黃金分割法對插入點的要求： 1 1）要求插入點）要求插入點1 1、2 2 的位置相對于區(qū)間的位置相對于區(qū)間a,ba,b兩端兩端點具有對稱性點具有對稱性，即，即 其中其中 為待定常數(shù)。為待定常數(shù)。1()bba2()aba1.黃金分割法黃金分割法2 2）黃金

16、分割法還要求黃金分割法還要求在保留下來的區(qū)間內(nèi)再插入一點所在保留下來的區(qū)間內(nèi)再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布例分布。 即每次縮小所得的新區(qū)間長度與縮小前區(qū)間長度即每次縮小所得的新區(qū)間長度與縮小前區(qū)間長度之比（即：區(qū)間收縮率）為定值。之比（即：區(qū)間收縮率）為定值。o 設原區(qū)間設原區(qū)間a,ba,b長度為長度為1 1如下圖所示，保留下來的區(qū)間如下圖所示，保留下來的區(qū)間 a,a,2 2 長度為長度為 ，區(qū)間縮短率為，區(qū)間縮短率為 。為了保持相。為了保持相同的比例分布，新插入點同的比例分布，新插入點 3 3應在應在 位位置上，

17、置上，1 1 在原區(qū)間的在原區(qū)間的 位置應相當于在保位置應相當于在保留區(qū)間的留區(qū)間的 位置。故有位置。故有 取方程正數(shù)解，得取方程正數(shù)解，得ab2111a213(1)2圖2-5 黃金分割法)(618. 0)()(618. 0)(21abaabaabbabb兩內(nèi)分點值兩內(nèi)分點值:結(jié)論：結(jié)論：所謂黃金分割是指將一線段分成兩段的方法，使整段長與較長段的長度所謂黃金分割是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段長度的比值即比值等于較長段與較短段長度的比值即 。215 10.6182 黃金分割法要求插入兩點：)(618. 0)()(618. 0)(21abaabaabbab

18、b黃金分割法區(qū)間消去示意圖：3.4 黃金分割法（黃金分割法（0.6180.618法）法）（1）給出初始搜索區(qū)間 及收斂精度 ，將 賦以 。 , a b0.618（2）按坐標點計算公式計算 并計算其對應的函數(shù)值 12和12,ff3.4 黃金分割法（黃金分割法（0.6180.618法）法）（3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標點計算公式，進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及其函數(shù)值。3.4 黃金分割法（黃金分割法（0.6180.618法）法）（4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度，如果收斂條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解。如

19、果條件不滿足則轉(zhuǎn)向步驟5。（5）產(chǎn)生新的插入點：如N0=0，則?。?）如果條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解。3.4 黃金分割法（黃金分割法（0.6180.618法）法）618.0ln)/(lnabk縮短區(qū)間的總次數(shù)（迭代次數(shù)）:給定,ba)(),(618. 0222xfyabax)(),(382. 0111xfyabax21yy 否否21211,yyxxxa)(),(618. 0222xfyabax是)(),(382. 0111xfyabax12122,yyxxxbab是)()(5 . 0 xffbax止xfab1x2x1y2y1x2xbxfab1x2x1y2y1x2x

20、a也可采用迭代次數(shù)是否大于或等于 k 作終止準則。38迭代序號aby1比較y20-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.665例3-3：用黃金分割法求 的極小值 ，搜索區(qū)間是2( )2f35 *12解：abaabb2139*1()21( 1.3860.665)21.0255ab *()1.0007f 解析解：1,( )1f 例例 3-1 用黃金分割法求函數(shù)用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，給的

21、極小點，給定定 x0=0, h=1, =0.2。解：1）確定初始區(qū)間a1=x0=0, f1=f(a1)=2a2=x0+h=0+1=1, f2=f(a2)=1由于f1f2, 應加大步長繼續(xù)向前探測。a3= x0+2h=0+2=2, f3=f(a3)=18由于f2f3,可知初始區(qū)間已經(jīng)找到，即a,b=a1,a3=0,22）用黃金分割法縮小區(qū)間 第一次縮小區(qū)間： a1=0+0.382(2-0)=0.764, f1=0.282 a2=0+0.618 (2-0)=1.236, f2=2.72 f10.2第二次縮小區(qū)間：第二次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0+0

22、.382X X(1.236-0)=0.472, f1=0.317 由于由于f1f2, 故新區(qū)間故新區(qū)間a,b=x1,b=0.472, 1.236 因為因為 b-a=1.236-0.472=0.7640.2, 應繼續(xù)縮小區(qū)間。應繼續(xù)縮小區(qū)間。 第三次縮小區(qū)間：l令 x1=x2=0.764, f1=f2=0.282l x2=0.472+0.618X(1.236-0.472)=0.944, f2=0.747l由于f10.2, 應繼續(xù)縮小區(qū)間。 第四次縮小區(qū)間：第四次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X X(0.944-0.472)=0.6

23、52, f1=0.223 由于由于f10.2, 應繼續(xù)縮小區(qū)間。應繼續(xù)縮小區(qū)間。第五次縮小區(qū)間：l令 x2=x1=0.652, f2=f1=0.223l x1=0.472+0.382X(0.764-0.472)=0.584, f1=0.262l由于f1f2, 故新區(qū)間a,b=x1,b=0.584, 0.764l因為 b-a=0.764-0.584=0.180.2, 停止迭代。極小點與極小值：x*=0.5X(0.584+0.764)=0.674, f(x*)=0.2223.5 一維搜索的二次插值法一維搜索的二次插值法試探法試探法（如黃金分割法）與（如黃金分割法）與插值法插值法的比較：的比較：不同

24、點不同點：表現(xiàn)在試驗點（插入點）位置的確定方法不同。：表現(xiàn)在試驗點（插入點）位置的確定方法不同。n多項式是函數(shù)逼近的一種常用工具。多項式是函數(shù)逼近的一種常用工具。o 在搜索區(qū)間內(nèi)可以利用若干試驗點處的函數(shù)在搜索區(qū)間內(nèi)可以利用若干試驗點處的函數(shù)值來構造低次多項式，用它作為函數(shù)的近似值來構造低次多項式，用它作為函數(shù)的近似表達式，并用這個多項式的極小點作為原函表達式，并用這個多項式的極小點作為原函數(shù)極小點的近似。數(shù)極小點的近似。n常用的插值多項式為常用的插值多項式為二次多項式。二次多項式。o 牛頓法（切線法）牛頓法（切線法） 利用一點的函數(shù)值、一利用一點的函數(shù)值、一階導數(shù)值和二階導數(shù)值來構造二次函數(shù)

25、。階導數(shù)值和二階導數(shù)值來構造二次函數(shù)。1.1. 二次插值法（拋物線法）二次插值法（拋物線法） 利用三個點的函利用三個點的函數(shù)值形成一個拋物線來構造二次函數(shù)。數(shù)值形成一個拋物線來構造二次函數(shù)。1、牛頓法（切線法）、牛頓法（切線法） 對于一維搜索函數(shù)對于一維搜索函數(shù) ，假定已經(jīng)給出極小點的一個較，假定已經(jīng)給出極小點的一個較好的近似點好的近似點 ，在，在 點附近用一個二次函數(shù)點附近用一個二次函數(shù) 來逼近函數(shù)來逼近函數(shù) 。 yf00 f 20000012ffff 然后以該二次函數(shù)然后以該二次函數(shù) 的極小點作為的極小點作為 極小點的一個新的極小點的一個新的近似點近似點 。根據(jù)極值必要條件：。根據(jù)極值必要

26、條件： f1 0 0100ff 1(0,1,2 )kkkkfkf牛頓法的幾何解釋：牛頓法的幾何解釋：1(0,1,2)kkkkfkf在上圖中，在在上圖中，在 處用一拋物線處用一拋物線 代替曲線代替曲線 ，相當于用一斜線相當于用一斜線 代替代替 。這樣各個近似點是。這樣各個近似點是通過對通過對 作切線求得與作切線求得與 軸的交點找到，故牛頓法軸的交點找到，故牛頓法又稱為切線法。又稱為切線法。)(f0)()()(f)(f牛頓法的計算步驟：牛頓法的計算步驟：1 1）給定初始點）給定初始點 0，控制誤差，控制誤差 ，并令，并令 0k 2 2）計算）計算 ,kkff3 3）求）求 1kkkkff4 4）若

27、）若 1kk，則求得近似解，則求得近似解 ，1k停止計算，否則作停止計算，否則作5 5）。）。 5 5）令）令 1kk轉(zhuǎn)轉(zhuǎn)2 2）。）。 例題：例題： 給定給定 43246164f，試用，試用牛頓法求其極小點牛頓法求其極小點 。 解：解：1 1）給定初始點）給定初始點 03，控制誤差，控制誤差 0.001 324(334)f 212(21)f01001331366ff31133662 2）3 3）4 4）重復上邊的過程，進行迭代，直到重復上邊的過程，進行迭代，直到 10.001kk為止?？傻玫接嬎憬Y(jié)果如下表為止?？傻玫接嬎憬Y(jié)果如下表: : 表3-2 牛頓法的搜索過程k01234值ak35.16

28、6674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059優(yōu)點：收斂速度快。優(yōu)點：收斂速度快。缺點：每一點都要進行二階導數(shù)，工作量大；缺點：每一點都要進行二階導數(shù)，工作量大； 當用數(shù)值微分代替二階導數(shù)，由于舍入誤當用數(shù)值微分代替二階導數(shù)，由于舍入誤差會影響迭代速度；差會影響迭代速度； 要求初始點離極小點不太遠，否則有可能要求初始點離極小點不太遠，否則有可能使極小化發(fā)散或

29、收斂到非極小點。使極小化發(fā)散或收斂到非極小點。牛頓法的特點：牛頓法的特點：、二次插值法（拋物線法）、二次插值法（拋物線法）p p（1）二次插值多項式的構成及其極值點）二次插值多項式的構成及其極值點 yf x設 在單谷區(qū)間中的三點 123的相應函數(shù)值 123()fff，則可以做出如下的二次插值多項式： 2012Paaa21011211Paaaf22012222Paaaf23013233Paaaf多項式多項式 P的極值點可從極值的必要條件求得的極值點可從極值的必要條件求得1220ppPaa，即，即 12/2paa， n為了確定這個極值點，只需計算出系數(shù)為了確定這個極值點，只需計算出系數(shù)a a1 1

30、和和a a2 2 。其。其方法法是利用方法法是利用a a0 0、a a1 1、a a2 2的聯(lián)立方程組中相鄰兩個方程的聯(lián)立方程組中相鄰兩個方程消去消去a a0 0 ，從而得到關于，從而得到關于a a1 1、a a2 2的方程組的方程組n 解得解得n 所以所以113212pcac31131ffc21121223ffccf() *p ）如果區(qū)間長度 31足夠小，則由 31p便得出我們所要求的近似極小點 p2 2）如果不滿足，必須縮小區(qū)間）如果不滿足，必須縮小區(qū)間 13, ，根據(jù)區(qū)間消取法，根據(jù)區(qū)間消取法原理不斷縮小區(qū)間。原理不斷縮小區(qū)間。根據(jù)區(qū)間消去法原理，需要已知根據(jù)區(qū)間消去法原理，需要已知區(qū)間

31、內(nèi)兩點的函數(shù)值。其中點區(qū)間內(nèi)兩點的函數(shù)值。其中點2 2的函數(shù)值的函數(shù)值y y2 2=f=f（2 2）已知，另外已知，另外一點可取一點可取p p點并計算其函數(shù)值點并計算其函數(shù)值y yp p=f=f（p p）。）。當當 y y2 2yyp p 時取時取 1 1，p p 為縮短后的搜索區(qū)間（如右為縮短后的搜索區(qū)間（如右圖）。圖）。當當y y2 2yyp p 時取時取 2 2，3 3 為縮短后為縮短后的搜索區(qū)間。的搜索區(qū)間。 二二次次插插值值法法程程序序框框圖圖例1： 用二次插值法求 sin45f在上的極小點。 12144.524.54.705120355y1-0.756802 -0.977590y2

32、-0.977590-0.999974y3-0.958924 -0.958924p4.7051204.710594yp-0.999974-0.999998例例 2 2 用二次插值法求函數(shù)用二次插值法求函數(shù)f f( (x x)=3)=3x x3 3-4-4x x+2+2的極小點，的極小點，給定給定 x x0 0=0, =0, =0.2=0.2。2 2）用二次插值法逼近極小點）用二次插值法逼近極小點相鄰三點的函數(shù)值相鄰三點的函數(shù)值: : x x1 1=0, =0, x x2 2=1, =1, x x3 3=2; =2; f f1 1=2, =2, f f2 2=1, =1, f f3 3=18. =

33、18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxx fxxfx xp p* *0.555, f0.555, fp p=0.292=0.292解解 : : 1 1）確定初始區(qū)間）確定初始區(qū)間初始區(qū)間初始區(qū)間 a a, , b b=0, 2, =0, 2, 中間點中間點x x2 2=1, =1, f f( (x x2 2)=1)=1。由于由于f fp p f f2 2, , x xp p * * 0.2, |=1-0.555=0.4450.2, 應繼續(xù)迭代。應繼續(xù)迭代。在新區(qū)間，相鄰三點的函數(shù)值在新區(qū)間，相

34、鄰三點的函數(shù)值: : x x1 1=0, =0, x x2 2=0.555, =0.555, x x3 3=1; =1; f f1 1=2, =2, f f2 2=0.292, =0.292, f f3 3=1, =1, 代入代入x xp p* *公式計算得：公式計算得：x xp p* *0.607, f0.607, fp p=0.243=0.243 由于由于f fp p x x2 2, , 新區(qū)間新區(qū)間 a a, , b b=x x2 2, , b b=0.555, 1=0.555, 1| |x x2 2- -x xp p * * |=|0.555-0.607|=0.0520.2, |=|0

35、.555-0.607|=0.0520.2, 迭代終止。迭代終止。 x xp p* *0.607, f0.607, f* *=0.243=0.243例例 3 用二次插值法求用二次插值法求 的極值點。的極值點。初始搜索區(qū)間初始搜索區(qū)間 ， 。432( )46164f xxxxx13 1 6x x 0.05解：取解：取x x2 2點為區(qū)間點為區(qū)間 x x1 1, , x x3 3 的中點的中點 ， 計算計算x x1 1, , x x2 2, , x x3 3 3 3點處的函數(shù)值點處的函數(shù)值f f1 1=19=19，f f2 2=-96.9375=-96.9375，f f3 3=124=124?？梢姾瘮?shù)值滿足?？梢姾瘮?shù)值滿足“高低高高低高”形態(tài)。形態(tài)。2130.5 ()2.5xxx以以x x1 1, , x x2 2, , x x3 3為插值點構造二次曲線。為插值點構造二次曲線。求第一次近似的二次曲線求第一次近似的二次曲線p p(