Newton插值法

Aitken逐次插值法虽然具有承袭性的特点，但其插值公式是递推型的，不便于进行理论分析。为此，可以把n次插值多项式改写成升幂的形式：
$$N_n(x)=c_0+c_1(x-x_0)+c_2(x-x)(x-x_1)+\cdots +c_n(x-x_0)(x-x_1)\cdots (x-x_{n-1})\text{\hspace{1em}(10)}$$
其中，$c_0,c_1,c_2,\cdots ,c_n$为待定系数。根据定理1，该多项式是惟一存在的。将插值条件
$$N_n(x_i)=f(x_i)(i=0,1,2,\cdots ,n)$$
代入（10）式中，即可以惟一确定出系数$c_0,c_1,c_2,\cdots ,c_n$，从而得到$N_n(x)$的升幂形式。为了方便计算，在具体计算这些系数之前，先引入差商的概念。

1. 差商的定义与性质

定义3：已知顺序排列的节点$x_0,x_1,x_2,\cdots ,x_{k-1},x_k,\cdots ,x_n$所对应的函数值为$f(x_0),f(x_2),\cdots$。

定义
$$f[x_0,x_k]=\frac{f(x_0)-f(x_k)}{x_0-x_k}(1\le k\le n)$$
函数$f(x)$在点$x_0,x_k$处的一阶差商；

定义
$$f[x_0;x_1,x_k]=\frac{f[x_0,x_1]-f[x_0,x_k]}{x_1-x_k}(2\le k\le n)$$
为函数$f(x)$在点$x_0,x_1,x_k$处的二阶差商；

定义
$$f[x_0,x_1;x_2,x_k]=\frac{f[x_0;x_1,x_2]-f[x_0;x_1,x_k]}{x_2-x_k}(3\le k\le n)$$
为函数$f(x)$在点$x_0,x_1,x_2,x_k$处的三阶差商；

依此类推，定义
$$f[x_0,x_1,\cdots ,x_{k-2};x_{k-1},x_k]=\frac{f[x_0,x_1,\cdots ;x_{k-2},x_{k-1}]-f[x_0,x_1,\cdots ;x_{k-2},x_k]}{x_{k-1}-x_k}\text{\hspace{1em}(11)}$$
为函数$f(x)$在点$x_0,x_1,x_2,\cdots ,x_{k-1},x_k$处的k阶差商。

k阶差商还有另外一种定义方法，即
$$f[x_0,x_1,\cdots ,x_{k-1},x_k]=\frac{f[x_0,x_1,\cdots ,x_{k-1}]-f[x_1,\cdots ,x_{k-1},x_k]}{x_0-x_k}\text{\hspace{1em}(12)}$$
（11）式为第一种格式的差商，（12）式为第二种格式的差商。两者具有完全相同的性质。

差商有如下性质：

（1）k阶差商$f[x_0,x_1,\cdots ,x_k]$是函数值$f(x_0),f(x_1),\cdots ,f(x_n)$的线性组合。即
$$f[x_0,x_1,\cdots ,x_k]=\sum _{i=0}^k\frac{f(x_i)}{(x_i-x_0)(x_i-x_1)\cdots (x_i-x_{i-1})\cdot (x_i-x_{i+1})\cdots (x_i-x_k)}$$
（2）差商的值与节点的排列顺序无关。即
$$f[x_0,x_1,\cdots ,x_k]=f[x_1,x_0,\cdots ,x_k]=\cdots =f[x_k,\cdots ,x_1,x_0]$$
（3）若$f[x,x_0,x_1,\cdots ,x_k]$是x的m次多项式，则$f[x,x_0,x_1,\cdots ,x_k,x_{k+1}]$是x的m-1次多项式。

2.Newton插值公式

为了求出Newton插值多项式
$$N_n(x)=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)+\cdots +c_n(x-x_0)(x-x_1)\cdots (x-x_{n-1})$$
的系数，将$N_n(xi)=f(x_i)(i=0,1,2,\cdots ,n)$按插值节点的顺序逐个代入上式，即：

由$N_n(x_0)=c_0=f(x_0)$，得:$c_0=f(x_0)$

由$N_n(x_1)=f(x_0)+c_1(x_1-x_0)=f(x_1)$，得：
$$c_1=\frac{f(x_1)-f(x_0)}{(x_1-x_0)}=\frac{f(x_0)-f(x_1)}{(x_0-x_1)}=f[x_0,x_1]$$
由$N_n(x_2)=f(x_0)+f[x_0,x_1](x_2-x_0)+c_2(x_2-x_0)(x_2-x_1)=f(x_2)$，得：
$$c_2=\frac{f(x_2)-f(x_0)-f[x_0,x_1](x_2-x_0)}{(x_2-x_0)(x_2-x_1)}=\frac{\frac{f(x_2)-f(x_0)}{(x_2-x_0)}-f[x_0,x_1]}{(x_2-x_1)}=\frac{f[x_0,x_1]-f[x_0,x_2]}{(x_1-x_2)}=f[x_0,x_1,x_2]$$
依次类推，可由差商的定义和数学归纳法得出全部系数，即：
$$c_k=f[x_0,x_1,\cdots ,x_k],(k=0,1,2,\cdots ,n)$$
这样就得到了Newton插值公式：
$$N_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0;x_1,x_2](x-x_0)(x-x_1)+\cdots +f[x_0,x_1,\cdots ,x_n](x-x_0)(x-x_1)\cdots (x-x_{n-1})$$
用Newton插值法构造插值多项式，只需计算各个节点间的各阶差商即可。由于各阶差商的计算具有递推规律。因此，将各阶差商排列在一起，组成差商表。第一种、第二种格式的差商表分别见下表：

3. 插值余项

如果把插值点x看成是$[a,b]$上的一固定点，由一阶差商定义，有：
$$f(x)=f(x_0)+f[x_0,x](x-x_0)$$
由二阶差商定义，有：
$$f[x_0,x]=f[x_0,x_1]+f[x_0;x_1,x](x-x_1)$$
由三阶差商定义，有：
$$f[x_0;x_1,x]=f[x_0;x_1,x_2]+f[x_0,x_1;x_2,x](x-x_2)$$
依次类推，有：
$$f[x_0,x1,\cdots ,x_{n-1},x]=f[x_0,x_1,\cdots ,x_n]+f[x_0,x_1,\cdots ;x_n,x](x-x_n)$$
将后一等式逐项代入前一等式，得：
$$\begin{gathered} f(x)=f(x_0)+f[x_0,x_1](x-x_0)+\cdots +f[x_0,x_1,\cdots ,x_n](x-x_0)(x-x_1)\cdots (x-x_{n-1})+f[x_0,x_1,\cdots ;x_n,x](x-x_0)(x-x_1)\cdots (x-x_n) \\ =N_n(x)+R_n(x) \end{gathered}$$
其中，
$$R_n(x)=f[x_0,x_1,\cdots ,x_n,x](x-x_0)(x-x_1)\cdots (x-x_n)$$
称为Newton插值的余项。

由于对相同插值节点，插值多项式是惟一的，所以，Newton插值多项式与Lagrange插值多项式是等价的。同样，两者的余项也是等价的。因此，当$f^{(n+1)}(x)$存在时，有：

$$f[x_0,x_1,\cdots ,x_n,x]=\frac{f^{(n+1)}(\xi )}{(n+1)!}$$