漫步最优化二十八——三次插值法

没有你的世界，
我会灵魂失控。
没有你的世界，
我被乌云拖着走。
没有你的世界，
我的世界一直狂风暴雨。
我不能承受没有你的世界，
因为我已经习惯有你的节奏。
其实我的愿望很小，
那就是每天看到你的微笑。
——畅宝宝的傻逼哥哥

另一个一维优化方法是三次插值法，它是基于三阶多项式

p (x) = a 0 + a 1 x + a 2 x 2 + a 3 x 3

与二次插值法一样，我们需要确定系数ai使得p(x)在某些点的值以及(或者)导数与f(x)的值以及(或者)导数相等，因为三阶不等式有四个系数，所以我们需要四个等式，选择不等式的方式有许多，因此三次插值的形式也有许多。

p(x)的图像可以是图1中的任何一个，显然，p(x)有一个极大值，还有一个极小值。令p(x)的一阶导等于零，即

p' (x) = a 1 + 2 a 2 x + 3 a 3 x 2 = 0

然后求解x，可以得出p(x)的极值点为

x = 1 3 a 3 (- a 2 \pm a 22 - 3 a 1 a 3 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt)

在极小点x¯处，p(x)的二阶导数为正，所以

p ″ (x ¯) = 2 a 2 + 6 a 3 x ¯ > 0

或者

x ¯ > - a 2 3 a 3

从而可以选出p(x)对应的极小值。

如果选择的四个等式是独立的，那么多项式p(x)将是f(x)的近似。我们令

p (x i) = a 0 + a 1 x i + a 2 x i 2 + a 3 x 3 i = f (x i)

其中i=1,2,3且

p' (x 1) = a 1 + 2 a 2 x 1 + 3 a 3 x 21 = f' (x 1)

通过求解上面的等式，可以确定a1,a3为

a 3 a 2 a 1 = β - γ θ - φ = β - θ a 3 = f' (x 1) - 2 a 2 x 1 - 3 a 3 x 21

其中

β γ θ φ = f (x 2) - f (x 1) + f' (x 1) (x 1 - x 2) (x 1 - x 2) 2 = f (x 3) - f (x 1) + f' (x 1) (x 1 - x 3) (x 1 - x 3) 2 = 2 x 21 - x 2 (x 1 + x 2) (x 1 - x 2) = 2 x 21 - x 3 (x 1 + x 3) (x 1 - x 3)

根据这些系数值可以得出最小值x¯。

图1