在学习了之前几期一维搜索算法后，今天我们来分析两种最新的算法，分别是两点三次插值法和两点插值法。之前的几种算法，在整个搜索过程中只对函数值进行了比较，在删除“坏”的区间时，已经计算出的函数值并没有得到充分的利用。今天介绍的两种方法是利用低次多项式P（x）在搜索区间上逼近目标函数，然而用近似多项式P（x）的极小点作为新区间的分割点的方法。近似多项式P（x）取二次多项式，则得二次插值法；取三次多项式，则得三次插值法。

二次插值法：

算法分析:

基本思想：在极小点附近，用二次三项式P（x）逼近目标函数,P（x）与在三点有相同的函数值，并假设：

令                                                      ,

又令                                          

记                ,,

,,

则可得：

令,将P(x)的驻点x记作,则

这样，把作为的极小点的一个估计，再从中选择目标函数值最小的点，以及其左右两点，给予相应的下标，代入上式，求出极小点的新的估计值，以此类推，产生点列{}，满足或者，终止迭代。

例题分析：

下面我们通过例题来进一步探讨：

例题：用二次插值法求函数的极小点，迭代三次给定.

解：由已知三个点，可求出（-1.2，-4.1472），（-1.1，-4.8037），（-0.8，-4.4032）

由迭代公式：

,,

,,

迭代次数
第一次	x	-1.2	-1.1	-0.8	-0.984
	f	-4.147	-4.804	-4.403	-4.996
第二次	x	-1.1	-0.984	-0.8	-0.990
	f	-4.804	-4.996	-4.403	-4.998
第三次	x	-1.1	-0.990	-0.984	-1.008
	f	-4.804	-4.998	-4.996	-4.999

那么我们看这个迭代结果，不难发现，求出的极小点是x=-1的近似值，并不是问题的全局最优解（x=2），由此，我们可以确定二次插值法对于初始点的要求较高，有时求出的并不是全局最优解，而是局部最优解。

---

算法代码：

'''
二次插值算法(抛物线法）
2023.10.9
'''


def fun(x):
    return x ** 2 + 2 * x - 10
def run(x1, x2, x3):
    B1 = (x2 * x2 - x3 * x3) * fun(x1)
    B2 = (x3 * x3 - x1 * x1) * fun(x2)
    B3 = (x1 * x1 - x2 * x2) * fun(x3)
    C1 = (x2 - x3) * fun(x1)
    C2 = (x3 - x1) * fun(x2)
    C3 = (x1 - x2) * fun(x3)
    D = (x1 - x2) * (x2 - x3) * (x3 - x1)
    if (B1 + B2 + B3) == 0:
        x0 = 0
    else:
        x0 = (B1 + B2 + B3) / (2 * (C1 + C2 + C3))
    Arr = [x0, x1, x2, x3]
    Arr.sort()
    if fun(x0) > fun(x2):
        index = Arr.index(x2)
        x1 = Arr[index - 1]
        x3 = Arr[index + 1]
    else:
        index = Arr.index(x0)
        x2 = x0
        x1 = Arr[index - 1]
        x3 = Arr[index + 1]
    return x1, x2, x3
def text(x1, x2, x3, ε):
    count = 0
    while abs(x3 - x1) and abs(x3 - x2) and abs(x2 - x1) > ε:
        count = count + 1
        print("第{}次迭代".format(count))
        Arr2 = run(x1, x2, x3)
        x1 = Arr2[0]
        x2 = Arr2[1]
        x3 = Arr2[2]
        print(Arr2)
    print("该精度下的最优解为：%f" % x2)
    print("函数在该精度上的最小值为",fun(x2))
    return
text(-3, 0.5, 4, 0.0001)

用该代码所运算的结果为：

第1次迭代
(-3, -1.0, 0.5)
第2次迭代
(-3, -1.0, -1.0)
该精度下的最优解为：-1.000000
函数在该精度上的最小值为 -11.0

总结：

二次插值法的优点在于对于局部最优解迭代速度较快，但是缺点也较明显，对于选定的三点，要求较高，有时求出的不是全局最高解而是局部最优解。

---

三次插值法：

算法分析：

基本思想：首先选取两个初始点,,(<),使得,这样，在区间（，）内存在极小点，然后利用这两点的函数值和导数值，构造一个三次多项式P（x），使它与在,具有相同的函数值和导数值，用P（x)逼近函数,进而用P（x)的极小点估计的极小点。

令                                

满足：            ，，，

代入可得：                                                  

解上述方程组，可求出系数a,b,c,d,从而确定三次多项式函数

求P（x)的极小点，由极小点的必备条件，既求满足的点，

由                  

令,                       

解方程，有两种情形：

（1）当a=0时，

（2）当a0时，

第一种情况下，由假设<0,>0,<

以及，可得b>0,

因此,故是P（x)的极小点。

第二种情况下，代入，由

要使，则取               

故两种情况，极小点可以统一写成            

记：

,,

可推断出：

继续推导：

代入得：

又将等式右端上下同时乘以,得到下式：

将两个式子相加，我们可以得到：

化简为：

其中，成立。由此，可利用，，，就可以求出P（x）的极小点。若充分小，就可以将P（x)的极小点作为的可接受的极小点；否则，可以从,，中确定两个点重复以上过程。

例题分析：

下面我们通过例题来进一步加深对算法的理解，

例题：用三次插值法求解下列问题：,,初始点取

解：                                          ，

∴

经过一次迭代，就可以达到最优解。

---

算法代码：

'''
三次插值算法
2023.10.9
'''
from sympy import *
x = symbols("x")
f_x = x**3-12*x-20

def run(x1,x2,ε):
    count = 0
    # 一阶求导
    first_grad = diff(f_x,x)
    # 判断给定区间内是否存在极小点
    if first_grad.subs({x: x1}) * first_grad.subs({x: x2}) > 0:
        print("该函数在该区间不存在极小点")
    else:
        print("该函数在该区间存在极小点")
        while abs(x2-x1) >= ε:
            count = count+1
            print("第{}次迭代".format(count))
            s = 3*( f_x.subs(x,x2) - f_x.subs(x,x1) )/(x2-x1)
            z = s - first_grad.subs({x: x1})-first_grad.subs({x: x2})
            w = (z * z -first_grad.subs({x: x1})*first_grad.subs({x: x2}))**0.5
            x0 = x1 + (x2-x1)*(1-((first_grad.subs({x: x2}))+w+z)/(first_grad.subs({x: x2})-first_grad.subs({x: x1})+2*w))
            if first_grad.subs({x: x0}) == 0:
                print("该精度下的最优解为：%f"%x0)
                break
            elif first_grad.subs({x: x0}) > 0:
                x1 = x0
            elif first_grad.subs({x: x0}) < 0:
                x2 = x0
        print("该精度下的最优解为：%f" % x0)
        return

run(1,5,0.001)

用该代码所运算的结果为：

该函数在该区间存在极小点
第1次迭代
该精度下的最优解为：2.000000
该精度下的最优解为：2.000000

总结：

三次插值法的收敛阶为2，一般认为要优于二次插值法。

算法比较：

从上面的一些例子，不难看出：在一维搜索方法中，利用导数的算法一般优于不利于导数的直接法，比如两分法，牛顿切线法，三次插值法优于成功—失败法，黄金分割算法和二次插值法；利用二阶导数的算法优于利用一阶导数的算法，如牛顿切线法优于二分法，当然也不尽然。

（行文中若有纰漏，希望大家指正）