基本思想
抛物线法也叫二次插值法,其基本思想是:在搜索区间中不断地使用二次多项式去近似目标函数,并逐步用插值多项式的极小点去逼近线搜索问题
m i n φ ( α ) = f ( x k + α d k ) min\,\,\,\varphi \left( \alpha \right) =f\left( x_k+\alpha d_k \right) minφ(α)=f(xk+αdk)
方法原理及推导
设函数在单谷区间 x 1 < x 2 < x 3 x_{1}<x_{2}<x_{3} x1<x2<x3的函数值 f ( x 1 ) > f ( x 2 ) < f ( x 3 ) f(x_{1})>f(x_{2})<f(x_{3}) f(x1)>f(x2)<f(x3)做出如下的二次插值多项式:
P ( x ) = a 0 + a 1 x + a 2 x 2 P\left( x \right) =a_0+a_1x+a_2x^2 P(x)=a0+a1x+a2x2
它应满足条件:
{ P ( x 1 ) = a 0 + a 1 x 1 + a 2 x 1 2 = f 1 = f ( x 1 ) P ( x 2 ) = a 0 + a 1 x 2 + a 2 x 2 2 = f 2 = f ( x 2 ) P ( x 3 ) = a 0 + a 1 x 3 + a 2 x 3 2 = f 3 = f ( x 3 ) \begin{cases} P\left( x_1 \right) =a_0+a_1x_1+a_2x_{1}^{2}=f_1=f\left( x_1 \right)\\ P\left( x_2 \right) =a_0+a_1x_2+a_2x_{2}^{2}=f_2=f\left( x_2 \right)\\ P\left( x_3 \right) =a_0+a_1x_3+a_2x_{3}^{2}=f_3=f\left( x_3 \right)\\ \end{cases} ⎩⎪⎨⎪⎧P(x1)=a0+a1x1+a2x12=f1=f(x1)P(x2)=a0+a1x2+a2x22=f2=f(x2)P(x3)=a0+a1x3+a2x32=f3=f(x3)
从极值的必要条件知 P ′ ( x ˉ ) = a 1 + 2 a 2 x ˉ = 0 P^{‘} \left( \bar{x} \right) =a_1+2a_2\bar{x}=0 P′(xˉ)=a1+2a2xˉ=0,求得 x ˉ = − a 1 / 2 a 2 \bar{x}=-a_{1}/2a_{2} xˉ=−a1/2a2
易知: a 1 ( x 1 − x 2 ) + a 2 ( x 1 2 − x 2 2 ) = f 1 − f 2 a 1 ( x 2 − x 3 ) + a 2 ( x 2 2 − x 3 2 ) = f 2 − f 3 a_1\left( x_1-x_2 \right) +a_2\left( x_{1}^{2}-x_{2}^{2} \right) =f_1-f_2\\ a_1\left( x_2-x_3 \right) +a_2\left( x_{2}^{2}-x_{3}^{2} \right) =f_2-f_3 a1(x1−x2)+a2(x12−x22)=f1−f2a1(x2−x3)+a2(x22−x32)=f2−f3
求出系数 a 1 a_{1} a1和 a 2 a_{2} a2,就可以求得抛物线方程极小值表达式。
其表达式为:
x ˉ = − a 1 / 2 a 2 = 1 2 ( x 2 2 − x 3 2 ) f 1 + ( x 3 2 − x 1 2 ) f 2 + ( x 1 2 − x 2 2 ) f 3 ( x 2 − x 3 ) f 1 + ( x 3 − x 1 ) f 2 + ( x 1 − x 2 ) f 3 \bar{x}=-a_1/2a_2=\frac{1}{2}\frac{\left( x_{2}^{2}-x_{3}^{2} \right) f_1+\left( x_{3}^{2}-x_{1}^{2} \right) f_2+\left( x_{1}^{2}-x_{2}^{2} \right) f_3}{\left( x_2-x_3 \right) f_1+\left( x_3-x_1 \right) f_2+\left( x_1-x_2 \right) f_3} xˉ=−a1/2a2=21(x2−x3)f1+(x3−x1)f2+(x1−x2)f3(x22−x32)f1+(x32−x12)f2+(x12−x22)f3
将其进行化简,可得另一种乘除计算量小的运算表达式:
{ x ˉ = − a 1 / 2 a 2 = 1 2 ( x 1 + x 3 − c 1 c 2 ) c 1 = f 1 − f 3 x 1 − x 3 , c 2 = f 1 − f 2 x 1 − x 2 − c 1 x 2 − x 3 \begin{cases} \bar{x}=-a_1/2a_2=\frac{1}{2}\left( x_1+x_3-\frac{c_1}{c_2} \right)\\ c_1=\frac{f_1-f_3}{x_1-x_3},\,\,c_2=\frac{\frac{f_1-f_2}{x_1-x_2}-c_1}{x_2-x_3}\\ \end{cases} ⎩⎨⎧xˉ=−a1/2a2=21(x1+x3−c2c1)c1=x1−x3f1−f3,c2=x2−x3x1−x2f1−f2−c1
算法步骤:
1、寻找满足如下条件的点,成为两头大中间小的点: x 1 < x 2 < x 3 x_{1}<x_{2}<x_{3} x1<x2<x3, f ( x 1 ) > f ( x 2 ) , f ( x 2 ) < f ( x 3 ) f(x_{1})>f(x_{2}),f(x_{2})<f(x_{3}) f(x1)>f(x2),f(x2)<f(x3)。
2、两头大中间小,可得 a 2 > 0 a_{2}>0 a2>0, 计算 x ˉ = 1 2 ( x 1 + x 3 − c 1 c 2 ) \bar{x}=\dfrac{1}{2}(x_{1}+x_{3}-\dfrac{c_{1}}{c_{2}}) xˉ=21(x1+x3−c2c1),为 P ( x ) P(x) P(x)的极小值点,且 x ˉ ∈ [ x 1 , x 3 ] \bar{x}\in\left[ x_{1},x_{3}\right] xˉ∈[x1,x3]。
3、若 ∣ x 2 − x ˉ ∣ < ε \left| x_2-\bar{x} \right|<\varepsilon ∣x2−xˉ∣<ε,则迭代结束,取 x ∗ = x ˉ x^*=\bar{x} x∗=xˉ,否则在点 x 1 , x 2 , x 3 , x ˉ x_{1},x_{2},x_{3},\bar{x} x1,x2,x3,xˉ中,选取使 f ( x ) f(x) f(x)最小的点作为新的 x 2 x_{2} x2,并使新的 x 1 x_{1} x1, x 3 x_{3} x3各是新的 x 2 x_{2} x2近旁的左右两点,继续进行迭代,直到满足终止准则。
具体练习及程序实现
使用抛物线插值法计算如下问题的近似最优解:
m i n f ( x ) = x 3 − 2 x + 1 min\,\,f\left( x \right) =x^3-2x+1 minf(x)=x3−2x+1
设初始搜索区间 [ a , b ] \left[ a,b \right] [a,b]= [ 0 , 3 ] \left[ 0,3 \right] [0,3],区间精度取 ε ⩽ 0.01 \varepsilon \leqslant 0.01 ε⩽0.01。
clc; clear; x1 = 0; x2 = 1; x3 = 3; eps = 0.01; f=@(x) x^3 - 2 * x + 1; %创建题目要求匿名函数,方便使用 while 1 f1=f(x1); f2=f(x2); f3=f(x3); a1=2*(f1*(x2-x3)+f2*(x2-x1)+f3*(x1-x2)); a2=(f1*(x2^2-x3^2)+f2*(x2^2-x1^2)+f3*(x1^2-x2^2)); xx=a2/a1; %计算极小值点xx if abs(x2-xx)<eps %下面为具体迭代过程 x=xx; f_x=f(xx); break else if (xx-x1)*(xx-x2)<0 if f(xx)<=f2 x3=x2; x2=xx; else x1=xx; end else if f(xx)<=f2 x1=x2; x2=xx; else x3=xx; end end end end disp(['最优解: x = ',num2str(x)]); disp(['此时: f(x) = ',num2str(f_x)]) %使用disp函数和num2str()进行输出
算法原理及程序实现简单,暂不使用函数模块化方法。
注:程序中使用while 1的原因是下面程序中需要使用break判断迭代的终止,而break只能在for或while循环中使用。
输出结果
运行程序,得到输出结果为:
最优解:x=0.7992 此时:f(x) = -0.0879
今天的文章
matlab 抛物线_抛物线原理通俗理解分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/81067.html