二次插值法.doc

一维无约束优化算法——二次插值法

--
一维无约束优化算法——二次插值法
二次插值法亦是用于一元函数在确定的初始区间内搜索极小点的一种方法。它属于曲线拟合方法的范畴。
基本原理
在求解一元函数的极小点时，常常利用一个低次插值多项式来逼近原目标函数，然后求该多项式的极小点(低次多项式的极小点比较容易计算)，并以此作为目标函数的近似极小点。如果其近似的程度尚未达到所要求的精度时，可以反复使用此法，逐次拟合，直到满足给定的精度时为止。
常用的插值多项式为二次或三次多项式，分别称为二次插值法和三次插值法。这里我们主要介绍二次插值法的计算公式。
假定目标函数在初始搜索区间中有三点、和，其函数值分别为、和(图1}，且满足，，即满足函数值为两头大中间小的性质。利用这三点及相应的函数值作一条二次曲线，其函数为一个二次多项式，式中、、为待定系数。

图1
根据插值条件，插值函数与原函数在插值结点、、处函数值相等，得
（2）
为求插值多项式的极小点，可令其一阶导数为零，即
（3）
解式(3)即求得插值函数的极小点（4）
式(4)中要确定的系数可在方程组(2)中利用相邻两个方程消去而得:
（5）
（6）
将式(5)、(6)代入式(4)便得插值函数极小值点的计算公式：
（7）
把取作区间内的另一个计算点，比较与两点函数值的大小，在保持两头大中间小的前提下缩短搜索区间，从而构成新的三点搜索区间，再继续按上述方法进行三点二次插值运算，直到满足规定的精度要求为止，把得到的最后的作为的近似极小值点。上述求极值点的方法称为三点二次插值法。
为便于计算，可将式(7)改写为
（8）
式中：
（9）
（10）
二．程序框图
开始
给定

结束

否
否
否
否
否
是
是
是
是
是
三．例题及其程序代码
1.用二次差值法求f()=sin在45上的极小值
2.程序
(1)functiony=f(x)
y=sin(x);…………………….%定义f文件
（2）c1=(y3-y1)/(x3-x1);
c2=((y2-y1)/(x2-x1)-c1)/(x2-x3);
ap=0.5*(x1+x3-c1/c2);
yp=f(ap);……………………%定义f1文件
（3）x1=4;
x2=4.5;
x3=5;
e=0.001;
y1=f(x1);
y2=f(x2);
y3=f(x3);………………%确定初始差值节点
h=0.1;
c1=(y3-y1)/(x3-x1);
c2=((y2-y1)/(x2-x1)-c1)/(x2-x3);
ap=0.5*(x1+x3-c1/c2);
yp=f(ap);…%计算二次插值函数极小点
while(abs((y2-yp)/y2)<e)....%判断迭代终止
if((ap-x2)*h>0)条件
if(y2>=yp)
x1=x2;
y1=y2;
x2=ap;
y2=yp;
f1;
else
x3=ap;
y3=yp;
f1;
end
elseif(y2>=yp)
x3=x2;
y3=y2;
x2=ap;
y2=yp;
f1;
else
x1=ap;
y1=yp;
f1;…………………..%缩短搜索区间
end
end
if(y2<yp)
xo=x2;
yo=y2;

else
xo=ap;
yo=yp;

end
xo
yo

二次插值法

四结果分析

经过MATLAB运算，结果如上，与解析法运算结果相同，说明二次差值的效果很好。值得说明的一点是，e即最优解范围，e取的越小，计算结果越精确，但是循环的次数会变多，因此选择合适的e对用二次差值法求极小点也很有必要的。