Neville 插值

Neville 插值是基于 Lagrange 插值方法发展出来的一种插值方法。它利用两个低次插值多项式经过再次插值后便会得到较高次的插值多项式这一原理。

基本思想

假设$p_{i,k}$表示对样本点$(x_i, y_i), (x_{i+1}, y_{i+1}), \cdots, (x_{i+k}, y_{i+k})$的插值问题的 Lagrange 插值多项式，对于任意的$p_{i, i+1}$会归结于简单的线性插值场合。

而对于$p_{i, j}, p_{i+1, j+1}, p_{i, j+1}$，将$(x_i, p_{i, j}), (x_{j+1}, p_{i+1, j+1})$视做“样本点”，应用线性插值公式

$$p_{i, j+1} = \dfrac{x - x_{j+1}}{x_i - x_{j+1}} p_{i, j} + \dfrac{x - x_i}{x_{j+1} - x_i} p_{i+1, j+1}.$$

这实际上已经可以解决利用低次（线性）插值多项式，经过再次插值得到高次插值多项式了，形象地得到以下的图（以$n=5$为例）

数值功效

该方法的一大特点是可承袭性，可以根据精度要求增加样本点，而计算可以复用之前的数据，例如上图中蓝色部分就是在增加样本点之后需要再做的计算。

参考资料

1. 黄云清, 《数值计算方法》, 科学出版社, 北京, 2012-06, ISBN 978-7-0302-3428-5.