二次插值算法.docx

《二次插值算法.docx》由会员分享，可在线阅读，更多相关《二次插值算法.docx（9页珍藏版）》请在优知文库上搜索。

1、二次辅值法亦是用千一元函数/()在确定的初始区间内搜寻微小点的一种方法.它属于曲线拟合方法的范跖，一、基本原理在求解一元函数月的微小点时，经常利用一个低次插值多项式PK)来靠近原目标函数，然后求该多项式的微小点(低次多项式的微小点比较简单计算)，并以此作为目标函数/3)的近似微小点。假如其近似的程度尚未达到所要求的精度时，可以反复运用此法，逐次拟合,直到满意给定的精度时为止。常用的插值多项式负为二次或三次多项式，分别称为二次插值法和三次插值法。这里我们主要介绍二次插值法的计算公式。假定目标函数在初始搜寻区间卜M中有三点、/和通(00o),其函数值分别为工、力和(图1,且满意+aH三j*冽=3%

2、十+，24=/)为求插值多项式P（八）的微小点片,可令其一阶导数为零，即p,（八）=a1.+2a2a=0(3)解式(3)即求得插值函数的微小点一涛(4)式(4)中要确定的系数与町可在方程组(2)中利用相邻两个方程消去。而得：6-+（E-Nb+泗ba,=a-一”，）_丁依（5）多=博-冽幽-冽*-0）-（6）将式（5）、（6）代入式（4）便得插值函数微小值点可的计算公式：.对k+俯冲+口二空k%=-（*-西+（0以+仙）-Nk（7）把再取作区间即W1.内的另一个计算点，比较；与小两点函数值的大小，在保持两头大中间小的前提下缩短搜寻区间，从而构成新的三点搜寻区间，再接着按上述方法进行三点二次插值运

3、算，直到满意规定的精度要求为止,把得到的最终的E作为了3）的近似微小值点。上述求极值点的方法称为三点二次插值法。为便于计算，可将式（7）改写为犷+/T）（8）式中:伉Mq一冽-*-a0）（10）:、迭代过程与算法框图(1)确定初始插值结点通常取初始搜寻区间【%同的两端点与中点为M1.)=，,)=6,=。乂/+中)。计算函数值/=/Hn),1.k0),3=k),构成三个初始插值结点召、舄、舄。(2)计算二次插值函数微小点W按式计算W,并将W记作点)，计算了,=/(/).若本步骤为对初始搜寻区间的第一次插值或”点仍为初始给定点时，则进行下一步(3);否则转步骤(4)(3)缩短搜寻区间缩短搜寻区间的

4、原则是：比较函数值力、,取其小者所对应的点作为新的心)点，并以此点左右两邻点分别取作新的公和构成缩短后的新搜寻区间Wi1.其详细方法则如图2所示，依据原区间中d)和OW的相对位置以与函数值力和角之比较有a、b、c、d四种状况，图中阴影线部分表示丢去的区间。在对新区间三个新点的代号作依次a、户、的一般化处理后，”算其函数值，并令，=/(),=M,力=/依),返回步骤。图2(b)图2(C)图2(d)(4)推断迭代终止条件在一般状况下，因“是前一次插值函数的微小值点，。是木次插值函数的微小值点，若以。和ND的距离足够小时，即满意W归。或和“两者原函数值已很接近，即满意儿-AK一则停止迭代，这时，若4

5、=e,微小值2=().如不满意上述迭代终止条件，则返回步骤(3),再次缩短搜寻区间，直至最终满意终止条件。按上述步骤设计的二次插值法算法框图见图3。/给定o6e1.2.3)hac,o(a+/WgG5/)/C5-(u-a-QO.5(*+-Q“-Z(U3-/”)(“”0“2人0?u,-an?/*GJazYW一$*出X输出“；”ff(.a)-图3算法框图中有几点需作些说明。1 .判别框J=。?若成立,按式(9)和式(10)则有-_c.-33-,一啰-淤）说明三个插值结点4（/，工）、玛（/）/）、鸟卜/）在一条直线上；2 .判别框（/*湃-小）。？若不成立，说明乂落在区间之外。上述两种状况只是在区间已缩得很小，由于三个插值结点已非常接近,计算机的舍入误差才可能使其发生。此时取小却和人作为最优解应是合理的。3 .在初始搜寻区间第一次插值或小仍为初始给定点时，源和#并不代表前后二次插值函数微小点，因而判别式W-0T并不能准确地反映该不该终止迭代，这时应进行步骤（3）缩短搜寻区间，宜至初始点修第一次由仪代替，运用判别式进行终止判别才具意义。为此，算法框图中设置开关K=O和K=I分别表示初始点出“第次由a代替前和后的状态。