第三章一維搜索線性搜索演示文稿

第三章一維搜索線性搜索演示文稿目前一頁\總數(shù)六十五頁\編于六點(diǎn)優(yōu)選第三章一維搜索線性搜索目前二頁\總數(shù)六十五頁\編于六點(diǎn)3第3章一維搜索方法3.1概述3.1.1一維問題是多維問題的基礎(chǔ)求目標(biāo)函數(shù)f(X)的極小點(diǎn)，從理論上說需要求解方程：其中那么如何來求f(X)的極小點(diǎn)呢？基本思想:這種方法是逐次迭代的方法，在電子計算機(jī)上很容易實(shí)現(xiàn)，因此它在優(yōu)化設(shè)計中被廣泛地采用。目前三頁\總數(shù)六十五頁\編于六點(diǎn)4這個過程稱為一維搜索過程。如：則當(dāng)Sk方向上的任何一點(diǎn)可以表示為其中α是步長因子，為實(shí)系數(shù)，此時Sk方向上任何一點(diǎn)的目標(biāo)函數(shù)值為，它是參數(shù)α的一元函數(shù)。那么在沿Sk方向求的極小點(diǎn)，這就是求一元函數(shù)

的極小問題，它可表示為：目前四頁\總數(shù)六十五頁\編于六點(diǎn)一維搜索示意圖目前五頁\總數(shù)六十五頁\編于六點(diǎn)

求多元函數(shù)極值點(diǎn)，需要進(jìn)行一系列的一維搜索?？梢娨痪S搜索是優(yōu)化搜索方法的基礎(chǔ)。求解一元函數(shù)的極小點(diǎn)，可采用解析解法，即利用一元函數(shù)的極值條件求在用函數(shù)的導(dǎo)數(shù)求時，所用的函數(shù)是僅以步長因子為變量的一元函數(shù)，而不是以設(shè)計點(diǎn)x為變量的多元函數(shù)。3.1.2的確定方法目前六頁\總數(shù)六十五頁\編于六點(diǎn)為了直接利用的函數(shù)式求解最佳步長因子。把或它的簡寫形式進(jìn)行泰勒展開，取到二階項(xiàng)，即將上式對進(jìn)行微分并令其等于零，給出極值點(diǎn)應(yīng)滿足的條件從而求得目前七頁\總數(shù)六十五頁\編于六點(diǎn)這里是直接利用函數(shù)而不需要把它化成步長因子。的函數(shù)。不過，此時需要計算點(diǎn)處梯度和海賽矩陣H。解析解法的缺點(diǎn)——需要進(jìn)行求導(dǎo)計算。對于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難或無法求導(dǎo)的情況，使用解析法將是非常不便的。因此，在優(yōu)化設(shè)計中，求解最佳步長因子主要采用數(shù)值解法，利用計算機(jī)通過反復(fù)迭代計算求得最佳步長因子的近似值。數(shù)值解法的基本思路是：首先確定所在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得的數(shù)值近似解。目前八頁\總數(shù)六十五頁\編于六點(diǎn)解析法:①f(X(k)+αS(k))沿S(k)

方向在x(k)

點(diǎn)泰勒展開；②取二次近似：

對α求導(dǎo)，令其為零。

④求得最優(yōu)步長目前九頁\總數(shù)六十五頁\編于六點(diǎn)數(shù)值解法基本思路：

解析解法對于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難等情況難以實(shí)現(xiàn)。在實(shí)際優(yōu)化設(shè)計中，數(shù)值解法的應(yīng)用更為有效，且適合計算機(jī)的運(yùn)算特點(diǎn)。

一維搜索也稱直線搜索。這種方法不僅對于解決一維最優(yōu)化問題具有實(shí)際意義，而且也是求解多維最優(yōu)化問題的重要支柱。一維搜索一般分為兩大步驟：(1)確定初始搜索區(qū)間[a，b]，該區(qū)間應(yīng)是包括一維函數(shù)極小點(diǎn)在內(nèi)的單谷區(qū)間。(2)在單谷區(qū)間[a,b]內(nèi)通過縮小區(qū)間尋找極小點(diǎn)。先確定在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間所，從而獲得的數(shù)值近似解。目前十頁\總數(shù)六十五頁\編于六點(diǎn)1、確定搜索區(qū)間的外推法在給定區(qū)間內(nèi)僅有一個谷值（或有唯一的極小點(diǎn)）的函數(shù)稱為單谷函數(shù)，其區(qū)間稱為單谷區(qū)間。函數(shù)值：“大—小—大”圖形：“高—低—高”單谷區(qū)間中一定能求得一個極小點(diǎn)。3.2確定初始區(qū)間目前十一頁\總數(shù)六十五頁\編于六點(diǎn)從開始，以初始步長向前試探。如果函數(shù)值上升，則步長變號，即改變試探方向。如果函數(shù)值下降，則維持原來的試探方向，并將步長加倍。區(qū)間的始點(diǎn)、中間點(diǎn)依次沿試探方向移動一步。此過程一直進(jìn)行到函數(shù)值再次上升時為止，即可找到搜索區(qū)間的終點(diǎn)。最后得到的三點(diǎn)即為搜索區(qū)間的始點(diǎn)、中間三點(diǎn)和終點(diǎn)，形成函數(shù)值的“高－低－高”趨勢。單谷區(qū)間目前十二頁\總數(shù)六十五頁\編于六點(diǎn)f(x)0α1α3α0f(x)α3α1說明：單谷區(qū)間內(nèi)，函數(shù)可以有不可微點(diǎn)，也可以是不連續(xù)函數(shù)；目前十三頁\總數(shù)六十五頁\編于六點(diǎn)外推方法基本思想：對任選一個初始點(diǎn)及初始步長，通過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為“高—低—高”形態(tài)。步驟：

1）選定初始點(diǎn)a1，初始步長h=h0，計算y1=f(a1)和y2=f(a1+h)2）比較y1和y2；a）如果y1>y2，向右前進(jìn)，加大步長h=2h0，轉(zhuǎn)（3）向前；b）如果y1<y2，向左后退，h=-2h0，將a1和a2,y1和y2的值互換。轉(zhuǎn)（3）向后探測；c）如果y1=y2，極小點(diǎn)在a1和a1+h之間。3）產(chǎn)生新的探測點(diǎn)a3=a2+h，y3=f(a3)；目前十四頁\總數(shù)六十五頁\編于六點(diǎn)4）比較函數(shù)值y2和y3：a）如果y2>y3

，加大步長h=2h，a1=a2,a2=a3,轉(zhuǎn)（3）繼續(xù)探測；b）如果y2<y3，則初始區(qū)間得到：a=min[a1,a3],b=max[a1,a3]，函數(shù)最小值所在區(qū)間為[a,b]。目前十五頁\總數(shù)六十五頁\編于六點(diǎn)右圖表示沿的正向試探。每走一步都將區(qū)間的始點(diǎn)、中間點(diǎn)沿試探方向移動一步（進(jìn)行換名）。經(jīng)過三步最后確定搜索間，并且得到區(qū)間始點(diǎn)、中間點(diǎn)和終點(diǎn)所對應(yīng)的函數(shù)值。y1y3→y2y2→y1a3→a2a2→a1a1Oaa3h0h02h0圖3-2正向搜索的外推法目前十六頁\總數(shù)六十五頁\編于六點(diǎn)右圖所表示的情況是：開始是沿的正方向試探，但由于函數(shù)值上升而改變了試探方向，最后得到始點(diǎn)，中間點(diǎn)和終點(diǎn)

及它們的對應(yīng)函數(shù)值

從而形成單谷區(qū)間為一維搜索區(qū)間。y1←y2a2←a3a1←a2←a1Oaa32h0h0h0y3y1←y2←y1y2←y3a1←a2圖3-3反向搜索的外推法目前十七頁\總數(shù)六十五頁\編于六點(diǎn)khx1x2x30h0初始點(diǎn)初始點(diǎn)+h012h0初始點(diǎn)初始點(diǎn)+h0初始點(diǎn)+3h024h0初始點(diǎn)+h0初始點(diǎn)+3h0初始點(diǎn)+7h038h0初始點(diǎn)+3h0初始點(diǎn)+7h0初始點(diǎn)+15h0前進(jìn)搜索步驟表目前十八頁\總數(shù)六十五頁\編于六點(diǎn)khx1x2x30h0初始點(diǎn)初始點(diǎn)+h012h0初始點(diǎn)+h0初始點(diǎn)初始點(diǎn)-2h024h0初始點(diǎn)初始點(diǎn)-2h0初始點(diǎn)-6h038h0初始點(diǎn)-2h0初始點(diǎn)-6h0初始點(diǎn)-14h0后退搜索步驟表目前十九頁\總數(shù)六十五頁\編于六點(diǎn)20khx1y1x2y2x3y310.10.2090.18.2030.36.68120.40.18.2030.36.6810.74.42930.80.36.6810.74.4291.57.125解：目前二十頁\總數(shù)六十五頁\編于六點(diǎn)21khx1y1x2y2x3y310.1-0.21.812.0961.914.3771.914.3771.812.0961.68.4882-0.41.812.0961.68.4881.24.5843-0.81.68.4881.24.5840.45.992

運(yùn)用進(jìn)退法確定出初始搜索區(qū)間[a,b]后，便可采用一維優(yōu)化方法來求出函數(shù)f(x)在區(qū)間內(nèi)的最優(yōu)點(diǎn)x*。目前二十一頁\總數(shù)六十五頁\編于六點(diǎn)222.程序框圖h=h0y1=f(x1)、x2=x1+h、y2=f(x2)給定x1、h0y1≥y2y2≥y3是h=2hx3=x2+h、y3=f(x3)結(jié)束否h=-hx3=x1y3=y1a=x1、b=x3是x1=x2y1=y2x2=x3y2=y3是a=x3、b=x1否h>0否初始進(jìn)退距前進(jìn)計算后退計算目前二十二頁\總數(shù)六十五頁\編于六點(diǎn)

，

搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點(diǎn)的數(shù)值近似解。

假定在搜索區(qū)間內(nèi)任取兩點(diǎn)，且

3.3區(qū)間消去方法目前二十三頁\總數(shù)六十五頁\編于六點(diǎn)(1)f（a1）<f（b1）,則極小點(diǎn)必在區(qū)間[a，b1]內(nèi);目前二十四頁\總數(shù)六十五頁\編于六點(diǎn)(1)f（a1）<f（b1）,則極小點(diǎn)必在區(qū)間[a，b1]內(nèi);(2)f（a1）>f（b1）,則極小點(diǎn)必在區(qū)間[α1，b]內(nèi);目前二十五頁\總數(shù)六十五頁\編于六點(diǎn)(1)f（a1）<f（b1）,則極小點(diǎn)必在區(qū)間[a，b1]內(nèi);(2)f（a1）>f（b1）,則極小點(diǎn)必在區(qū)間[α1，b]內(nèi);(3)f（a1）=f（b1）,則極小點(diǎn)必在區(qū)間[α1，b1]內(nèi)可以總結(jié)為兩種情況：若，則取[a,b1]為縮小后的搜索區(qū)間。若，則取[a1,b]為縮小后的搜索區(qū)間。目前二十六頁\總數(shù)六十五頁\編于六點(diǎn)試探法黃金分割法插值法二次插值法3一維搜索方法分類從前面的分析可知，每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點(diǎn)并計算其函數(shù)值。而插入點(diǎn)的位置，可以由不同的方法來確定。就形成了不同的一維搜索方法。一維搜索方法分類目前二十七頁\總數(shù)六十五頁\編于六點(diǎn)3.4黃金分割法（0.618法）黃金分割法黃金分割法的搜索過程目前二十八頁\總數(shù)六十五頁\編于六點(diǎn)概述在實(shí)際計算中，最常用的一維搜索試探方法是黃金分割法，又稱作0.618法。我們可以通過學(xué)習(xí)黃金分割法來了解一維搜索試探方法的基本思想。在搜索區(qū)間[a,b]內(nèi)適當(dāng)插入兩點(diǎn)α1、α2，并計算其函數(shù)值。α1、α2將區(qū)間分成三段。應(yīng)用函數(shù)的單谷性質(zhì)，通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。然后再在保留下來的區(qū)間上作同樣的處置，如此迭代下去，使搜索區(qū)間無限縮小，從而得到極小點(diǎn)的數(shù)值近似解。3.4黃金分割法（0.618法）目前二十九頁\總數(shù)六十五頁\編于六點(diǎn)黃金分割法是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法。適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。黃金分割法對插入點(diǎn)的要求：

1）要求插入點(diǎn)α1、α2的位置相對于區(qū)間[a,b]兩端點(diǎn)具有對稱性，即

其中為待定常數(shù)。1.黃金分割法目前三十頁\總數(shù)六十五頁\編于六點(diǎn)2）黃金分割法還要求在保留下來的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。即每次縮小所得的新區(qū)間長度與縮小前區(qū)間長度之比（即：區(qū)間收縮率）為定值。目前三十一頁\總數(shù)六十五頁\編于六點(diǎn)設(shè)原區(qū)間[a,b]長度為1如下圖所示，保留下來的區(qū)間[a,α2]長度為，區(qū)間縮短率為。為了保持相同的比例分布，新插入點(diǎn)α3應(yīng)在位置上，α1在原區(qū)間的位置應(yīng)相當(dāng)于在保留區(qū)間的位置。故有取方程正數(shù)解，得目前三十二頁\總數(shù)六十五頁\編于六點(diǎn)α1、α2將區(qū)間分成三段黃金分割法要求在保留下來的區(qū)間內(nèi)再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。兩內(nèi)分點(diǎn)值:結(jié)論：所謂黃金分割是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段長度的比值即。目前三十三頁\總數(shù)六十五頁\編于六點(diǎn)黃金分割法要求插入兩點(diǎn)：黃金分割法區(qū)間消去示意圖：3.4

黃金分割法（0.618法）目前三十四頁\總數(shù)六十五頁\編于六點(diǎn)2.黃金分割法的搜索過程（1）給出初始搜索區(qū)間及收斂精度，將賦以

。

（2）按坐標(biāo)點(diǎn)計算公式計算并計算其對應(yīng)的函數(shù)值3.4

黃金分割法（0.618法）目前三十五頁\總數(shù)六十五頁\編于六點(diǎn)（3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標(biāo)點(diǎn)計算公式，進(jìn)行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗(yàn)點(diǎn)及其函數(shù)值。3.4

黃金分割法（0.618法）目前三十六頁\總數(shù)六十五頁\編于六點(diǎn)（4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度，如果收斂條件滿足，則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。如果條件不滿足則轉(zhuǎn)向步驟5。（5）產(chǎn)生新的插入點(diǎn)：如N0=0，則?。?）如果條件滿足，則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。3.4

黃金分割法（0.618法）縮短區(qū)間的總次數(shù)（迭代次數(shù)）:目前三十七頁\總數(shù)六十五頁\編于六點(diǎn)黃金分割法程序框圖給定否否是是止也可采用迭代次數(shù)是否大于或等于k作終止準(zhǔn)則。目前三十八頁\總數(shù)六十五頁\編于六點(diǎn)39迭代序號aby1比較y20-30.0561.94450.115<7.6671-3-1.1110.0561.944-0.987<0.1152-3-1.832-1.1110.056-0.306>-0.9873-1.832-1.111-0.6650.056-0.987<-0.8884-1.832-1.386-1.111-0.665-0.851>-0.9875-1.386-1.111-0.940-0.665例3-3：用黃金分割法求的極小值，搜索區(qū)間是解：目前三十九頁\總數(shù)六十五頁\編于六點(diǎn)40解析解：目前四十頁\總數(shù)六十五頁\編于六點(diǎn)例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，給定x0=0,h=1,ε=0.2。解：1）確定初始區(qū)間a1=x0=0,f1=f(a1)=2a2=x0+h=0+1=1,f2=f(a2)=1由于f1>f2,應(yīng)加大步長繼續(xù)向前探測。a3=x0+2h=0+2=2,f3=f(a3)=18由于f2<f3,可知初始區(qū)間已經(jīng)找到，即[a,b]=[a1,a3]=[0,2]2）用黃金分割法縮小區(qū)間

第一次縮小區(qū)間：

a1=0+0.382×(2-0)=0.764,f1=0.282a2=0+0.618×(2-0)=1.236,f2=2.72

f1<f2,新區(qū)間[a,b]=[a,a2]=[0,1.236],b-a>0.2目前四十一頁\總數(shù)六十五頁\編于六點(diǎn)第二次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]因?yàn)閎-a=1.236-0.472=0.764>0.2,應(yīng)繼續(xù)縮小區(qū)間。

第三次縮小區(qū)間：令x1=x2=0.764,f1=f2=0.282

x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]因?yàn)閎-a=0.944-0.472=0.472>0.2,應(yīng)繼續(xù)縮小區(qū)間。目前四十二頁\總數(shù)六十五頁\編于六點(diǎn)

第四次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]因?yàn)閎-a=0.764-0.472=0.292>0.2,應(yīng)繼續(xù)縮小區(qū)間。第五次縮小區(qū)間：令x2=x1=0.652,f2=f1=0.223

x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因?yàn)閎-a=0.764-0.584=0.18<0.2,停止迭代。極小點(diǎn)與極小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222目前四十三頁\總數(shù)六十五頁\編于六點(diǎn)概述一維搜索問題是在某一確定區(qū)間內(nèi)尋求一元函數(shù)的極小點(diǎn)的位置，在某些情況下，如果沒有函數(shù)表達(dá)式，但能夠給出若干試驗(yàn)點(diǎn)處的函數(shù)值，就可以根據(jù)這些點(diǎn)處的函數(shù)值，利用插值法建立函數(shù)的某種近似表達(dá)式，進(jìn)而求出函數(shù)的極小點(diǎn)，并用它作為原來函數(shù)極小點(diǎn)的近似值。這種方法稱作插值法，又稱作函數(shù)逼近法。3.5

一維搜索的二次插值法目前四十四頁\總數(shù)六十五頁\編于六點(diǎn)試探法（如黃金分割法）與插值法的比較：不同點(diǎn)：表現(xiàn)在試驗(yàn)點(diǎn)（插入點(diǎn)）位置的確定方法不同。目前四十五頁\總數(shù)六十五頁\編于六點(diǎn)多項(xiàng)式是函數(shù)逼近的一種常用工具。在搜索區(qū)間內(nèi)可以利用若干試驗(yàn)點(diǎn)處的函數(shù)值來構(gòu)造低次多項(xiàng)式，用它作為函數(shù)的近似表達(dá)式，并用這個多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似。常用的插值多項(xiàng)式為二次多項(xiàng)式。牛頓法（切線法）利用一點(diǎn)的函數(shù)值、一階導(dǎo)數(shù)值和二階導(dǎo)數(shù)值來構(gòu)造二次函數(shù)。二次插值法（拋物線法）

利用三個點(diǎn)的函數(shù)值形成一個拋物線來構(gòu)造二次函數(shù)。目前四十六頁\總數(shù)六十五頁\編于六點(diǎn)

1、牛頓法（切線法）對于一維搜索函數(shù)，假定已經(jīng)給出極小點(diǎn)的一個較好的近似點(diǎn)，在點(diǎn)附近用一個二次函數(shù)來逼近函數(shù)

。然后以該二次函數(shù)的極小點(diǎn)作為極小點(diǎn)的一個新的近似點(diǎn)。根據(jù)極值必要條件：目前四十七頁\總數(shù)六十五頁\編于六點(diǎn)牛頓法的幾何解釋：在上圖中，在處用一拋物線代替曲線，相當(dāng)于用一斜線代替。這樣各個近似點(diǎn)是通過對作切線求得與軸的交點(diǎn)找到，故牛頓法又稱為切線法。目前四十八頁\總數(shù)六十五頁\編于六點(diǎn)牛頓法的計算步驟：1）給定初始點(diǎn)，控制誤差，并令2）計算3）求4）若，則求得近似解，停止計算，否則作5）。5）令轉(zhuǎn)2）。目前四十九頁\總數(shù)六十五頁\編于六點(diǎn)例題：

給定，試用牛頓法求其極小點(diǎn)。解：1）給定初始點(diǎn)，控制誤差2）3）4）目前五十頁\總數(shù)六十五頁\編于六點(diǎn)重復(fù)上邊的過程，進(jìn)行迭代，直到為止?？傻玫接嬎憬Y(jié)果如下表:表3-2牛頓法的搜索過程k01234值ak35.166674.334744.03964.00066f'(ak)-52153.3518332.301993.382990.00551f"(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059目前五十一頁\總數(shù)六十五頁\編于六點(diǎn)優(yōu)點(diǎn)：收斂速度快。缺點(diǎn)：每一點(diǎn)都要進(jìn)行二階導(dǎo)數(shù)，工作量大；當(dāng)用數(shù)值微分代替二階導(dǎo)數(shù)，由于舍入誤差會影響迭代速度；要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則有可能使極小化發(fā)散或收斂到非極小點(diǎn)。牛頓法的特點(diǎn)：目前五十二頁\總數(shù)六十五頁\編于六點(diǎn)２、二次插值法（拋物線法）基本思想：二次插值的基本思想是利用目標(biāo)函數(shù)在不同3點(diǎn)的函數(shù)值構(gòu)成一個與原函數(shù)f(x)相近似的二次多項(xiàng)式p(x)，以函數(shù)p(x)的極值點(diǎn)xp(即p′(x*p)=0的根)作為目標(biāo)函數(shù)f(x)的近似極值點(diǎn)。目前五十三頁\總數(shù)六十五頁\編于六點(diǎn)（1）二次插值多項(xiàng)式的構(gòu)成及其極值點(diǎn)設(shè)在單谷區(qū)間中的三點(diǎn)

的相應(yīng)函數(shù)值

，則可以做出如下的二次插值多項(xiàng)式：目前五十四頁\總數(shù)六十五頁\編于六點(diǎn)多項(xiàng)式的極值點(diǎn)可從極值的必要條件求得，即，

為了確定這個極值點(diǎn)，只需計算出系數(shù)a1和a2。其方法法是利用a0、a1、a2的聯(lián)立方程組中相鄰兩個方程消去a0，從而得到關(guān)于a1、a2的方程組目前五十五頁\總數(shù)六十五頁\編于六點(diǎn)解得所以目前五十六頁\總數(shù)六十五頁\編于六點(diǎn)如果令則這樣就得到了f(α)極小點(diǎn)α*的近似解αp。

１）如果區(qū)間長度

足夠小，則由

便得出我們所要求的近似極小點(diǎn)

目前五十七頁\總數(shù)六十五頁\編于六點(diǎn)2）如果不滿足，必須縮小區(qū)間

，根據(jù)區(qū)間消取法原理不斷縮小區(qū)間。根據(jù)區(qū)間消去法原理，需要已知區(qū)間內(nèi)兩點(diǎn)的函數(shù)值。其中點(diǎn)α2的函數(shù)值y2=f（α2）已知，另外一點(diǎn)可取αp點(diǎn)并計算其函數(shù)值yp=f（αp）。當(dāng)y2<yp時取[α1，αp]為縮短后的搜索區(qū)間（如右圖）。當(dāng)y2≥yp

時取[α2，α3]為縮短后的搜索區(qū)間。

目前五十八頁\總數(shù)六十五頁\編于六點(diǎn)二次插值法程序框圖目前五十九頁\總數(shù)六十五頁\編于六點(diǎn)例1：用二次插值法求

上的極小點(diǎn)。

12α144.5α24.54.705120α355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924αp4.7051204.710594yp-0.999974-0.999998二次插值法計算過程示例目前六十頁\總數(shù)六十五頁\編于六點(diǎn)例2用二次插值法求函數(shù)f(x)=3x