Newton 插值

数值分析上的 Newton 插值是一种插值方法，它是基于 Lagrange 插值进行的。

一般插值公式

设有点$(x_i, f(x_i)), i = 0,1,2,\cdots,n$，过这些点的不高于$n$次的多项式通过下式确定：

$$N_n(x) = f(x_0) + \sum_{k=1}^n f[x_0, x_1, \cdots, x_k] (x-x_0) (x-x_1) \cdots (x - x_{k-1})$$

其中，$f[x_0, \cdots, x_k]$是对于节点$x_0, \cdots, x_k$的$k$阶差商，它可以使用差商的递推公式计算每一项。

等距节点公式

当$x_i$等距排列时，上式会大大简化，设$x_i = x_0 + ih, i = 0,1,2,\cdots,n$

主要有以下两种插值公式：

1. 向前插值公式，主要用于左端点附近的插值
   $$N_n(x) = f(x_0) + \sum_{k=1}^n \dfrac{\Delta^k f_0}{k!} t (t-1) \cdots (t-k+1).$$
   其中，$x = x_0 + th.$
2. 向后插值公式，主要用于右端点附近的插值
   $$N_n(x) = f(x_0) + \sum_{k=1}^n \dfrac{\nabla^k f_0}{k!} t (t+1) \cdots (t+k-1).$$
   其中，$x = x_n + th.$

上述符号详见差分。

参考资料

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