[数学建模算法] (24) 插值和拟合：牛顿插值

最编程 2024-06-30 12:20:16

...

首先需要提出差商，差分的概念和性质

1.差商

定义：设有函数 $f(x), x_{0}, x_{1}, x_{2}, \cdots$ 为一系列互不相等的点，称 $\frac{f\left(x_{i}\right)-f\left(x_{j}\right)}{x_{i}-x_{j}}(i \neq j)$ 为 $f(x)$ 关于点 $x_{i}, x_{j}$ 一阶差商（也称均差）记为 $f\left[x_{i}, x_{j}\right]$ ，即：
$f\left[x_{i}, x_{j}\right]=\frac{f\left(x_{i}\right)-f\left(x_{j}\right)}{x_{i}-x_{j}}$
称一阶差商的差商：
$\frac{f\left[x_{i}, x_{j}\right]-f\left[x_{j}, x_{k}\right]}{x_{i}-x_{k}}$
为 $f(x)$ 关于 $x_{i}, x_{j}, x_{k}$ 的二阶差商，记为 $f\left[x_{i}, x_{j}, x_{k}\right]$ ，一般地，称：
$\frac{f\left[x_{0}, x_{1}, \cdots, x_{k-1}\right]-f\left[x_{1}, x_{2}, \cdots, x_{k}\right]}{x_{0}-x_{k}}$
为 $f(x)$ 关于点 $x_{0}, x_{1}, \cdots, x_{k}$ 的 $k$ 阶差商，记为：
$f\left[x_{0}, x_{1}, \cdots, x_{k}\right]=\frac{f\left[x_{0}, x_{1}, \cdots, x_{k-1}\right]-f\left[x_{1}, x_{2}, \cdots, x_{k}\right]}{x_{0}-x_{k}}$
容易证明，差商具有下述性质：
$f\left[x_{i}, x_{j}\right]=f\left[x_{j}, x_{i}\right]$
$f\left[x_{i}, x_{j}, x_{k}\right]=f\left[x_{i}, x_{k}, x_{j}\right]=f\left[x_{j}, x_{i}, x_{k}\right]$

2.Newton插值公式

线性插值公式可表成：
$\varphi_{1}(x)=f\left(x_{0}\right)+\left(x-x_{0}\right) f\left[x_{0}, x_{1}\right]$
称为一次 Newton 插值多项式。一般地，由各阶差商的定义，依次可得：

$f(x)=f\left(x_{0}\right)+\left(x-x_{0}\right) f\left[x, x_{0}\right]$
$f\left[x, x_{0}\right]=f\left[x_{0}, x_{1}\right]+\left(x-x_{1}\right) f\left[x, x_{0}, x_{1}\right]$
$f\left[x, x_{0}, x_{1}\right]=f\left[x_{0}, x_{1}, x_{2}\right]+\left(x-x_{2}\right) f\left[x, x_{0}, x_{1}, x_{2}\right]$
$......$
$f\left[x, x_{0}, \cdots, x_{n-1}\right]=f\left[x_{0}, x_{1}, \cdots, x_{n}\right]+\left(x-x_{n}\right) f\left[x, x_{0}, \cdots, x_{n}\right]$
将上述各式分别乘 $1,\left(x-x_{0}\right),\left(x-x_{0}\right)\left(x-x_{1}\right), \cdots,\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right)$ ，然后相加并消去两边相等的部分，既得：
$\begin{aligned} f(x)=& f\left(x_{0}\right)+\left(x-x_{0}\right) f\left[x_{0}, x_{1}\right]+\cdots \\ &+\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right) f\left[x_{0}, x_{1}, \cdots, x_{n}\right] \\ &+\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n}\right) f\left[x, x_{0}, x_{1}, \cdots, x_{n}\right] \end{aligned}$
记：
$\begin{aligned} N_{n}(x) &=f\left(x_{0}\right)+\left(x-x_{0}\right) f\left[x_{0}, x_{1}\right]+\cdots \\ &+\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right) f\left[x_{0}, x_{1}, \cdots, x_{n}\right] \\ R_{n}(x) &=\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n}\right) f\left[x, x_{0}, x_{1}, \cdots, x_{n}\right] \\=& \omega_{n+1}(x) f\left[x, x_{0}, x_{1}, \cdots, x_{n}\right] \end{aligned}$
显然， $N_{n}(x)$ 是至多 $n$ 次的多项式，且满足插值条件，因而它是 $f(x)$ 的 $n$ 次插值多项式。这种形式的插值多项式称为 Newton 插值多项式。 $R_{n}(x)$ 称为 Newton 插值余项。

Newton 插值的优点是：每增加一个节点，插值多项式只增加一项，即：
$N_{n+1}(x)=N_{n}(x)+\left(x-x_{0}\right) \cdots\left(x-x_{n}\right) f\left[x_{0}, x_{1}, \cdots, x_{n+1}\right]$
因而便于递推运算。而且 Newton 插值的计算量小于 Lagrange 插值。

由插值多项式的唯一性可知，Newton 插值余项与 Lagrange 余项也是相等的，即：
$R_{n}(x)=\omega_{n+1}(x) f\left[x, x_{0}, x_{1}, \cdots, x_{n}\right]$
$=\frac{f^{(n+1)}(\xi)}{(n+1) !} \omega_{n+1}(x) \quad \xi \in(a, b)$
其中 $\xi \in(\alpha, \beta), \alpha=\min _{0 \leq i \leq n}\left\{x_{i}\right\}, \beta=\max _{0 \leq i \leq n}\left\{x_{i}\right\}$

同时可得差商与导数的关系：
$f\left[x_{0}, x_{1}, \cdots, x_{n}\right]=\frac{f^{(n)}(\xi)}{n !}$

3.差分

当节点等距时，即相邻两个节点之差（称为步长）为常数，Newton 插值公式的形式会更简单。此时关于节点间函数的平均变化率（差商）可用函数值之差（差分）来表示。

定义：设有等距节点 $x_{k}=x_{0}+k h(k=0,1, \cdots, n)$ ，步长 $h$ 为常数， $f_{k}=f\left(x_{k}\right)$ 。称相邻两个节点 $x_{k}, x_{k+1}$ 处的函数值的增量 $f_{k+1}-f_{k}(k=0,1, \cdots, n-1)$ 为函数 $f(x)$ 在点 $x_{k}$ 处以 $h$ 为步长的一阶差分，记为 $\Delta f_{k}$ ，即：
$\Delta f_{k}=f_{k+1}-f_{k} \quad(k=0,1, \cdots, n)$

类似地，定义差分的差分为高阶差分。如二阶差分为：
$\Delta^{2} f_{k}=\Delta f_{k+1}-\Delta f_{k} \quad(k=0,1, \cdots, n-2)$
一般的， $m$ 阶差分为
$\Delta^{m} f_{k}=\Delta^{m-1} f_{k+1}-\Delta^{m-1} f_{k} \quad(k=2,3, \cdots)$
上面定义的各阶差分又称为向前差分。常用的差分还有两种：
$\nabla f_{k}=f_{k}-f_{k-1}$
称为 $f(x)$ 在 $x_{k}$ 处以 $h$ 为步长的向后差分：
$\delta f_{k}=f\left(x_{k}+\frac{h}{2}\right)-f\left(x_{k}-\frac{h}{2}\right)$
称为 $f(x)$ 在 $x_{k}$ 处以 $h$ 为步长的中心差分。一般地， $m$ 阶向后差分与 $m$ 阶中心差分公式为：
$\begin{aligned} \nabla^{m} f_{k} &=\nabla^{m-1} f_{k}-\nabla^{m-1} f_{k-1} \\ \delta^{m} f_{k} &=\delta^{m-1} f_{k+\frac{1}{2}}-\delta^{m-1} f_{k-\frac{1}{2}} \end{aligned}$

差分具有以下性质：
(1)各阶差分均可表成函数值的线性组合，例如：
$\Delta^{m} f_{k}=\sum_{j=0}^{m}(-1)^{j}\left(\begin{array}{c}{m} \\ {j}\end{array}\right) f_{k+m-j}$
$\nabla^{m} f_{k}=\sum_{j=0}^{m}(-1)^{j}\left(\begin{array}{c}{m} \\ {j}\end{array}\right) f_{k-j}$
(2)各种差分之间可以互化。向后差分与中心差分化成向前差分的公式如下：
$\begin{aligned} \nabla^{m} f_{k} &=\Delta^{m} f_{k-m} \\ \delta^{m} f_{k} &=\Delta^{m} f_{k-\frac{m}{2}} \end{aligned}$

4.等距节点插值公式

如果插值节点是等距的，则插值公式可用差分表示。设已知节点 $x_{k}=x_{0}+k h(k=0,1,2, \cdots, n)$ ，则有：
$\begin{aligned} N_{n}(x) &=f\left(x_{0}\right)+f\left[x_{0}, x_{1}\right]\left(x-x_{0}\right) \\ &+\cdots+f\left[x_{0}, x_{1}, \cdots, x_{n}\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right) \\=& f_{0}+\frac{\Delta f_{0}}{h}\left(x-x_{0}\right)+\cdots+\frac{\Delta^{n} f_{0}}{n ! h^{n}}\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right) \end{aligned}$
若令 $x=x_{0}+t h$ ，上式又可变形为：
$N_{n}\left(x_{0}+t h\right)=f_{0}+t \Delta f_{0}+\cdots+\frac{t(t-1) \cdots(t-n+1)}{n !} \Delta^{n} f_{0}$
上式又称Newton向前插值公式。