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

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

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

■

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

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

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

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

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

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

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

進(jìn)退試算法的基本思想為：

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

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

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

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

進(jìn)退試算法的運(yùn)算步驟如下：(2)將α0及α0+h代入目標(biāo)函數(shù)f(x)進(jìn)行計(jì)算并比較大小(1)給定初始點(diǎn)α0和初始步長(zhǎng)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)進(jìn)退試算法的運(yùn)算步驟如下：(2)將α0及α0+h代入目標(biāo)5若f(α0+h)≤f(α0+3h)，則所計(jì)算的相鄰三點(diǎn)

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

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

的右側(cè)，需做前進(jìn)試算。

否則，將步長(zhǎng)再加倍，并重復(fù)上述運(yùn)算?！?.1搜索區(qū)間的確定在做前進(jìn)運(yùn)算時(shí)，為加速計(jì)算，可將步長(zhǎng)h

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

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

的左側(cè)，需做后退試算。在做后退運(yùn)算時(shí)，應(yīng)將步長(zhǎng)變?yōu)?h

，并從

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

若f(α0-h)>f(α0)，則搜索區(qū)間可取為否則，將步長(zhǎng)加倍，繼續(xù)后退，重復(fù)上述步驟，直到滿足單峰區(qū)間條件為止。§3.1搜索區(qū)間的確定(4)若f(α0)<f(α0+h)，則表明極小點(diǎn)在7f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，找到極小點(diǎn)的數(shù)值近似解。假定在搜索區(qū)間內(nèi)[a,b]任取兩點(diǎn)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]對(duì)于上述縮短后的新區(qū)間，可在其內(nèi)再取一個(gè)新點(diǎn)，然后將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，以再次按照上述方法，進(jìn)一步縮短區(qū)間，這樣不斷進(jìn)行下去，直到所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到近似最優(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]對(duì)于上述縮短后的新9一、適用范圍

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

a1

a2bf(a2)af(a1)

a1b

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

b,

,

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

x1

x2b

x2f(x2)

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

初始點(diǎn)x0=0,步長(zhǎng)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,應(yīng)繼續(xù)向前探測(cè)

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,應(yīng)繼續(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,應(yīng)繼續(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,應(yīng)繼續(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,應(yīng)繼續(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]因?yàn)閎-a=0.764-0.584=0.18<0.2,停止迭代。黃金分割法求的的極小點(diǎn)與極小值：

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

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

x2φ0(x)

x0f(x)

φ1(x)

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

x1x2φ0(x)

x*f(x)

φ1(x)

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

f(x)

φ0(x)

φ1(x)

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

′(x)代替曲線f

′(x)。這樣各個(gè)近似點(diǎn)是通過(guò)對(duì)作f

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

f(x)

φ0(x)

φ1(x)

f′

(x)

f′

(x)

x*x0φ′1(x)

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

開始計(jì)算，YN給定初始點(diǎn)，誤差,令k=0計(jì)算，結(jié)束牛頓法程序框圖開始計(jì)算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，試用牛頓法計(jì)算其極小點(diǎn)。給定初始點(diǎn)x0=3，ε=0.001，計(jì)算公式：函數(shù)的二階導(dǎo)數(shù)：解：函數(shù)的一階導(dǎo)數(shù)：§3.4插值方法數(shù)值\k0123

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

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

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

'(x)的值越小問(wèn)題越嚴(yán)重。

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

在給定的單峰區(qū)間中，利用目標(biāo)函數(shù)上的三個(gè)點(diǎn)來(lái)構(gòu)造一個(gè)二次插值函數(shù)，以近似地表達(dá)原目標(biāo)函數(shù)f(a)，并求這個(gè)插值函數(shù)的極小點(diǎn)近似作為原目標(biāo)函數(shù)的極小點(diǎn)。

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

解得系數(shù)可求得二、二次插值法（拋物線法）§3.4插值方法構(gòu)造的二次插值函數(shù)曲線通過(guò)原函數(shù)上的三個(gè)點(diǎn):解得系數(shù)可28二次插值法程序框圖開始計(jì)算，YN給定,縮短區(qū)間名稱置換結(jié)束二次插值法程序框圖開始計(jì)算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）收斂速度比黃金分割法快，但可靠性不如黃金分割

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

給定x0=0,ε=0.2。解1）確定初始區(qū)間:[a,b]=[0,2]2）用二次插值法逼近極小點(diǎn)相鄰三點(diǎn)的函數(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ū)間，相鄰三點(diǎn)的函數(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,應(yīng)繼續(xù)迭代。yp→y2y2→y3xpx3x2x1x2x3xx2x3xp在新區(qū)間，相鄰三點(diǎn)的函數(shù)值:x1=0,x2=0.35第三章一維搜索方法3.3一維搜索的試探法3.1搜索區(qū)間的確定3.2區(qū)間消去法原理3.4一維搜索的插值法第三章一維搜索方法3.3一維搜索的試探法3.1搜索區(qū)36求解一維目標(biāo)函數(shù)f(X)最優(yōu)解的過(guò)程，稱為一維優(yōu)化(一維搜索)，所使用的方法稱為一維優(yōu)化方法。由前數(shù)值迭代法可知，求某目標(biāo)函數(shù)的最優(yōu)值時(shí)，迭代過(guò)程每一步的格式都是從某一定點(diǎn)X(k)

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

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

■

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

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

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

最終求出該搜索區(qū)間內(nèi)的一維極小點(diǎn)。§3.1搜索區(qū)間的確定求解一維目標(biāo)函數(shù)f(X)最優(yōu)解的過(guò)程，稱為一維優(yōu)化(一維37根據(jù)函數(shù)的變化情況，可將區(qū)間分為單峰區(qū)間和多峰區(qū)間。所謂單峰區(qū)間，就是在該區(qū)間內(nèi)的函數(shù)變化只有一個(gè)峰值，即函數(shù)的極小值。

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

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

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

進(jìn)退試算法的基本思想為：

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

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

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

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

進(jìn)退試算法的運(yùn)算步驟如下：(2)將α0及α0+h代入目標(biāo)函數(shù)f(x)進(jìn)行計(jì)算并比較大小(1)給定初始點(diǎn)α0和初始步長(zhǎng)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)進(jìn)退試算法的運(yùn)算步驟如下：(2)將α0及α0+h代入目標(biāo)40若f(α0+h)≤f(α0+3h)，則所計(jì)算的相鄰三點(diǎn)

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

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

的右側(cè)，需做前進(jìn)試算。

否則，將步長(zhǎng)再加倍，并重復(fù)上述運(yùn)算?！?.1搜索區(qū)間的確定在做前進(jìn)運(yùn)算時(shí)，為加速計(jì)算，可將步長(zhǎng)h

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

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

的左側(cè)，需做后退試算。在做后退運(yùn)算時(shí)，應(yīng)將步長(zhǎng)變?yōu)?h

，并從

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

若f(α0-h)>f(α0)，則搜索區(qū)間可取為否則，將步長(zhǎng)加倍，繼續(xù)后退，重復(fù)上述步驟，直到滿足單峰區(qū)間條件為止。§3.1搜索區(qū)間的確定(4)若f(α0)<f(α0+h)，則表明極小點(diǎn)在42f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，找到極小點(diǎn)的數(shù)值近似解。假定在搜索區(qū)間內(nèi)[a,b]任取兩點(diǎn)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]對(duì)于上述縮短后的新區(qū)間，可在其內(nèi)再取一個(gè)新點(diǎn)，然后將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，以再次按照上述方法，進(jìn)一步縮短區(qū)間，這樣不斷進(jìn)行下去，直到所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到近似最優(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]對(duì)于上述縮短后的新44一、適用范圍

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

a1

a2bf(a2)af(a1)

a1b

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

b,

,

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

x1

x2b

x2f(x2)

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

初始點(diǎn)x0=0,步長(zhǎng)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,應(yīng)繼續(xù)向前探測(cè)

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,應(yīng)繼續(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,應(yīng)繼續(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,應(yīng)繼續(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,應(yīng)繼續(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]因?yàn)閎-a=0.764-0.584=0.18<0.2,停止迭代。黃金分割法求的的極小點(diǎn)與極小值：

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

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

x2φ0(x)

x0f(x)

φ1(x)

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

x1x2φ0(x)

x*f(x)

φ1(x)

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

f(x)

φ0(x)

φ1(x)

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

′(x)代替曲線f

′(x)。這樣各個(gè)近似點(diǎn)是通過(guò)對(duì)作f

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

f(x)

φ0(x)

φ1(x)

f′

(x)

f′

(x)

x*x0φ′1(x)

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

開始計(jì)算，YN給定初始點(diǎn)，誤差,令k=0計(jì)算，結(jié)束牛頓法程序框圖開始計(jì)算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，試用牛頓法計(jì)算其極小點(diǎn)。給定初始點(diǎn)x0=3，ε=0.001，計(jì)算公式：函數(shù)的二階導(dǎo)數(shù)：解：函數(shù)的一階導(dǎo)數(shù)：§3.4插值方法數(shù)值\k0158

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

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

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

'(x)的值越小問(wèn)題越嚴(yán)重。

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

在給定的單峰區(qū)間中，利用目標(biāo)函數(shù)上的三個(gè)點(diǎn)來(lái)構(gòu)造一個(gè)二次插值函數(shù)，以近似地表達(dá)原目標(biāo)函數(shù)f(a)，并求這個(gè)插值函數(shù)的極小點(diǎn)近似作為原目標(biāo)函數(shù)的極小點(diǎn)。

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