Aitken（埃特金）逐次插值法 | 一次插值、二次插值、k次插值

Aitken（埃特金）逐次插值法

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

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

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

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

1. 一次插值（线性插值）

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

2. 二次插值

顺序给出两个插值节点$x_0,x_1$x0​,x1​，再新增加一个节点$x_i(i\geq 2)$xi​(i≥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)$fk​(xi​)=(x0​−x1​)(x0​−x2​)(x−x1​)(x−x2​)​f(x0​)+(x1​−x0​)(x1​−x2​)(x−x0​)(x−x2​)​f(x1​)+(x2​−x0​)(x2​−x1​)(x−x0​)(x−x1​)​f(x2​)
若取i=2，则表示以$x_0,x_1$x0​,x1​和$x_2$x2​为节点进行二次插值，其结果为：
$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)$f2​(x2​)=(x0​−x1​)(x0​−x2​)(x−x1​)(x−x2​)​f(x0​)+(x1​−x0​)(x1​−x2​)(x−x0​)(x−x2​)​f(x1​)+(x2​−x0​)(x2​−x1​)(x−x0​)(x−x1​)​f(x2​)
若取i=3，则表示以$x_0，x_1$x0​，x1​和$x_3$x3​为节点进行二次插值，其结果为：
$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)$f2​(x3​)=(x0​−x1​)(x0​−x3​)(x−x1​)(x−x3​)​f(x0​)+(x1​−x0​)(x1​−x3​)(x−x0​)(x−x3​)​f(x1​)+(x3​−x0​)(x2​−x1​)(x−x0​)(x−x3​)​f(x3​)
整理$f_2(x_2)$f2​(x2​)得：
$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)$f2​(x2​)=x1​−x2​x−x2​​f1​(x1​)+x2​−x1​x−x1​​f1​(x2​)
同理
$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)$f2​(xi​)=x1​−xi​x−xi​​f1​(x1​)+xi​−x1​x−x1​​f1​(xi​)
由此可得出如下结论：$f_2(x_i)$f2​(xi​)表示取固定节点$x_1$x1​和变化节点$x_i(i\geq k)$xi​(i≥k)及其相应的$f_1(x_1)，f_1(x_i)$f1​(x1​)，f1​(xi​)进行线性插值，得到关于x的2次多项式。

3. k次插值

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

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

Aitken逐次插值法的特点是：

（1）将一个高次插值过程归结为线性插值的多次重复。

（2）插值表中的每个数据均为插值结果，从这些数据的一致程度可判断插值结果的精度，如果未达到精度要求，则在增加一个节点进行插值，直至满意为止。