最優(yōu)化一維搜索方法課件

第三章一維搜索方法3.3一維搜索的試探法3.1搜索區(qū)間的確定3.2區(qū)間消去法原理3.4一維搜索的插值法第三章一維搜索方法3.3一維搜索的試探法3.1搜索區(qū)1求解一維目標函數(shù)f(X)最優(yōu)解的過程，稱為一維優(yōu)化(一維搜索)，所使用的方法稱為一維優(yōu)化方法。由前數(shù)值迭代法可知，求某目標函數(shù)的最優(yōu)值時，迭代過程每一步的格式都是從某一定點X(k)

出發(fā)，沿著某一使目標函數(shù)下降的規(guī)定方向S(k)搜索，以找出此方向的極小點X(k+1)

。這一過程是各種最優(yōu)化方法的一種基本過程。一維搜索方法一般分兩步進行：

■

首先確定一個包含函數(shù)極小點的初始區(qū)間，即確定

函數(shù)的搜索區(qū)間，該區(qū)間必須是單峰區(qū)間；

■然后采用縮小區(qū)間或插值逼近的方法得到最優(yōu)步長，

最終求出該搜索區(qū)間內的一維極小點?！?.1搜索區(qū)間的確定求解一維目標函數(shù)f(X)最優(yōu)解的過程，稱為一維優(yōu)化(一維2根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰區(qū)間，就是在該區(qū)間內的函數(shù)變化只有一個峰值，即函數(shù)的極小值。

即在單峰區(qū)間內的極小值點X*的左側：函數(shù)呈下降趨勢，而在單峰區(qū)間內的極小值點X*

的右側：函數(shù)呈上升趨勢。也就是說，單峰區(qū)間的函數(shù)值呈“高-低-高”的變化特征?！?.1搜索區(qū)間的確定x*abx0f(x)根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰3

目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法是進退試算法。

進退試算法的基本思想為：

1)按照一定的規(guī)律給出若干試算點，

2)依次比較各試算點的函數(shù)值的大小，

3)直到找到相鄰三點函數(shù)值按“高-低-高”

變化的單峰區(qū)間為止§3.1搜索區(qū)間的確定目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法是進退試算法。4

進退試算法的運算步驟如下：(2)將α0及α0+h代入目標函數(shù)f(x)進行計算并比較大小(1)給定初始點α0和初始步長h§3.1搜索區(qū)間的確定f(x)x0aba0f(a0)a0+hf(a0+h)a0+3hf(a0+3h)f(x)x0aba0-hf(a0-h)a0f(a0)a0+hf(a0+h)進退試算法的運算步驟如下：(2)將α0及α0+h代入目標5若f(α0+h)≤f(α0+3h)，則所計算的相鄰三點

的函數(shù)值已具“高-低-高”特征，這時可確定搜索區(qū)間

(3)若f(α0)>f(α0+h)，則表明極小點在試算點

的右側，需做前進試算。

否則，將步長再加倍，并重復上述運算?！?.1搜索區(qū)間的確定在做前進運算時，為加速計算，可將步長h

增加2倍，并取計算新點為α0+h+2h=α0+3h若f(α0+h)≤f(α0+3h)，則所計算的相鄰三6

(4)若f(α0)<f(α0+h)，則表明極小點在試算點

的左側，需做后退試算。在做后退運算時，應將步長變?yōu)?h

，并從

點出α0發(fā)，得到后退點為α0-h

若f(α0-h)>f(α0)，則搜索區(qū)間可取為否則，將步長加倍，繼續(xù)后退，重復上述步驟，直到滿足單峰區(qū)間條件為止?！?.1搜索區(qū)間的確定(4)若f(α0)<f(α0+h)，則表明極小點在7f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，找到極小點的數(shù)值近似解。假定在搜索區(qū)間內[a,b]任取兩點a1、b1,且a1<b1f1＝f（a1），

f2＝f（b1）一、基本思想a1a1

a1

b1baabb

b1b1§3.2區(qū)間消去法原理f1>f2

f1<f2

f1=f2

f(x)

f(x)

f(x)

f(b1)f(a1)f(b1)f(a1)f(b1)af(a18(1)f1<f2,新區(qū)間為[a,b1](2)f1>f2,新區(qū)間為[a1,b](3)f1=f2,新區(qū)間為[a1,b1]對于上述縮短后的新區(qū)間，可在其內再取一個新點，然后將此點和該區(qū)間內剩下的那一點進行函數(shù)值大小的比較，以再次按照上述方法，進一步縮短區(qū)間，這樣不斷進行下去，直到所保留的區(qū)間縮小到給定的誤差范圍內，而得到近似最優(yōu)解。新區(qū)間為[a1,b]f(b1)af(a1)

a1

b1bf(b1)f(a1)a1ab

b1f(b1)f(a1)a1bab1(1)f1<f2,新區(qū)間為[a,b1]對于上述縮短后的新9一、適用范圍

適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單峰”外不作其他要求，甚至可以不連續(xù)。適應面相當廣。基本原理為區(qū)間消去法§3.3黃金分割法黃金分割法插入兩點：f(a2)af(a1)

a1

a2bf(a2)af(a1)

a1b

a2一、適用范圍§3.3黃金分割法黃金分割法插入兩點：f(a10黃金分割法還要求在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布?！?.3黃金分割法λα2α1λ2ab11-λα1α3λ(1-λ)α2λa黃金分割法還要求在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三11黃金分割法程序框圖開始輸入a,

b,

,

YN結束YNaf(x2)f(x1)b

x1

x2b

x2f(x2)

x1黃金分割法程序框圖開始輸入a,b,,12例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，

初始點x0=0,步長h=1,精度

ε=0.2。解：1）確定初始區(qū)間

x1=x0=0,f1=f(x1)=2

x2=x0+h=0+1=1

f2=f(x2)=1

由于f1>f2,應繼續(xù)向前探測

x3=

x0+2h=0+2=2

f3=f(x3)=18由于f2<f3,可知初始區(qū)間已經(jīng)找到，即

[a,b]=[x1,x3]=[0,2]§3.3黃金分割法f(x1)=2x1=0f(x2)=1x2=1f(x3)=18x3=2ab例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極132）用黃金分割法縮小區(qū)間

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

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

由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0,1.236]由于b-a＝1.236>0.2,應繼續(xù)縮小區(qū)間§3.3黃金分割法f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abb2）用黃金分割法縮小區(qū)間§3.3黃金分割法f(x1)=014§3.3黃金分割法第二次縮小區(qū)間：令x2=x1=0.764,

f2=f1=0.282

x1=0+0.382×(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]由于b-a=1.236-0.472=0.764>0.2,應繼續(xù)縮小區(qū)間f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abbx2f(x2)x1f(x1)a§3.3黃金分割法第二次縮小區(qū)間：f(x1)=0.28215

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

f1=f2=0.282

x2=0.472+0.618×(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]由于b-a=0.944-0.472=0.472>0.2,應繼續(xù)縮小區(qū)間?！?.3黃金分割法

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

f2=f1=0.282

x1=0.472+0.382×(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]由于b-a=0.764-0.472=0.292>0.2,應繼續(xù)縮小區(qū)間。第三次縮小區(qū)間：§3.3黃金分割法第四次縮小區(qū)間：16第五次縮小區(qū)間：令x2=x1=0.652,

f2=f1=0.223

x1=0.472+0.382×(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=0.18<0.2,停止迭代。黃金分割法求的的極小點與極小值：

x=0.5×(0.584+0.764)=0.674,f(x)=0.222§3.3黃金分割法求導運算求的極小點與極小值：

x=0.667,f(x)=0.222第五次縮小區(qū)間：黃金分割法求的的極小點與極小值：§3.317一、牛頓法§3.4插值方法利用一點的函數(shù)值、一階導數(shù)以及二階導數(shù)構造二次多項式。用構造的二次多項式的極小點作為原函數(shù)極小點的近似。x*xf(x)

x2φ0(x)

x0f(x)

φ1(x)

x1一、牛頓法§3.4插值方法利用一點的函數(shù)值、一階導數(shù)以及18一、牛頓法設f(x)為一個連續(xù)可微的函數(shù)，則在點x0附近進行泰勒展開并保留到二次項：用二次函數(shù)φ(x)的極小點x1作為f(x)極小點的一個近似點。根據(jù)極值必要條件:§3.4插值方法xf(x)

x1x2φ0(x)

x*f(x)

φ1(x)

x0一、牛頓法設f(x)為一個連續(xù)可微的函數(shù)，則在點x0附近進行19即依此類推可得牛頓迭代公式：一、牛頓法§3.4插值方法x2x1x0x*f(x)

f(x)

φ0(x)

φ1(x)

即依此類推可得牛頓迭代公式：一、牛頓法§3.4插值方法x20在x0處用一拋物線φ(x)代替曲線f(x)，相當于用一斜直線φ

′(x)代替曲線f

′(x)。這樣各個近似點是通過對作f

′(x)切線求得與軸的交點找到的，所以有時牛頓法又稱作切線法。x2x1x0x*f(x)

f(x)

φ0(x)

φ1(x)

f′

(x)

f′

(x)

x*x0φ′1(x)

x2x1在x0處用一拋物線φ(x)代替曲線f(x)，相當于用一斜直21牛頓法程序框圖

開始計算，YN給定初始點，誤差,令k=0計算，結束牛頓法程序框圖開始計算22數(shù)值\k

0

1

2

3

435.1667

4.33474

4.03960

4.00066-52

153.35183

32.30199

3.38299

0.0055124

184.33332

109.44586

86.86992

84.04720

5.1667

4.33474

4.03960

4.00066

4.00059

2.1667

0.83196

0.29514

0.03894

0.00007例3-2給定f(x)=x4-4x3-6x2-16x+4，試用牛頓法計算其極小點。給定初始點x0=3，ε=0.001，計算公式：函數(shù)的二階導數(shù)：解：函數(shù)的一階導數(shù)：§3.4插值方法數(shù)值\k0123

優(yōu)點：1）收斂速度快。

缺點：1）要計算函數(shù)的一階和二階導數(shù)，增加每次迭代的工作量。

2）數(shù)值微分計算函數(shù)二階導數(shù)，舍入誤差將嚴重影響牛頓法的收斂速度，f

'(x)的值越小問題越嚴重。

3）牛頓法要求初始點離極小點不太遠，否則可能使極小化序列發(fā)散或收斂到非極小點。一、牛頓法§3.4插值方法優(yōu)點：1）收斂速度快。一、牛頓法§3.4插值方法24二、二次插值法（拋物線法）

在給定的單峰區(qū)間中，利用目標函數(shù)上的三個點來構造一個二次插值函數(shù)，以近似地表達原目標函數(shù)f(a)，并求這個插值函數(shù)的極小點近似作為原目標函數(shù)的極小點。

§3.4插值方法f(x)xf1x1f2x2f3x3xpx*二、二次插值法（拋物線法）§3.4插值方法f(x)x25y0xxp1x1x2xpx3xy0x*y1y2ypy3x1x2xpx*y1y2ypyp1y0xxp1x1x2xpx3xy0x*y1y2ypy3x1x26xpxp1x1x2xpx3xy0x*y1y2ypy3x2x3xy0x*y2ypy3yp1xpxp1x1x2xpx3xy0x*y1y2ypy3x2x327構造的二次插值函數(shù)曲線通過原函數(shù)上的三個點:

解得系數(shù)可求得二、二次插值法（拋物線法）§3.4插值方法構造的二次插值函數(shù)曲線通過原函數(shù)上的三個點:解得系數(shù)可28二次插值法程序框圖開始計算，YN給定,縮短區(qū)間名稱置換結束二次插值法程序框圖開始計算29x1x2xpx3xy0x*y1y2ypy3x1x2xpx3x0x*yy1y2ypy3x1x2xpx3xy0x*y1y2ypy3x1x2xpx3x30二次插值法程序編制換名方法(1)1)

x2<xp

y2≥yp

y2<ypy2→y1yp→y2xpx1x2x3xy2yp→y3xpx1x2x3xx1x2x3二次插值法程序編制換名方法(1)1)x2<xpy2≥y31二次插值法程序編制換名方法(2)2)

x2>xp

y2≥ypyp→y2y2→y3xpx1x2x3xx3x2

y2<ypyp→y1y2xpx1x2x3xx1二次插值法程序編制換名方法(2)2)x2>xpy2≥32（1）二次插值法只要求f(x)連續(xù)，不要求其一階可微；（2）收斂速度比黃金分割法快，但可靠性不如黃金分割

法好，程序也較長。特點：§3.4插值方法二、二次插值法（拋物線法）（1）二次插值法只要求f(x)連續(xù)，不要求其一階可微；特33例3-3用二次插值法求函數(shù)f(X)=3x3-4x+2的極小點，

給定x0=0,ε=0.2。解1）確定初始區(qū)間:[a,b]=[0,2]2）用二次插值法逼近極小點相鄰三點的函數(shù)值:x1=0,x2=1,x3=2;f1=2,

f2=1,f3=18.代入公式：xp＝0.555,fp=0.292例3-3用二次插值法求函數(shù)f(X)=3x3-4x+2的極34在新區(qū)間，相鄰三點的函數(shù)值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.

xp=0.607,fp=0.243

由于fp<f2,xp>x2,新區(qū)間[a,b]=[x2,b]=[0.555,1]|x2-xp|=|0.555-0.607|=0.052<0.2,迭代終止。

x*=0.607,f*=0.243由于fp<f2,xp<x2,新區(qū)間[a,b]=[a,x2]=[0,1]|x2-xp|=|1-0.555|=0.445>0.2,應繼續(xù)迭代。yp→y2y2→y3xpx3x2x1x2x3xx2x3xp在新區(qū)間，相鄰三點的函數(shù)值:x1=0,x2=0.35第三章一維搜索方法3.3一維搜索的試探法3.1搜索區(qū)間的確定3.2區(qū)間消去法原理3.4一維搜索的插值法第三章一維搜索方法3.3一維搜索的試探法3.1搜索區(qū)36求解一維目標函數(shù)f(X)最優(yōu)解的過程，稱為一維優(yōu)化(一維搜索)，所使用的方法稱為一維優(yōu)化方法。由前數(shù)值迭代法可知，求某目標函數(shù)的最優(yōu)值時，迭代過程每一步的格式都是從某一定點X(k)

出發(fā)，沿著某一使目標函數(shù)下降的規(guī)定方向S(k)搜索，以找出此方向的極小點X(k+1)

。這一過程是各種最優(yōu)化方法的一種基本過程。一維搜索方法一般分兩步進行：

■

首先確定一個包含函數(shù)極小點的初始區(qū)間，即確定

函數(shù)的搜索區(qū)間，該區(qū)間必須是單峰區(qū)間；

■然后采用縮小區(qū)間或插值逼近的方法得到最優(yōu)步長，

最終求出該搜索區(qū)間內的一維極小點?！?.1搜索區(qū)間的確定求解一維目標函數(shù)f(X)最優(yōu)解的過程，稱為一維優(yōu)化(一維37根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰區(qū)間，就是在該區(qū)間內的函數(shù)變化只有一個峰值，即函數(shù)的極小值。

即在單峰區(qū)間內的極小值點X*的左側：函數(shù)呈下降趨勢，而在單峰區(qū)間內的極小值點X*

的右側：函數(shù)呈上升趨勢。也就是說，單峰區(qū)間的函數(shù)值呈“高-低-高”的變化特征?！?.1搜索區(qū)間的確定x*abx0f(x)根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰38

目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法是進退試算法。

進退試算法的基本思想為：

1)按照一定的規(guī)律給出若干試算點，

2)依次比較各試算點的函數(shù)值的大小，

3)直到找到相鄰三點函數(shù)值按“高-低-高”

變化的單峰區(qū)間為止§3.1搜索區(qū)間的確定目前在一維優(yōu)化搜索中確定單峰區(qū)間常用的方法是進退試算法。39

進退試算法的運算步驟如下：(2)將α0及α0+h代入目標函數(shù)f(x)進行計算并比較大小(1)給定初始點α0和初始步長h§3.1搜索區(qū)間的確定f(x)x0aba0f(a0)a0+hf(a0+h)a0+3hf(a0+3h)f(x)x0aba0-hf(a0-h)a0f(a0)a0+hf(a0+h)進退試算法的運算步驟如下：(2)將α0及α0+h代入目標40若f(α0+h)≤f(α0+3h)，則所計算的相鄰三點

的函數(shù)值已具“高-低-高”特征，這時可確定搜索區(qū)間

(3)若f(α0)>f(α0+h)，則表明極小點在試算點

的右側，需做前進試算。

否則，將步長再加倍，并重復上述運算?！?.1搜索區(qū)間的確定在做前進運算時，為加速計算，可將步長h

增加2倍，并取計算新點為α0+h+2h=α0+3h若f(α0+h)≤f(α0+3h)，則所計算的相鄰三41

(4)若f(α0)<f(α0+h)，則表明極小點在試算點

的左側，需做后退試算。在做后退運算時，應將步長變?yōu)?h

，并從

點出α0發(fā)，得到后退點為α0-h

若f(α0-h)>f(α0)，則搜索區(qū)間可取為否則，將步長加倍，繼續(xù)后退，重復上述步驟，直到滿足單峰區(qū)間條件為止。§3.1搜索區(qū)間的確定(4)若f(α0)<f(α0+h)，則表明極小點在42f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，找到極小點的數(shù)值近似解。假定在搜索區(qū)間內[a,b]任取兩點a1、b1,且a1<b1f1＝f（a1），

f2＝f（b1）一、基本思想a1a1

a1

b1baabb

b1b1§3.2區(qū)間消去法原理f1>f2

f1<f2

f1=f2

f(x)

f(x)

f(x)

f(b1)f(a1)f(b1)f(a1)f(b1)af(a143(1)f1<f2,新區(qū)間為[a,b1](2)f1>f2,新區(qū)間為[a1,b](3)f1=f2,新區(qū)間為[a1,b1]對于上述縮短后的新區(qū)間，可在其內再取一個新點，然后將此點和該區(qū)間內剩下的那一點進行函數(shù)值大小的比較，以再次按照上述方法，進一步縮短區(qū)間，這樣不斷進行下去，直到所保留的區(qū)間縮小到給定的誤差范圍內，而得到近似最優(yōu)解。新區(qū)間為[a1,b]f(b1)af(a1)

a1

b1bf(b1)f(a1)a1ab

b1f(b1)f(a1)a1bab1(1)f1<f2,新區(qū)間為[a,b1]對于上述縮短后的新44一、適用范圍

適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單峰”外不作其他要求，甚至可以不連續(xù)。適應面相當廣?；驹頌閰^(qū)間消去法§3.3黃金分割法黃金分割法插入兩點：f(a2)af(a1)

a1

a2bf(a2)af(a1)

a1b

a2一、適用范圍§3.3黃金分割法黃金分割法插入兩點：f(a45黃金分割法還要求在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布?！?.3黃金分割法λα2α1λ2ab11-λα1α3λ(1-λ)α2λa黃金分割法還要求在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三46黃金分割法程序框圖開始輸入a,

b,

,

YN結束YNaf(x2)f(x1)b

x1

x2b

x2f(x2)

x1黃金分割法程序框圖開始輸入a,b,,47例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，

初始點x0=0,步長h=1,精度

ε=0.2。解：1）確定初始區(qū)間

x1=x0=0,f1=f(x1)=2

x2=x0+h=0+1=1

f2=f(x2)=1

由于f1>f2,應繼續(xù)向前探測

x3=

x0+2h=0+2=2

f3=f(x3)=18由于f2<f3,可知初始區(qū)間已經(jīng)找到，即

[a,b]=[x1,x3]=[0,2]§3.3黃金分割法f(x1)=2x1=0f(x2)=1x2=1f(x3)=18x3=2ab例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極482）用黃金分割法縮小區(qū)間

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

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

由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0,1.236]由于b-a＝1.236>0.2,應繼續(xù)縮小區(qū)間§3.3黃金分割法f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abb2）用黃金分割法縮小區(qū)間§3.3黃金分割法f(x1)=049§3.3黃金分割法第二次縮小區(qū)間：令x2=x1=0.764,

f2=f1=0.282

x1=0+0.382×(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]由于b-a=1.236-0.472=0.764>0.2,應繼續(xù)縮小區(qū)間f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abbx2f(x2)x1f(x1)a§3.3黃金分割法第二次縮小區(qū)間：f(x1)=0.28250

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

f1=f2=0.282

x2=0.472+0.618×(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]由于b-a=0.944-0.472=0.472>0.2,應繼續(xù)縮小區(qū)間。§3.3黃金分割法

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

f2=f1=0.282

x1=0.472+0.382×(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]由于b-a=0.764-0.472=0.292>0.2,應繼續(xù)縮小區(qū)間。第三次縮小區(qū)間：§3.3黃金分割法第四次縮小區(qū)間：51第五次縮小區(qū)間：令x2=x1=0.652,

f2=f1=0.223

x1=0.472+0.382×(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=0.18<0.2,停止迭代。黃金分割法求的的極小點與極小值：

x=0.5×(0.584+0.764)=0.674,f(x)=0.222§3.3黃金分割法求導運算求的極小點與極小值：

x=0.667,f(x)=0.222第五次縮小區(qū)間：黃金分割法求的的極小點與極小值：§3.352一、牛頓法§3.4插值方法利用一點的函數(shù)值、一階導數(shù)以及二階導數(shù)構造二次多項式。用構造的二次多項式的極小點作為原函數(shù)極小點的近似。x*xf(x)

x2φ0(x)

x0f(x)

φ1(x)

x1一、牛頓法§3.4插值方法利用一點的函數(shù)值、一階導數(shù)以及53一、牛頓法設f(x)為一個連續(xù)可微的函數(shù)，則在點x0附近進行泰勒展開并保留到二次項：用二次函數(shù)φ(x)的極小點x1作為f(x)極小點的一個近似點。根據(jù)極值必要條件:§3.4插值方法xf(x)

x1x2φ0(x)

x*f(x)

φ1(x)

x0一、牛頓法設f(x)為一個連續(xù)可微的函數(shù)，則在點x0附近進行54即依此類推可得牛頓迭代公式：一、牛頓法§3.4插值方法x2x1x0x*f(x)

f(x)

φ0(x)

φ1(x)

即依此類推可得牛頓迭代公式：一、牛頓法§3.4插值方法x55在x0處用一拋物線φ(x)代替曲線f(x)，相當于用一斜直線φ

′(x)代替曲線f

′(x)。這樣各個近似點是通過對作f

′(x)切線求得與軸的交點找到的，所以有時牛頓法又稱作切線法。x2x1x0x*f(x)

f(x)

φ0(x)

φ1(x)

f′

(x)

f′

(x)

x*x0φ′1(x)

x2x1在x0處用一拋物線φ(x)代替曲線f(x)，相當于用一斜直56牛頓法程序框圖

開始計算，YN給定初始點，誤差,令k=0計算，結束牛頓法程序框圖開始計算57數(shù)值\k

0

1

2

3

435.1667

4.33474

4.03960

4.00066-52

153.35183

32.30199

3.38299

0.0055124

184.33332

109.44586

86.86992

84.04720

5.1667

4.33474

4.03960

4.00066

4.00059

2.1667

0.83196

0.29514

0.03894

0.00007例3-2給定f(x)=x4-4x3-6x2-16x+4，試用牛頓法計算其極小點。給定初始點x0=3，ε=0.001，計算公式：函數(shù)的二階導數(shù)：解：函數(shù)的一階導數(shù)：§3.4插值方法數(shù)值\k0158

優(yōu)點：1）收斂速度快。

缺點：1）要計算函數(shù)的一階和二階導數(shù)，增加每次迭代的工作量。

2）數(shù)值微分計算函數(shù)二階導數(shù)，舍入誤差將嚴重影響牛頓法的收斂速度，f

'(x)的值越小問題越嚴重。

3）牛頓法要求初始點離極小點不太遠，否則可能使極小化序列發(fā)散或收斂到非極小點。一、牛頓法§3.4插值方法優(yōu)點：1）收斂速度快。一、牛頓法§3.4插值方法59二、二次插值法（拋物線法）

在給定的單峰區(qū)間中，利用目標函數(shù)上的三個點來構造一個二次插值函數(shù)，以近似地表達原目標函數(shù)f(a)，并求這個插值函數(shù)的極小點近似作為原目標函數(shù)的極小點。

§3.4插值方法f(x)xf1x1f2x2f3x3xpx*二、二次插值法（拋物線法）§3.4插值方法f(x)x60y0xxp1x1x2xpx3x