简介

牛顿插值是多项式插值的一种，即通过 $n+\phantom{0}$$\phantom{0}1$ 个插值节点构造 $n$ 次插值多项式

$$P(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_n{x}^n$$$$P(x_i)=y_i,i=0,1,\cdots ,n$$

对于拉格朗日插值，每新增一个插值节点，都要重算所有插值基函数。而牛顿插值能够实现「增量更新」，无需推倒重来。

基本思想

当追加 $(x_k,\phantom{0}$$\phantom{0}{y}_k)$ 时，给原先的插值多项式 $P(x)$ 加上一个多项式

$$a_k\cdot (x-x_0)(x-x_1)\cdots (x-x_{k-1})$$

以上多项式在代入 $x=\phantom{0}$$\phantom{0}{x}_0,\phantom{0}$$\phantom{0}{x}_1,\phantom{0}$$\phantom{0}\cdots ,\phantom{0}$$\phantom{0}{x}_{k-1}$ 时均为 $0$，也就是保持了原先的插值结果；待定系数 $a_k$ 的值通过方程 $P(x_k)=\phantom{0}$$\phantom{0}{y}_k$ 解出。

现用多项式 $P(x)$ 近似 $f(x)$，并依次追加插值节点：

1. 追加 $(x_0,\phantom{0}$$\phantom{0}{y}_0)$，此时构造 $P(x)=\phantom{0}$$\phantom{0}{a}_0$，其中 $a_0=\phantom{0}$$\phantom{0}{y}_0$；
2. 追加 $(x_1,\phantom{0}$$\phantom{0}{y}_1)$，此时更新 $P(x)=\phantom{0}$$\phantom{0}{a}_0+\phantom{0}$$\phantom{0}{a}_1(x-\phantom{0}$$\phantom{0}{x}_0)$，其中 $a_1=\phantom{0}$$\phantom{0}{\displaystyle \frac{y_1-y_0}{x_1-x_0}}$；
3. 追加 $(x_2,\phantom{0}$$\phantom{0}{y}_2)$，此时更新 $P(x)=\phantom{0}$$\phantom{0}{a}_0+\phantom{0}$$\phantom{0}{a}_1(x-\phantom{0}$$\phantom{0}{x}_0)+\phantom{0}$$\phantom{0}{a}_2(x-\phantom{0}$$\phantom{0}{x}_0)(x-\phantom{0}$$\phantom{0}{x}_1)$，其中 $a_2=\phantom{0}$$\phantom{0}{\displaystyle \frac{{\displaystyle \frac{y_2-y_0}{x_2-x_0}}-{\displaystyle \frac{y_1-y_0}{x_1-x_0}}}{x_2-x_1}}$；
4. $\cdots$

容易看出，待定系数 $a_k$ 的形式符合某一规律，且其复杂性随规模的增大而增大。

差商

一阶差商 $f[x_0,\phantom{0}$$\phantom{0}{x}_1]$

$$f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}$$

二阶差商 $f[x_0,\phantom{0}$$\phantom{0}{x}_1,\phantom{0}$$\phantom{0}{x}_2]$

$$\begin{array}{rl}f[x_0,x_1,x_2]& =\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_1}\\ & =\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}\end{array}$$

k 阶差商 $f[x_0,\phantom{0}$$\phantom{0}\cdots ,\phantom{0}$$\phantom{0}{x}_k]$

$$\begin{array}{rl}f[x_0,\cdots ,x_k]& =\frac{f[x_0,\cdots ,x_{k-2},x_k]-f[x_0,\cdots ,x_{k-1}]}{x_k-x_{k-1}}\\ & =\frac{f[x_1,\cdots ,x_k]-f[x_0,\cdots ,x_{k-1}]}{x_k-x_0}\end{array}$$

性质 1

k 阶差商可表示为 $f(x_0),\phantom{0}$$\phantom{0}f(x_1),\phantom{0}$$\phantom{0}\cdots ,\phantom{0}$$\phantom{0}f(x_k)$ 的线性组合。

$$f[x_0,\cdots ,x_k]=\sum _{i=0}^k\frac{f(x_i)}{\prod _{\begin{array}{c}j=0\\ j\ne i\end{array}}^k(x_i-x_j)}$$

性质 2（对称性）

差商是顺序不敏感的。

$$f[\cdots ,x_i,x_{i+1},\cdots ]=f[\cdots ,x_{i+1},x_i,\cdots ]$$

性质 3

若 $f(x)$ 在 $[a,\phantom{0}$$\phantom{0}b]$ 上存在 $n$ 阶导数，且 $x_0,\phantom{0}$$\phantom{0}{x}_1,\phantom{0}$$\phantom{0}\cdots ,\phantom{0}$$\phantom{0}{x}_n\in [a,\phantom{0}$$\phantom{0}b]$，则

$$f[x_0,\cdots ,x_n]=\frac{f^{(n)}(\xi )}{n!},\xi \in (a,b)$$

性质 1：证

采用数学归纳法。

$k=\phantom{0}$$\phantom{0}1$ 时命题显然成立。

$$f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}=\frac{f(x_1)}{x_1-x_0}+\frac{f(x_0)}{x_0-x_1}$$

$k>1$ 时，假设原命题对 $k-\phantom{0}$$\phantom{0}1$ 成立，则

$$\begin{array}{rl}f[x_0,\cdots ,x_k]& =\frac{f[x_1,\cdots ,x_k]-f[x_0,\cdots ,x_{k-1}]}{x_k-x_0}\\ & =\frac{{\displaystyle \sum _{i=1}^k\frac{f(x_i)}{\prod _{\begin{array}{c}j=1\\ j\ne i\end{array}}^k(x_i-x_j)}-\sum _{i=0}^{k-1}\frac{f(x_i)}{\prod _{\begin{array}{c}j=0\\ j\ne i\end{array}}^{k-1}(x_i-x_j)}}}{x_k-x_0}\\ & =\frac{{\displaystyle \sum _{i=0}^k(x_i-x_0)\frac{f(x_i)}{\prod _{\begin{array}{c}j=0\\ j\ne i\end{array}}^k(x_i-x_j)}-\sum _{i=0}^k(x_i-x_k)\frac{f(x_i)}{\prod _{\begin{array}{c}j=0\\ j\ne i\end{array}}^k(x_i-x_j)}}}{x_k-x_0}\\ & =\frac{{\displaystyle \sum _{i=0}^k(x_k-x_0)\frac{f(x_i)}{\prod _{\begin{array}{c}j=0\\ j\ne i\end{array}}^k(x_i-x_j)}}}{x_k-x_0}\\ & =\sum _{i=0}^k\frac{f(x_i)}{\prod _{\begin{array}{c}j=0\\ j\ne i\end{array}}^k(x_i-x_j)}\end{array}$$

即原命题对 $k$ 成立。

因此原命题在 ${\mathbb{Z}}^{+}\phantom{0}$$\phantom{0}$ 上成立。

性质 2：证

由性质 1 有

$$f[\cdots ,x_i,x_{i+1},\cdots ]=\sum _h\frac{f(x_h)}{\prod _{j\ne h}(x_h-x_j)}=f[\cdots ,x_{i+1},x_i,\cdots ]$$

性质 3：证

已知拉格朗日插值多项式

$$L_n(x)=\sum _{k=0}^{n}f(x_k)\cdot {\ell }_k(x),{\ell }_k(x)=\prod _{\begin{array}{c}i=0\\ i\ne k\end{array}}^n\frac{x-x_i}{x_k-x_i}$$

和拉格朗日插值余项的定义式

$$R_n(x)=f(x)-L_n(x)$$

注意到 $R_n(x)$ 有共 $n+\phantom{0}$$\phantom{0}1$ 个互异零点 $x_0,\phantom{0}$$\phantom{0}{x}_1,\phantom{0}$$\phantom{0}\cdots ,\phantom{0}$$\phantom{0}{x}_n$。

根据罗尔（Rolle）定理有

• $R_n^{\prime }(x)$ 在 $(a,\phantom{0}$$\phantom{0}b)$ 上有 $n$ 个零点；
• $R_n^{″}(x)$ 在 $(a,\phantom{0}$$\phantom{0}b)$ 上有 $n-\phantom{0}$$\phantom{0}1$ 个零点；
• $\cdots$
• $R_n^{(n)}(x)$ 在 $(a,\phantom{0}$$\phantom{0}b)$ 上有 $1$ 个零点。

即存在 $\xi \in (a,\phantom{0}$$\phantom{0}b)$ 使得

$$R_n^{(n)}(\xi )=f^{(n)}(\xi )-L_n^{(n)}(\xi )=0$$

又因为 ${\ell }_k(x)$ 的最高项 $x^n$ 的系数为 $\prod _{\begin{array}{c}i=0\\ i\ne k\end{array}}^n{\displaystyle \frac{1}{x_k-x_i}}$，结合性质 1 有

$$L_n^{(n)}(\xi )=n!\sum _{k=0}^{n}f(x_i)\prod _{\begin{array}{c}i=0\\ i\ne k\end{array}}^n{\displaystyle \frac{1}{x_k-x_i}}=n!\cdot f[x_0,\cdots ,x_k]$$

故

$$f^{(n)}(\xi )-n!\cdot f[x_0,\cdots ,x_k]=0$$$$f[x_0,\cdots ,x_k]=\frac{f^{(n)}(\xi )}{n!}$$

差商表

$x_k$	$f(x_k)$	一阶差商	二阶差商	三阶差商	四阶差商
$x_0$	$f(x_0)$
$x_1$	$f(x_1)$	$f[x_0,\phantom{0}$$\phantom{0}{x}_1]$
$x_2$	$f(x_2)$	$f[x_1,\phantom{0}$$\phantom{0}{x}_2]$	$f[x_0,\phantom{0}$$\phantom{0}{x}_1,\phantom{0}$$\phantom{0}{x}_2]$
$x_3$	$f(x_3)$	$f[x_2,\phantom{0}$$\phantom{0}{x}_3]$	$f[x_1,\phantom{0}$$\phantom{0}{x}_2,\phantom{0}$$\phantom{0}{x}_3]$	$f[x_0,\phantom{0}$$\phantom{0}{x}_1,\phantom{0}$$\phantom{0}{x}_2,\phantom{0}$$\phantom{0}{x}_3]$
$x_4$	$f(x_4)$	$f[x_3,\phantom{0}$$\phantom{0}{x}_4]$	$f[x_2,\phantom{0}$$\phantom{0}{x}_3,\phantom{0}$$\phantom{0}{x}_4]$	$f[x_1,\phantom{0}$$\phantom{0}{x}_2,\phantom{0}$$\phantom{0}{x}_3,\phantom{0}$$\phantom{0}{x}_4]$	$f[x_0,\phantom{0}$$\phantom{0}{x}_1,\phantom{0}$$\phantom{0}{x}_2,\phantom{0}$$\phantom{0}{x}_3,\phantom{0}$$\phantom{0}{x}_4]$

牛顿插值

n 次牛顿插值多项式 $N_n(x)$

$$N_n(x)=f(x_0)+\sum _{k=1}^{n}f[x_0,\cdots ,x_k]\prod _{i=0}^{k-1}(x-x_i)$$

容易由数学归纳法证明 $N_n(x)$ 是正确的插值多项式。

一次牛顿插值多项式 $N_1(x)$

$$N_1(x)=f(x_0)+f[x_0,x_1](x-x_0)$$

二次牛顿插值多项式 $N_2(x)$

$$N_2(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)$$

牛顿插值余项

由多项式插值定理得，同一条件下的牛顿插值多项式 $N_n(x)$ 和拉格朗日插值多项式 $L_n(x)$ 相同，故余项也相同。

$$R_n(x)=f(x)-N_n(x)=f(x)-L_n(x)$$

详见拉格朗日插值余项。