二次插值算法

1、二次插值法亦是用于一元函数在确定的初始区间内搜索极小点的一种方法。它属于曲线拟合方法的范畴。一、基本原理在求解一元函数-J的极小点时，常常利用一个低次插值多项式r F丿来逼近原目标函数，然后求该多项式的极小点（低次多项式的极小点比较容易计算 ），并以此作为目标函数的近似极小点。如果其近似的程度尚未达到所要求的精度时， 可以反复使用此法，逐次拟合, 直到满足给定的精度时为止。常用的插值多项式（二为二次或三次多项式，分别称为二次插值法和三次插值法。这里我 们主要介绍二次插值法的计算公式。假定目标函数在初始搜索区间 b上中有三点 少、旣和-''，其函数值分别为、二和二（图1，且满足T

2、 ，段， 仏，即满足函数值为两头大中间小的性质。禾U用这三点及相应的函数值作一条二次曲 线，其函数'I；为一个二次多项式(1)式中亠、二-比为待定系数。d-根据插值条件，插值函数 与原函数-；1在插值结点-、I处函数值相等，得戸（曲）=兔+如护+匀於y=7i戸（口）=怖+2/）+旳 =j2戸（c/”）=矶+2谭+ 口用加=了占r ' （ 2）为求插值多项式的极小点，可令其一阶导数为零，即解式（3）即求得插值函数的极小点Fj （ 4） 式中要确定的系数一5心可在方程组（2）中利用相邻两个方程消去心而得:一 应尸匕 * （尹'一 口少、4 ”、疔 一 e妙 茲 （&

3、一用、比十（d一心）十3一 毎3一抚X凸p）-段国）防）一 ）将式（5）、（6）代入式（4）便得插值函数极小值点I的计算公式:-<?曾A】+&审-曲尸*十（/尸一妙丫 £（7）把二取作区间" f 内的另一个计算点，比较=与'两点函数值的大小，在保持''两头大中间小的前提下缩短搜索区间，从而构成新的三点搜索区间，再继续按上述方法进行三点二次插值运算，直到满足规定的精度要求为止，把得到的最后的V作为；的近似极小值点。上述求极值点的方法称为三点二次插值法。为便于计算，可将式（7）改写为式中:（9）t/a -刃血-卅）-5、迭代过程及算法框图确

4、定初始插值结点通常取初始搜索区间的两端点及中点为少二述护=3心二0.妝】）+曲）计算函数值构成三个初始插值结点(2) 计算二次插值函数极小点按式(8)计算、,并将。记作点二"，计算一儿 /。若本步骤为对初始搜索区间的第一次插值或点仍为初始给定点时，则进行下一步否则转步骤(4)(3) 缩短搜索区间缩短搜索区间的原则是：比较函数值丄、'，取其小者所对应的点作为新的 -：，点，并以此点左右两邻点分别取作新的丛% ，构成缩短后的新搜索区间叫。其具体方 法则如图2所示，根据原区间中二"和：的相对位置以及函数值 -和- 之比较有a、b、 c、d四种情况，图中阴影线部分表示丢去的

5、区间。在对新区间三个新点的代号作依次、二！、二'的一般化处理后，计算其函数值，并令_ ' '，_ ' ' ，返回步骤(2)。/(J0 严卅小、图 2( a)图 2 (b)图 2 (c)图 2 (d)(4)判断迭代终止条件在一般情况下，因是前一次插值函数的极小值点，工是本次插值函数的极小值点，若Ct一盘I ME 和的距离足够小时，即满足1一 ，或和 两者原函数值已很接近，即满足I"1"''，则停止迭代，这时，若儿二，输出极小值点-汀，极小值即'，4 ' -时，输出极小值点少"，极小值"

6、帰)如不满足上述迭代终止条件，则返回步骤(3)，再次缩短搜索区间，直至最后满足终止条件。按上述步骤设计的二次插值法算法框图见图3。算法框图中有几点需作些说明。广=n1判别框-?若成立，按式（9）和式（10）则有说明三个插值结点二'耳C）、耳（心丛）在一条直线上步骤（3）缩短搜索区间，直至初始点行终止判别才具意义。为此，算法框图中设置开关K=0和K=1分别表示初始点二第一次2判别框：''1 1 - ?若不成立，说明 亠"落在区间之外。上述两种情况只是在区间已缩得很小，由于三个插值结点已十分接近，计算机的舍入误差才可能使其发生。此时取 X !和一二作为最优解应是合理的。函数极小点，因而判别式&