插值法(二次插值法和三次插值法算法分析以及python代码解释) |
您所在的位置:网站首页 › 样条插值法和最小二乘插值 › 插值法(二次插值法和三次插值法算法分析以及python代码解释) |
在学习了之前几期一维搜索算法后,今天我们来分析两种最新的算法,分别是两点三次插值法和两点插值法。之前的几种算法,在整个搜索过程中只对函数值进行了比较,在删除“坏”的区间时,已经计算出的函数值并没有得到充分的利用。今天介绍的两种方法是利用低次多项式P(x)在搜索区间上逼近目标函数,然而用近似多项式P(x)的极小点作为新区间的分割点的方法。近似多项式P(x)取二次多项式,则得二次插值法;取三次多项式,则得三次插值法。 二次插值法: 算法分析:基本思想:在极小点附近,用二次三项式P(x)逼近目标函数 令 又令 记
则可得: 令 这样,把 下面我们通过例题来进一步探讨: 例题:用二次插值法求函数 解:由已知三个点,可求出(-1.2,-4.1472),(-1.1,-4.8037),(-0.8,-4.4032) 由迭代公式:
那么我们看这个迭代结果,不难发现,求出的极小点是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 总结:二次插值法的优点在于对于局部最优解迭代速度较快,但是缺点也较明显,对于选定的三点,要求较高,有时求出的不是全局最高解而是局部最优解。 三次插值法: 算法分析:基本思想:首先选取两个初始点 令 满足: 代入可得: 解上述方程组,可求出系数a,b,c,d,从而确定三次多项式函数 求P(x)的极小点,由极小点的必备条件,既求满足 由 令 解方程,有两种情形: (1)当a=0时, (2)当a 第一种情况下,由假设 因此 第二种情况下,代入,由 要使 故两种情况,极小点可以统一写成 记:
可推断出: 继续推导: 代入得: 又将等式右端上下同时乘以 将两个式子相加,我们可以得到: 化简为: 其中, 下面我们通过例题来进一步加深对算法的理解, 例题:用三次插值法求解下列问题: 解: ∴ 经过一次迭代,就可以达到最优解。 算法代码: ''' 三次插值算法 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,一般认为要优于二次插值法。 算法比较:从上面的一些例子,不难看出:在一维搜索方法中,利用导数的算法一般优于不利于导数的直接法,比如两分法,牛顿切线法,三次插值法优于成功—失败法,黄金分割算法和二次插值法;利用二阶导数的算法优于利用一阶导数的算法,如牛顿切线法优于二分法,当然也不尽然。 (行文中若有纰漏,希望大家指正) |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |