二次插值法的迭代步骤详解

图9-6 二次插值函数

1.构造三点二次插值多项式并求其极值

如图9-6所示，设[a，b]是函数f（x）具有唯一极小点的单峰区间。在该区间内取三点x₁=a、x₁＜x₂＜x₃、x₃=b，并计算三点函数值f₁=f（x₁）、f₂=f（x₂）、f₃=f（x₃）。记三点二次插值多项式的一般形式为φ（x）=p₁x²+p₂x+p₃，因φ（x）过点（x₁，f₁）、（x₂，f₂）和（x₃，f₃），式中待定系数p₁、p₂、p₃按插值理论由下面的方程组确定：

式中x₁、x₂、x₃和f₁、f₂、f₃已知，因此可解出p₁、p₂、p₃，从而得到所需的二次多项式φ（x）。

令二次多项式φ（x）的一阶导数等于零，求φ（x）的极小点x_φ^*，即令

得

将系数p₁、p₂代入上式，则

为简化起见，令

及(www.xing528.com)

则有

检验收敛准则|x_φ^*-x₂|≤ε？若满足则用x_φ^*代替原函数的最优点，即x^*=x_φ^*，输出最优解x^*、f^*=f（x^*）=f_φ。若不满足则应缩短区间后重复上面的迭代过程。

2.区间的缩短

区间的缩短是在保证函数值两头大、中间小的前提下，在x₁、x₂、x₃和x_φ^*四点中取三点构成新的区间，同时做符号置换。共有4种情况，分述如下：

1）如图9-7a所示，x_ϕ^*＞x₂，f_ϕ＞f₂，则应去掉区间（x_ϕ^*，x₃]，作符号置换：x₃=x_ϕ^*，f₃=f_ϕ。

2）如图9-7b所示，x_ϕ^*＞x₂，f_ϕ＜f₂，则应去掉区间[x₁，x₂），作符号置换：x₁=x₂，f₁=f₂，x₂=x_ϕ^*，f₂=f_ϕ。

3）如图9-7c所示，x_ϕ^*＜x₂，f_ϕ＜f₂，则应去掉区间（x₂，x₃]，作符号置换：x₃=x₂，f₃=f₂，x₂=x_ϕ^*，f₂=f_ϕ。

4）如图9-7d所示，x_ϕ^*＜x₂，f_ϕ＞f₂，则应去掉区间[x₁，x_ϕ^*]，作符号置换：x₁=x_ϕ^*，f₁=f_ϕ。

通过上述置换，即得到新的被缩短的区间[x₁，x₃]及三个插值点（x₁，f₁）、（x₂，f₂）、（x₃，f₃），可以重新构造插值多项式和继续求优迭代。

图9-7 二次插值法的区间缩短