一維搜索插值法

搜索方向步長(zhǎng)因子第三章一維搜索方法第一節(jié)概述步長(zhǎng)求多維目標(biāo)函數(shù)的極值時(shí)，假設(shè)迭代過(guò)程的出發(fā)點(diǎn)及搜索方向已確定，那么從出發(fā)，沿方向搜索新點(diǎn)的迭代格式為

式中，為步長(zhǎng)因子。選擇一特定步長(zhǎng)，使產(chǎn)生的新點(diǎn)是方向上目標(biāo)函數(shù)的極小點(diǎn)，即

那么稱(chēng)為方向上的最優(yōu)步長(zhǎng)因子。二維函數(shù)f(x)沿方向s的一維搜索例如最優(yōu)步長(zhǎng)因子

在搜索方向上，使目標(biāo)函數(shù)取得極小值的步長(zhǎng)因子，稱(chēng)為該方向上最優(yōu)步長(zhǎng)因子。

一維搜索

沿給定搜索方向，求最優(yōu)步長(zhǎng)因子的一元函數(shù)極值問(wèn)題，稱(chēng)為一維搜索。一維問(wèn)題是多維問(wèn)題的根底解析解法先將f(x+ad)進(jìn)行泰勒展開(kāi)，并取到二階項(xiàng)，后對(duì)泰勒展開(kāi)式利用微積分求極值方法獲得最正確步長(zhǎng)因子。求最正確步長(zhǎng)因子方法數(shù)值解法利用計(jì)算機(jī)通過(guò)反復(fù)迭代計(jì)算求得最正確步長(zhǎng)因子的近似值。根本思路是：先確定步長(zhǎng)因子〔最優(yōu)點(diǎn)〕所在的區(qū)間，然后根據(jù)區(qū)間消去法遠(yuǎn)離不斷縮小此區(qū)間，從而獲得最優(yōu)點(diǎn)的數(shù)值的近似解。0.618法,拋物線法,三次插值法.....例：則當(dāng)確實(shí)定方法1、運(yùn)用進(jìn)退法確定單變量函數(shù)極小點(diǎn)所在的搜索區(qū)間，該區(qū)間應(yīng)是單谷區(qū)間。單谷區(qū)間是指函數(shù)在區(qū)間內(nèi)只有一個(gè)極小點(diǎn)。在極小點(diǎn)左邊的函數(shù)值應(yīng)是嚴(yán)格下降，在極小點(diǎn)右邊的函數(shù)值應(yīng)是嚴(yán)格上升，即單谷區(qū)間內(nèi)的函數(shù)值具有的特征是：“高—低—高”。

2、運(yùn)用區(qū)間消去法，求極小點(diǎn)。第二節(jié)搜索區(qū)間確實(shí)定與區(qū)間消去法原理數(shù)值解法求解一般步驟正向搜索外推法一、確定初始搜索區(qū)間的外推法〔進(jìn)退法〕中間各個(gè)試探點(diǎn)函數(shù)值依次減少，h>0

反向搜索外推法第一試探點(diǎn)函數(shù)值上升，反向以后中間各個(gè)試探點(diǎn)函數(shù)值依次減少，h<01.取初始點(diǎn)為第一點(diǎn),前進(jìn)一步,得第二點(diǎn),并計(jì)算函數(shù)值.2.比較函數(shù)值,,向前試探3.比較函數(shù)值,,步長(zhǎng)加倍,向前試探4.比較函數(shù)值,,步長(zhǎng)加倍,再向前試探。5.比較函數(shù)值,所以a=2,b=8,即搜索區(qū)間為[a,b]=[2,8].

-外推法程序框圖二、區(qū)間消去法原理由外推法確定搜索區(qū)間[a,b]后，在區(qū)間內(nèi)插入兩點(diǎn)a1和b1〔a<a1<b1<b〕，計(jì)算插入點(diǎn)的函數(shù)值，并比較其大小，確定消去的區(qū)間，從而得到縮短的搜索區(qū)間，依次類(lèi)推，最后即可得到理論最小點(diǎn)的近似解。一維搜索方法分類(lèi)應(yīng)用區(qū)間消去原理，需要在確定的搜索內(nèi)給出插入點(diǎn)。根據(jù)確定插入點(diǎn)的方法不同，一維搜索方法分為兩大類(lèi)：試探法：黃金分割法、斐波那契法插值法〔函數(shù)逼近法〕：二次插值法、三次插值法、格點(diǎn)法等。黃金分割法的根本方法是通過(guò)不斷縮小搜索區(qū)間的長(zhǎng)度來(lái)搜索函數(shù)的極小點(diǎn)。在已確定的函數(shù)搜索區(qū)間內(nèi)，其函數(shù)值呈現(xiàn)”高—低—高”的特征。通過(guò)比較搜索區(qū)間內(nèi)兩試點(diǎn)的函數(shù)值，逐步縮短搜索區(qū)間，得到一個(gè)不斷縮小的區(qū)間序列，直到極小點(diǎn)所在區(qū)間縮小到給定的精度，取其中點(diǎn)作為近似極小點(diǎn)輸出。 這種方法步驟簡(jiǎn)單，效果較好，但是計(jì)算效率偏低，是計(jì)算中常用的方法之一。

第三節(jié)黃金分割法算法的關(guān)鍵插入點(diǎn)對(duì)稱(chēng)分布在搜索區(qū)間內(nèi)插入的兩個(gè)試點(diǎn)在區(qū)間的位置相對(duì)于區(qū)間邊界對(duì)稱(chēng)分布。

固定的區(qū)間收縮率區(qū)間收縮率是表示每次縮小所得到的新區(qū)間長(zhǎng)度與縮小前舊區(qū)間長(zhǎng)度之比.整理后得到一元二次方程其解故黃金分割法又稱(chēng)為0.618法。插入的兩個(gè)試點(diǎn)為:黃金分割法的搜索過(guò)程給出搜索區(qū)間[a,b]及收斂精度e，并置=0.618。按照公式(1)(2)計(jì)算插入點(diǎn)，并計(jì)算其函數(shù)值。根據(jù)區(qū)間消去法原理，進(jìn)行區(qū)間縮短。檢驗(yàn)區(qū)間是否縮短到足夠短，如果不滿足轉(zhuǎn)步驟2。否那么轉(zhuǎn)下步。取區(qū)間兩端點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。終止判別條件采用點(diǎn)距準(zhǔn)那么〔區(qū)間足夠小〕：1〕.在搜索區(qū)間內(nèi)取兩試點(diǎn)，并且計(jì)算它們函數(shù)值。

2〕比較兩試點(diǎn)函數(shù)值，縮短搜索區(qū)間.由于消去右區(qū)間初始搜索區(qū)間[2,8]，迭代精度ε=0.01,收斂條件:|b-a|<ε。3〕確定新區(qū)間

4〕判斷迭代終止條件：不滿足迭代終止條件，繼續(xù)搜索。708.52==ab292.412==aa6227.112-==ff4165.3)2708.5(618.0708.5)(618.01=-′-=--=abba2430.2104165.374165.3)(211-=+′-==aff5〕重新計(jì)算插入試點(diǎn)。[a,b]=[2,5.708]黃金分割法的程序框圖2、函數(shù)逼近法將搜索區(qū)間內(nèi)的假設(shè)干試驗(yàn)點(diǎn)的函數(shù)值構(gòu)造的低次多項(xiàng)式〔二次多項(xiàng)式〕作為函數(shù)的近似表達(dá)式，用這個(gè)多項(xiàng)式的極值作為原函數(shù)的極值點(diǎn)的近似點(diǎn)。第四節(jié)一維搜索的插值法1、插值方法與試探方法的比較牛頓法和拋物線法3、二次多項(xiàng)式逼近原函數(shù)的方法一、牛頓法〔切線法〕根本思想取原函數(shù)極小點(diǎn)的一個(gè)近似點(diǎn)，在近似點(diǎn)附近用二次函數(shù)〔泰勒展開(kāi)并保存到二次項(xiàng)〕逼近原函數(shù)，以逼近函數(shù)的極小點(diǎn)作為原極小點(diǎn)的新近似點(diǎn)，依此類(lèi)推,直到近似點(diǎn)滿足控制誤差為止，取最后的近似點(diǎn)作為原函數(shù)的極小點(diǎn)。迭代公式幾何解釋特點(diǎn)收斂速度快計(jì)算工作量大對(duì)初始點(diǎn)的選擇要求高二次插值法是利用目標(biāo)函數(shù)在假設(shè)干點(diǎn)的函數(shù)值或?qū)?shù)信息構(gòu)造二次多項(xiàng)式函數(shù)來(lái)逼近原一維搜索函數(shù)，并且用插值多項(xiàng)式的極值點(diǎn)近似作為目標(biāo)函數(shù)的極小點(diǎn)。由于二次多項(xiàng)式函數(shù)的圖形是拋物線，所以二次插值法又稱(chēng)為拋物線插值法。二次插值法1.根本思想在給定目標(biāo)函數(shù)的初始區(qū)間內(nèi)取三點(diǎn)，設(shè)它們的函數(shù)值分別為,滿足條件和。利用原函數(shù)曲線上的、和三點(diǎn)構(gòu)造一條拋物線式中，是待定系數(shù)。

原函數(shù)曲線——實(shí)線

插值函數(shù)曲線——虛線2.插入點(diǎn)的計(jì)算求插值多項(xiàng)式的極值點(diǎn)。待定系數(shù)由下面線性方程組得到求解線性方程組得到插值極小點(diǎn)

式中

3.二次插值算法形成把和作為在區(qū)間插入的兩個(gè)試點(diǎn)，根據(jù)區(qū)間消去法原理，縮短區(qū)間。重復(fù)上述過(guò)程，直到滿足終止條件，取較小的插入點(diǎn)作為原目標(biāo)函數(shù)極小點(diǎn)的近似解。3.二次插值算法形成把和作為在區(qū)間插入的兩個(gè)試點(diǎn)，根據(jù)區(qū)間消去法原理，縮短區(qū)間。重復(fù)上述過(guò)程，直到滿足終止條件，取較小的插入點(diǎn)作為原目標(biāo)函數(shù)極小點(diǎn)的近似解。4終止判別條件采用點(diǎn)距準(zhǔn)那么〔前后兩個(gè)插值點(diǎn)的距離不超過(guò)誤差限〕：1.計(jì)算初始點(diǎn)及其函數(shù)值2.計(jì)算插值點(diǎn)3.判斷收斂條件初始搜索區(qū)間[2,8]，迭代精度ε=0.01,收斂條件:|ap-a2|<ε。5.重新計(jì)算插值點(diǎn)6.判斷收斂條件，得最優(yōu)解4.縮短搜索區(qū)間二次插值法程序框圖補(bǔ)充說(shuō)明——區(qū)間端點(diǎn)換名方法：〔1〕

二次插值法只要求f(x)連續(xù)，不要求其一階可微?！?〕

收斂速度比黃金分割法快，但可靠性不如黃金分割法好，程序也較長(zhǎng)?！?〕如p(x)