第四節(jié)黃金分割_二次差值法

1、 第三章 一維搜索方法3.3 一維搜索的試探法3.1 搜索區(qū)間的確定3.2 區(qū)間消去法原理3.4 一維搜索的插值法f(b1)f(a1)f(b1)f(a1)f(b1)af(a1) 搜索區(qū)間確定搜索區(qū)間確定之后，采用區(qū)間消去法逐步之后，采用區(qū)間消去法逐步縮短搜索區(qū)間縮短搜索區(qū)間，找到極小點(diǎn)的數(shù)值近似解。找到極小點(diǎn)的數(shù)值近似解。 假定在搜索區(qū)間內(nèi)假定在搜索區(qū)間內(nèi)a,b 任取兩點(diǎn)任取兩點(diǎn)a1、b1,且且a1f2 f1f2 f1=f2 f(x) f(x) f(x) f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1(1)f1f2, 新區(qū)間為新區(qū)間為a1

2、,b;(3)如如f1=f2, 新區(qū)間為新區(qū)間為a1,b112ff1 , a b對于上述對于上述縮短后的新區(qū)間縮短后的新區(qū)間，可在其內(nèi)再取一個(gè)，可在其內(nèi)再取一個(gè)新點(diǎn)新點(diǎn)，然后，然后將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，將此點(diǎn)和該區(qū)間內(nèi)剩下的那一點(diǎn)進(jìn)行函數(shù)值大小的比較，以再次按照以再次按照上述方法上述方法，進(jìn)一步，進(jìn)一步縮短區(qū)間縮短區(qū)間，這樣不斷進(jìn)行下，這樣不斷進(jìn)行下去，直到去，直到所保留的區(qū)間所保留的區(qū)間縮小到給定的誤差范圍內(nèi)，而得到縮小到給定的誤差范圍內(nèi)，而得到近似最優(yōu)解近似最優(yōu)解。新區(qū)間為新區(qū)間為111222(1)(),( )(),()aabaff aaabaff aab a2a

3、1 a2a a1f(a1)f(a2)f(a2)f(a1)b一、適用范圍一、適用范圍 適用于適用于a,b區(qū)間上的任何區(qū)間上的任何單谷函數(shù)單谷函數(shù)求極小值問題。對求極小值問題。對函數(shù)除要求函數(shù)除要求“單谷單谷”外不作其他要求，甚至可以外不作其他要求，甚至可以不連不連續(xù)續(xù)。適應(yīng)面相當(dāng)廣?；驹頌椤＿m應(yīng)面相當(dāng)廣?；驹頌閰^(qū)間消去法區(qū)間消去法3.3 3.3 黃金分割法黃金分割法黃金分割法插入兩點(diǎn)：黃金分割法插入兩點(diǎn)：黃金分割法黃金分割法要求在區(qū)間要求在區(qū)間a,b中中插入的兩點(diǎn)位置是對插入的兩點(diǎn)位置是對稱稱的，如圖所示，的，如圖所示，ax1=x2b。設(shè)區(qū)間長為。設(shè)區(qū)間長為L，插入的，插入的兩個(gè)點(diǎn)把區(qū)間

4、分成兩個(gè)點(diǎn)把區(qū)間分成較長的一段較長的一段 和和較短的一段較短的一段(L )，如圖所示，如圖所示， ax2=bx1= ， ax1=bx2=L- ，這樣，這樣，無論刪去那一段，保留的區(qū)間長度總是無論刪去那一段，保留的區(qū)間長度總是 ，在每次，在每次迭代中，迭代中，整個(gè)區(qū)間的長度整個(gè)區(qū)間的長度L 與較長一段長度的比與較長一段長度的比等等于于較長一段長度與較短長度的比較長一段長度與較短長度的比。a2x1xbLL1LL比例系數(shù)式中：LLLLLLLLLL382.0618.0618.02152150101012222a2x1xbLL黃金分割法采用固定的縮短率黃金分割法采用固定的縮短率0.618L/(1-)Lb

5、x1x2?取點(diǎn)公式取點(diǎn)公式 原始區(qū)間原始區(qū)間 a, b, 第一次內(nèi)點(diǎn)為第一次內(nèi)點(diǎn)為x1,x2x1 =ax2?a +(1-)( b- a)f1=f(x1)x2a +=( b- a)f2=f(x2)?(1) 若若 f1f2abx1f1 =f(x1)a= a,b=x2, x2=x1x1a +=(1-)( b- a)f2= f1,(1-)L/L /LL(1-)L（2 2）黃金分割法的迭代步驟）黃金分割法的迭代步驟 （1 1）給定）給定初始單峰區(qū)間初始單峰區(qū)間 a,b 及允許誤差及允許誤差 00；（2 2）計(jì)算內(nèi)分點(diǎn)及其函數(shù)值）計(jì)算內(nèi)分點(diǎn)及其函數(shù)值)(),()(618. 0)(382. 0221121x

6、ffxffabaxabax較長的一段較短的一段（3 3）比較函數(shù)值）比較函數(shù)值 f1和和 f2的大??；的大??；(區(qū)間消去法區(qū)間消去法) 根據(jù)比較結(jié)果縮短搜索區(qū)間根據(jù)比較結(jié)果縮短搜索區(qū)間a2x1xb)(),(382. 0)(,111121212xffabaxxffxxbx間里點(diǎn)繼承保留到新搜索區(qū)即A. 當(dāng)當(dāng) f1 f2 時(shí)，極小點(diǎn)必在時(shí)，極小點(diǎn)必在a, x2中，則中，則B. 當(dāng)當(dāng) f1 f2 時(shí)，極小點(diǎn)必在時(shí)，極小點(diǎn)必在x1, b中，則中，則)(),(618. 0(,222212121xffabaxxffxxax）點(diǎn)繼承保留到新區(qū)間里即（4）判斷是否滿足精度要求。若新區(qū)間已縮短至預(yù)）判斷是否滿足

7、精度要求。若新區(qū)間已縮短至預(yù)定精度要求，即定精度要求，即b-a ，則轉(zhuǎn)第，則轉(zhuǎn)第5）步；否則轉(zhuǎn)第）步；否則轉(zhuǎn)第3）步，進(jìn)行下一次迭代計(jì)算。）步，進(jìn)行下一次迭代計(jì)算。（5）輸出）輸出最終區(qū)間的最終區(qū)間的中點(diǎn)中點(diǎn)作為作為近似最優(yōu)點(diǎn)近似最優(yōu)點(diǎn)，其對應(yīng)，其對應(yīng)的函數(shù)值即為最優(yōu)值，他們組成的最優(yōu)解為的函數(shù)值即為最優(yōu)值，他們組成的最優(yōu)解為 ：)(,2*xffbax收斂收斂迭代一輪后？迭代一輪后？兩內(nèi)點(diǎn)及其函數(shù)值兩內(nèi)點(diǎn)及其函數(shù)值x2x1x1x2= a+0.618（ba)，x1= a+0.382（ba），），F(xiàn)1 =f（ x1 ）,F 2 =f( x2)輸入輸入 a，b, tol F1F2 x2 b x1 x

8、2F1 F2 x1 = a+0.382(ba)， x1 ax2 x1F2 F 1x2 = a+0.618（ba)，batol x*=（a+b）/2， F（x*） 結(jié)束結(jié)束 yesnoyesnoabx2?下一輪迭代下一輪迭代abx1F1 =f( x1)本輪迭代本輪迭代bax2F2 =f( x2)最優(yōu)點(diǎn)找到最優(yōu)點(diǎn)找到例例 用黃金分割法求單變量函數(shù)用黃金分割法求單變量函數(shù)f()=2-7+10的極小點(diǎn)，初始搜索區(qū)的極小點(diǎn)，初始搜索區(qū)間間a,b=2,5.708，迭代精度，迭代精度=0.25。2.877525.7080迭代次數(shù)迭代次數(shù)abx1x2y1比較比較y2012345222.87752.87753.

9、20993.41655.70804.29204.29203.75093.75093.75093.4165 4.29202.87753.41653.75093.41653.2099 3.41653.54433.41653.5443 3.6232-2.2430-1.8601-2.2430-2.1659-2.2430-1.6227-2.2430-2.1870-2.2430-2.24803.41654.29203.75093.2099ab黃金分割法程序框圖黃金分割法程序框圖 開開 始始輸入輸入a, b, , 120.382()0.618()xabaxaba12( )()f xf x22121111,0

10、.382(),( )bx xx ffxabaff x11212222,0.618(),()ax xxffxabaff x*0.5(),()xabff x結(jié)結(jié) 束束例例 3-1 用黃金分割法求函數(shù)用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點(diǎn)，的極小點(diǎn)， 初始點(diǎn)初始點(diǎn) x0=0, 步長步長h=1,精度精度 =0.2。解：解：1）確定初始區(qū)間確定初始區(qū)間 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1 f2=f(x2)=1 由于由于f1f2, 應(yīng)繼續(xù)向前探測應(yīng)繼續(xù)向前探測 x3= x0+2h=0+2=2 f3=f(x3)=18 由于由于f2f3,可知初始區(qū)間已經(jīng)找到，即可

11、知初始區(qū)間已經(jīng)找到，即 a,b=x1,x3=0,23.3 3.3 黃金分割法黃金分割法2）用黃金分割法縮小區(qū)間用黃金分割法縮小區(qū)間 第一次縮小區(qū)間：第一次縮小區(qū)間： x1=0+0.382(2-0)=0.764, f1=0.282 x2=0+0.618(2-0)=1.236, f2=2.72 由于由于f10.2,應(yīng)繼續(xù)縮小區(qū)間應(yīng)繼續(xù)縮小區(qū)間3.3 3.3 黃金分割法黃金分割法第二次縮小區(qū)間：第二次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382 (1.236-0)=0.472, f1=0.317 由于由于f1f2, 故故新區(qū)間新區(qū)間a,b=x1,b=0.4

12、72, 1.236 由于由于 b-a=1.236-0.472=0.7640.2, 應(yīng)繼續(xù)縮小區(qū)間應(yīng)繼續(xù)縮小區(qū)間 第三次縮小區(qū)間：第三次縮小區(qū)間： 令令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=0.747 由于由于f10.2, 應(yīng)繼續(xù)縮小區(qū)間。應(yīng)繼續(xù)縮小區(qū)間。3.3 3.3 黃金分割法黃金分割法 第四次縮小區(qū)間：第四次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382 (0.944-0.472)=0.652, f1=0.223由于由于f10.2, 應(yīng)繼續(xù)縮小區(qū)間。

13、應(yīng)繼續(xù)縮小區(qū)間。第五次縮小區(qū)間：第五次縮小區(qū)間：令令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382 (0.764-0.472)=0.584, f1=0.262由于由于f1f2, 故故新區(qū)間新區(qū)間a,b=x1,b=0.584, 0.764因?yàn)橐驗(yàn)?b-a=0.764-0.584=0.180.2, 停止迭代。停止迭代。黃金分割法黃金分割法求的的極小點(diǎn)與極小值：求的的極小點(diǎn)與極小值： x=0.5 (0.584+0.764)=0.674, f(x)=0.2223.3 3.3 黃金分割法黃金分割法求導(dǎo)運(yùn)算求導(dǎo)運(yùn)算求的極小點(diǎn)與極小值：求的極小點(diǎn)與極小值： x=0.667,

14、 f(x)=0.222一、牛頓法一、牛頓法3.4 3.4 插值方法插值方法利用一點(diǎn)的利用一點(diǎn)的函數(shù)值函數(shù)值、一階導(dǎo)數(shù)一階導(dǎo)數(shù)以及以及二階二階導(dǎo)數(shù)導(dǎo)數(shù)構(gòu)造二次多項(xiàng)構(gòu)造二次多項(xiàng)式。用構(gòu)造的二次式。用構(gòu)造的二次多項(xiàng)式的極小點(diǎn)作多項(xiàng)式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的為原函數(shù)極小點(diǎn)的近似。近似。設(shè)設(shè)f(a)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)為一個(gè)連續(xù)可微的函數(shù)，則在點(diǎn)a0附近附近進(jìn)行泰勒展開并保留到二次項(xiàng)：進(jìn)行泰勒展開并保留到二次項(xiàng)：2000001( )( )()()()()()2f aaf afaaafaaa1()0a用二次函數(shù)用二次函數(shù)(a)的極小點(diǎn)的極小點(diǎn)a1作為作為f(a)極小點(diǎn)的一個(gè)近似極小點(diǎn)的一個(gè)近似點(diǎn)

15、。根據(jù)極值必要條件點(diǎn)。根據(jù)極值必要條件:0010()()()0fafaaa即即0100()()faaafa依此類推可得依此類推可得牛頓迭代公式：牛頓迭代公式：1()()kkkkfaaafa在在a0處用一拋物線處用一拋物線(a)代替曲線代替曲線f(a)，相當(dāng)于用一斜直線相當(dāng)于用一斜直線(a)代替曲線代替曲線f(a) 。這樣各個(gè)近似點(diǎn)。這樣各個(gè)近似點(diǎn)是通過對作是通過對作f(a)切切線求得與軸的交點(diǎn)線求得與軸的交點(diǎn)找到的，所以，有找到的，所以，有時(shí)，牛頓法又稱作時(shí)，牛頓法又稱作切線法。切線法。1kkaa牛頓法牛頓法開開 始始計(jì)算計(jì)算 ，*1kaa給定初始點(diǎn)給定初始點(diǎn) ，誤差，誤差 ,令令k=00a(

16、 ),( )kkff計(jì)算計(jì)算 ，1()()kkkkfaaafa1kk結(jié)結(jié) 束束數(shù)值數(shù)值 k 0 1 2 3 4 3 5.1667 4.33474 4.03960 4.00066 -52 153.35183 32.30199 3.38299 0.00551 24 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 41664234xxxxxFkxkxFkxF 給定初始點(diǎn)給定初始點(diǎn)x0=3，=0.001，計(jì)算公式：，計(jì)算

17、公式：1()()kkkkF xxxFx 1224122 xxxF函數(shù)的二階導(dǎo)數(shù)：函數(shù)的二階導(dǎo)數(shù)： 161212423xxxxF解：解： 函數(shù)的一階導(dǎo)數(shù)：函數(shù)的一階導(dǎo)數(shù)：1kx 優(yōu)點(diǎn)優(yōu)點(diǎn)：1）收斂速度快。）收斂速度快。 缺點(diǎn)缺點(diǎn)：1）要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次）要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加每次 迭代的工作量。迭代的工作量。 2）數(shù)值微分計(jì)算函數(shù)二階導(dǎo)數(shù)，舍入誤差將）數(shù)值微分計(jì)算函數(shù)二階導(dǎo)數(shù)，舍入誤差將 嚴(yán)重影響牛頓法的收斂速度，嚴(yán)重影響牛頓法的收斂速度， f (x)的值越的值越 小問題越嚴(yán)重。小問題越嚴(yán)重。 3）牛頓法要求）牛頓法要求初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)初始點(diǎn)離極小點(diǎn)不太遠(yuǎn)，否則，

18、否則 可能使極小化序列發(fā)散或收斂到非極小點(diǎn)?？赡苁箻O小化序列發(fā)散或收斂到非極小點(diǎn)。牛頓法牛頓法二、二次插值法（二、二次插值法（）a1af(a)2a3a1ff23fa*在給定的在給定的單峰區(qū)間單峰區(qū)間中，利用目標(biāo)函數(shù)上的中，利用目標(biāo)函數(shù)上的三個(gè)點(diǎn)三個(gè)點(diǎn)來來構(gòu)構(gòu)造造一個(gè)一個(gè)二次插值函數(shù)二次插值函數(shù)，以近似地表達(dá)，以近似地表達(dá)原目標(biāo)函數(shù)原目標(biāo)函數(shù)，并，并求這個(gè)插值函數(shù)的求這個(gè)插值函數(shù)的極小點(diǎn)極小點(diǎn)近似作為原目標(biāo)函數(shù)的近似作為原目標(biāo)函數(shù)的極小點(diǎn)極小點(diǎn)。( )f aap2( )=ABCp aB=-2Cpay0aap1a1a2apa3ay0a*y1y2ypy3a1a2apa*y1y2ypyp1apap1a

19、1a2apa3ay0a*y1y2ypy3a2a3ay0a*y2ypy3yp1211112222223333p()ABCp()ABCp()ABCfff構(gòu)造的構(gòu)造的上的三個(gè)點(diǎn)上的三個(gè)點(diǎn): : 解得解得系數(shù)系數(shù)222222231312123122331231312123122331()()()()()()()()()()()()fffBfffC 2222222313121232313121231 ()()()22 ()()()pBfffCfff 2pyy二次插值法二次插值法開開 始始計(jì)算計(jì)算 ，*2min,pyyy給定給定 ,123123a a a y y y ,ppy縮短區(qū)間縮短區(qū)間名稱置換名稱置換結(jié)結(jié) 束束a1a2apa3ay0a*y1y2ypy3a1a2apa3a0a*yy1y2ypy3*2min,pyyy二次插值法程序編制換名方法二次插值法程序編制換名方法(1)(1)1) a2ap y2yp y2ap y2 yp y2yp（1 1）二次插值法只要求）二次插值法