一維搜索插值法

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

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

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

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

一維搜索

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

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

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

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

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

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

2〕比較兩試點函數(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〕重新計算插入試點。[a,b]=[2,5.708]黃金分割法的程序框圖2、函數(shù)逼近法將搜索區(qū)間內(nèi)的假設(shè)干試驗點的函數(shù)值構(gòu)造的低次多項式〔二次多項式〕作為函數(shù)的近似表達式，用這個多項式的極值作為原函數(shù)的極值點的近似點。第四節(jié)一維搜索的插值法1、插值方法與試探方法的比較牛頓法和拋物線法3、二次多項式逼近原函數(shù)的方法一、牛頓法〔切線法〕根本思想取原函數(shù)極小點的一個近似點，在近似點附近用二次函數(shù)〔泰勒展開并保存到二次項〕逼近原函數(shù)，以逼近函數(shù)的極小點作為原極小點的新近似點，依此類推,直到近似點滿足控制誤差為止，取最后的近似點作為原函數(shù)的極小點。迭代公式幾何解釋特點收斂速度快計算工作量大對初始點的選擇要求高二次插值法是利用目標函數(shù)在假設(shè)干點的函數(shù)值或?qū)?shù)信息構(gòu)造二次多項式函數(shù)來逼近原一維搜索函數(shù)，并且用插值多項式的極值點近似作為目標函數(shù)的極小點。由于二次多項式函數(shù)的圖形是拋物線，所以二次插值法又稱為拋物線插值法。二次插值法1.根本思想在給定目標函數(shù)的初始區(qū)間內(nèi)取三點，設(shè)它們的函數(shù)值分別為,滿足條件和。利用原函數(shù)曲線上的、和三點構(gòu)造一條拋物線式中，是待定系數(shù)。

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

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

式中

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

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

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