Aitken（埃特金）逐次插值法

本文主要是介绍Aitken（埃特金）逐次插值法 | 一次插值、二次插值、k次插值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断离散数据 $(x_i,y_i)(i=0,1,2,\cdots,n)$ 的插值精度，既可以采用事后误差估计的方法，也可以在插值点x的附近选取部分数据进行插值，然后再增加一些插值节点进行插值。若两次的插值结果之差小于规定的误差，则可认为插值精度复合要求而停止。这种在插值计算精度不够时增加节点（插值多项式的次数一般不宜超过6~8次）以提高插值精度方法就是所谓的逐次插值法。

在上述情况中，运用Lagrange插值方法存在一个明显缺点，就是当插值节点发生变化和增加时，Lagrange插值公式中的所有基函数都得重新计算，即计算量大。由于插值节点发生变化和增加只是个别节点，因此只对发生变化和增加的结点进行计算以减小计算量十分重要。

Aitken逐次插值法就是一种可以灵活地增加插值节点数，在前面计算结果的基础上继续进行计算而不必重新开始计算的方法。可见，Aitken逐次插值法具有承袭性的特点。

先约定表示插值结果的符号，设在插值区间 $[a, b]$ 上，有n+1个顺序排列的插值节点 $x_0,\cdots,x_k,\cdots,x_n$ ，插值点为x。由前k个顺序排列的插值节点 $x_0,x_1,\cdots,x_{k-1}$ 构成的插值函数是x的k-1次多项式，可以用 $f(x_0,\cdots,x_{k-1};x_{k-1})$ 表示，简记为 $f_{k-1}(x_{k-1})$ 。在上述k个插值节点 $x_0,x_1,\cdots,x_{k-1}$ 的后面，再顺序增加一个新插值节点 $x_i(i\geq k)$ ，进行k次插值。其插值函数是x的k次多项式，用 $f(x_0,\cdots,x_{k-1};x_k)$ 表示，简记为 $f_k(x_i)$ ，其中k表示插值次数， $x_k$ 为新增加的插值节点。在简记符号 $f_k(x_i)$ 中，k个顺序排列插值节点 $x_0,x_1,\cdots,x_{k-1}$ 中的最后一个节点 $x_{k-1}$ ，由 $f_k(x_i)$ 下标k隐含地给出。

一次插值（线性插值）

首先给出一个固定插值节点 $x_0$ 及其函数值 $f(x_0)$ ，再新增加一个节点 $x_i(i\geq 1)$ （自然同时也给出其函数值 $f(x_i)$ ），用这两个插值节点进行线性插值，其结果为：
$f_1(x_i)=\frac{x-x_i}{x_0-x_i}f(x_0)+\frac{x-x_0}{x_i-x_0}f(x_i) \quad (i\geq 1)$
若取 $i = 1$ ，则表示以 $x_0,x_1$ 为节点进行一次插值，结果为：
$f_1(x_1)=\frac{x-x_1}{x_0-x_1}f(x_0)+\frac{x-x_0}{x_1-x_0}f(x_1)$
若取 $i = 2$ ，则表示以 $x_0$ 和 $x_2$ 为节点进行一次插值，结果为：
$f_1(x_2)=\frac{x-x_2}{x_0-x_2}f(x_0)+\frac{x-x_0}{x_2-x_0}f(x_2)$
由此可得出如下结论： $f_1(x_i)$ 表示取固定节点 $x_0$ 和变化节点 $x_i(i\geq 1)$ 及其相应的 $f(x_0),f(x_1)$ 进行线性插值，得到关于x的一次多项式。

二次插值

顺序给出两个插值节点 $x_0,x_1$ ，再新增加一个节点 $x_i(i\geq 2)$ ，用这3个插值节点进行插值，其结果为：
$f_k(x_i)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}f(x_0)+\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}f(x_1)+\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}f(x_2)$
若取i=2，则表示以 $x_0,x_1$ 和 $x_2$ 为节点进行二次插值，其结果为：
$f_2(x_2)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}f(x_0)+\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}f(x_1)+\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}f(x_2)$
若取i=3，则表示以 $x_0，x_1$ 和 $x_3$ 为节点进行二次插值，其结果为：
$f_2(x_3)=\frac{(x-x_1)(x-x_3)}{(x_0-x_1)(x_0-x_3)}f(x_0)+\frac{(x-x_0)(x-x_3)}{(x_1-x_0)(x_1-x_3)}f(x_1)+\frac{(x-x_0)(x-x_3)}{(x_3-x_0)(x_2-x_1)}f(x_3)$
整理 $f_2(x_2)$ 得：
$f_2(x_2)=\frac{x-x_2}{x_1-x_2}f_1(x_1)+\frac{x-x_1}{x_2-x_1}f_1(x_2)$
同理
$f_2(x_i)=\frac{x-x_i}{x_1-x_i}f_1(x_1)+\frac{x-x_1}{x_i-x_1}f_1(x_i)$
由此可得出如下结论： $f_2(x_i)$ 表示取固定节点 $x_1$ 和变化节点 $x_i(i\geq k)$ 及其相应的 $f_1(x_1)，f_1(x_i)$ 进行线性插值，得到关于x的2次多项式。

k次插值

根据以上分析，可以推出如下结论：用两个 $k - 1$ 次插值的结果 $f_{k-1}(x_{k-1})$ 和 $f_{k-1}(x_i)$ ，进行线性插值，即可得到k次插值的结果 $f_k(x_i)$ 。即：

$f_k(x_i)$ 表示固定节点 $x_{k-1}$ 和变化节点 $x_i(i\geq k)$ 及其相应的 $f_{k-1}(x_{k-1}),f_{k-1}(x_i)$ 进行线性插值，从而得到关于x的k次多项式：
$f_k(x_i)=\frac{x-x_i}{x_{k-1}-x_i}f_{k-1}(x_{k-1})+\frac{x-x_{k-1}}{x_i-x_{k-1}}f_{k-1}(x_i), \quad (i\geq k) \tag{10}$
根据（10）式，可以计算出当 $k=1,2,\cdots,n(i=k,k+1,\cdots,n)$ 时的 $f_k(x_i)$ ，由于计算 $f_k(x_i)$ 有很强的规律性，故将其排列成下表所示，该表称为Aitken插值表。从表中可以看出， $f_k(x_i)$ 是逐列计算出来的。这种足部提高插值次数以获得更高精度插值结果的插值方法称为Aitken逐次插值方法。