二次插值算法Word版

整理為word格式整理為word格式整理為word格式二次插值法亦是用于一元函數(shù)在確定的初始區(qū)間內(nèi)搜索極小點(diǎn)的一種方法。它屬于曲線擬合方法的范疇。一、基本原理在求解一元函數(shù)的極小點(diǎn)時(shí)，常常利用一個(gè)低次插值多項(xiàng)式來(lái)逼近原目標(biāo)函數(shù)，然后求該多項(xiàng)式的極小點(diǎn)(低次多項(xiàng)式的極小點(diǎn)比較容易計(jì)算)，并以此作為目標(biāo)函數(shù)的近似極小點(diǎn)。如果其近似的程度尚未達(dá)到所要求的精度時(shí)，可以反復(fù)使用此法，逐次擬合，直到滿足給定的精度時(shí)為止。常用的插值多項(xiàng)式為二次或三次多項(xiàng)式，分別稱為二次插值法和三次插值法。這里我們主要介紹二次插值法的計(jì)算公式。假定目標(biāo)函數(shù)在初始搜索區(qū)間中有三點(diǎn)、和，其函數(shù)值分別為、和(圖1}，且滿足，，即滿足函數(shù)值為兩頭大中間小的性質(zhì)。利用這三點(diǎn)及相應(yīng)的函數(shù)值作一條二次曲線，其函數(shù)為一個(gè)二次多項(xiàng)式（1）式中、、為待定系數(shù)。整理為word格式整理為word格式整理為word格式圖1根據(jù)插值條件，插值函數(shù)與原函數(shù)在插值結(jié)點(diǎn)、、處函數(shù)值相等，得（2）為求插值多項(xiàng)式的極小點(diǎn)，可令其一階導(dǎo)數(shù)為零，即（3）解式(3)即求得插值函數(shù)的極小點(diǎn)（4）式(4)中要確定的系數(shù)可在方程組(2)中利用相鄰兩個(gè)方程消去而得:（5）整理為word格式整理為word格式整理為word格式（6）將式(5)、(6)代入式(4)便得插值函數(shù)極小值點(diǎn)的計(jì)算公式：（7）把取作區(qū)間內(nèi)的另一個(gè)計(jì)算點(diǎn)，比較與兩點(diǎn)函數(shù)值的大小，在保持兩頭大中間小的前提下縮短搜索區(qū)間，從而構(gòu)成新的三點(diǎn)搜索區(qū)間，再繼續(xù)按上述方法進(jìn)行三點(diǎn)二次插值運(yùn)算，直到滿足規(guī)定的精度要求為止，把得到的最后的作為的近似極小值點(diǎn)。上述求極值點(diǎn)的方法稱為三點(diǎn)二次插值法。為便于計(jì)算，可將式(7)改寫(xiě)為（8）式中：（9）（10）二、迭代過(guò)程及算法框圖(1)確定初始插值結(jié)點(diǎn)通常取初始搜索區(qū)間的兩端點(diǎn)及中點(diǎn)為，，。計(jì)算函數(shù)值，，，構(gòu)成三個(gè)初始插值結(jié)點(diǎn)、、。整理為word格式整理為word格式整理為word格式(2)計(jì)算二次插值函數(shù)極小點(diǎn)按式(8)計(jì)算，并將記作點(diǎn)，計(jì)算。若本步驟為對(duì)初始搜索區(qū)間的第一次插值或點(diǎn)仍為初始給定點(diǎn)時(shí)，則進(jìn)行下一步(3);否則轉(zhuǎn)步驟(4)(3)縮短搜索區(qū)間縮短搜索區(qū)間的原則是：比較函數(shù)值、，取其小者所對(duì)應(yīng)的點(diǎn)作為新的點(diǎn)，并以此點(diǎn)左右兩鄰點(diǎn)分別取作新的和，構(gòu)成縮短后的新搜索區(qū)間。其具體方法則如圖2所示，根據(jù)原區(qū)間中和的相對(duì)位置以及函數(shù)值和之比較有a、b、c、d四種情況，圖中陰影線部分表示丟去的區(qū)間。在對(duì)新區(qū)間三個(gè)新點(diǎn)的代號(hào)作依次、、的一般化處理后，計(jì)算其函數(shù)值，并令，，，返回步驟(2)。圖2（a）整理為word格式整理為word格式整理為word格式圖2（b）圖2（c）整理為word格式整理為word格式整理為word格式圖2（d）(4)判斷迭代終止條件在一般情況下，因是前一次插值函數(shù)的極小值點(diǎn)，是本次插值函數(shù)的極小值點(diǎn)，若和的距離足夠小時(shí)，即滿足，或和兩者原函數(shù)值已很接近，即滿足，則停止迭代，這時(shí)，若，輸出極小值點(diǎn)，極小值;否則，即時(shí)，輸出極小值點(diǎn)，極小值。如不滿足上述迭代終止條件，則返回步驟(3)，再次縮短搜索區(qū)間，直至最后滿足終止條件。按上述步驟設(shè)計(jì)的二次插值法算法框圖見(jiàn)圖3。整理為word格式整理為word格式整理為word格式圖3算法框圖中有幾點(diǎn)需作些說(shuō)明。1.判別框?若成立，按式(9)和式(10)則有說(shuō)明三個(gè)插值結(jié)點(diǎn)、、在一條直線上;整理為word格式整理為word格式整理為word格式2.判別框?若不成立，說(shuō)明落在區(qū)間之外。上述兩種情況只是在區(qū)間已縮得很小，由于三個(gè)插值結(jié)點(diǎn)已十分接近，計(jì)算機(jī)的舍入誤差才可能使其發(fā)生。此時(shí)取和作為最優(yōu)解應(yīng)是合理的。3.在初始搜索區(qū)間第一次插值或仍為初始給定點(diǎn)時(shí)，和并不代表前后二次插值函數(shù)極小點(diǎn)，因而判別式并不能確切地反映該不該終止迭代，這時(shí)應(yīng)進(jìn)行步驟(3)縮短搜索區(qū)間，直至初始點(diǎn)第一次由代替，使用判別式?進(jìn)行終止判別才具