Newton 插值

每添加一个新的插值节点后，使用 Lagrange 插值都需要重新计算所有的 Lagrange 基函数，计算量较大。而使用 Newton 插值则只需要计算新增的插值节点对应的基函数，可以有效减少计算量。

差商

介绍 Newton 插值之前，需要先介绍差商的概念。

• 一阶差商指的是函数值的差除以自变量的差；
• 二阶差商指的是一阶差商的差除以自变量的差；
• ……
• $k$ 阶差商指的是 $k-1$ 阶差商的差除以自变量的差。

差商定义为：

$$\begin{array}{rl}f[x_0]& =f(x_0)\\ f[x_0,x_1]& =\frac{f[x_1]-f[x_0]}{x_1-x_0}\\ f[x_0,x_1,x_2]& =\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}\\ & ⋮\\ f[x_0,x_1,\dots ,x_n]& =\frac{f[x_1,\dots ,x_n]-f[x_0,x_1,\dots ,x_{n-1}]}{x_n-x_0}\end{array}$$

差商的重要性质：

1. 节点顺序不影响其大小，即 $f[x_0,x_1,x_2,\dots ,x_n]=f[x_n,x_1,x_2,\dots ,x_0]$。
2. $f[x_0,x_1,x_2,\dots ,x_n]=\frac{f^{(n)}(\xi )}{n!}$，$\xi$ 为 $[a,b]$ 上的某个数。

插值函数

已知 $n+1$ 个节点时，$n$ 次 Newton 插值方法：

$$\begin{array}{rl}p(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})\\ =& 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})\end{array}$$

在实际计算时，计算差商一般会使用差商表：

$x$	$f(x)$	一阶差商	二阶差商	三阶差商	$\cdots$
$x_0$	$f(x_0)$
$x_1$	$f(x_1)$	$f[x_0,x_1]$
$x_2$	$f(x_2)$	$f[x_1,x_2]$	$f[x_0,x_1,x_2]$
$x_3$	$f(x_3)$	$f[x_2,x_3]$	$f[x_1,x_2,x_3]$	$f[x_0,x_1,x_2,x_3]$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

《计算方法》是一门重视计算的学科，使用差商表列表计算可以高效计算出各差商。位于对角线的差商就是 Newton 插值对应的系数。