Newton 插值

插值

张瑞
中国科学技术大学数学科学学院

Newton 插值

  • Lagrange插值不需要解线性方程组，而且，节点不变时，插值基函数也不会变化。
  • 增加一个节点，Lagrange插值需要重新计算。
  • 可以做到增加一个节点，就在原来的插值函数的基础上，增加一个新的函数吗？

差商

定义 1.
节点$\{x_i\}_{i=0}^n$互不相同，定义函数$f(x)$的一阶差商为

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

定义$f(x)$的n阶差商为

\[f[x_0,x_1,\cdots,x_n]=\frac{f[x_0,x_1,\cdots,x_{n-1}]-f[x_1,\cdots,x_n]}{x_0-x_n} \]

差商具有如下性质

定理 1. (差商的展开式)
$n$阶差商$f[x_0,x_1,\cdots,x_n]$ 可以展开为

\[\sum_{i=0}^n\frac{f(x_i)}{(x_i-x_0)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)} \]

证明. 用数学归纳法

定理 2. (差商的对称性)
函数$f(x)$的差商与节点的次序无关，即

\[f[x_0,x_1,\cdots,x_n]=f[x_{p_0},x_{p_1},\cdots,x_{p_n}] \]

其中$p_0,p_1,\cdots,p_n$是$0,1,\cdots,n$的任一排列

证明. 由展开式可得。

例 1. 设$f(x)=\alpha u(x)+\beta v(x)$，其中$\alpha$, $\beta$是常数，试证明

\[f[x_0,x_1,\cdots,x_n]=\alpha u[x_0,x_1,\cdots,x_n]+\beta v[x_0,x_1,\cdots, x_n] \]

证明. 利用差商的展开式

例 2. 若

\[f[x_0,x_1,x_2,x_3]=\frac{f[x_0,x_2,x_3]-f[x_0,x_1,x_3]}{x_a-x_b} \]

求$a$, $b$的值。

解. 找不同的点。$a=2$, $b=1$

Newton型插值

由差商公式

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

得到

(1)
\[f(x)=f(x_0)+f[x,x_0](x-x_0) \]

类似，

\[f[x,x_0,x_1]=\frac{f[x,x_0]-f[x_0,x_1]}{x-x_1} \]

有

(2)
\[f[x,x_0]=f[x_0,x_1]+(x-x_1)f[x,x_0,x_1] \]

将(2)代入(1)则有

(3)
\[\begin{aligned} f(x)=f(x_0)&+f[x_0,x_1](x-x_0) \\ & +f[x,x_0,x_1](x-x_0)(x-x_1) \end{aligned} \]

进一步，有

\[f[x,x_0,x_1]=f[x_0,x_1,x_2]+(x-x_2)f[x,x_0,x_1,x_2] \]

代入(3)

\[\begin{aligned} f(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) \\ &+ f[x,x_0,x_1,x_2](x-x_0)(x-x_1)(x-x_2) \end{aligned} \]

这样，有

\[\begin{aligned} f(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)\cdots(x-x_{n-1}) \\ &+f[x,x_0,\cdots,x_n](x-x_0)\cdots(x-x_n) \end{aligned} \]
\[\begin{aligned} f(x)=&f(x_0)+f[x,x_0](x-x_0) \\ =&f(x_0)+f[x_0,x_1](x-x_0)+f[x,x_0,x_1](x-x_0)(x-x_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) \\ &+ f[x,x_0,x_1,x_2](x-x_0)(x-x_1)(x-x_2)\\ =&\cdots\\ =&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)\cdots(x-x_{n-1}) \\ &+f[x,x_0,\cdots,x_n](x-x_0)\cdots(x-x_n) \end{aligned} \]

记

\[\begin{aligned} 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)\cdots(x-x_{n-1}) \end{aligned} \]

则有

\[\begin{aligned} &N_n(x)=N_{n-1}(x)+f[x_0,x_1,\cdots,x_n](x-x_0)\cdots(x-x_{n-1}) {\color{green}(*)}\\ &N_{n-1}(x_k)=N_n(x_k), k=0,1,\cdots,n-1 \end{aligned} \]

和

\[\begin{aligned} f(x)&=N_n(x)+f[x,x_0,\cdots,x_n](x-x_0)\cdots(x-x_n) \\ &=N_{n-1}(x)+f[x,x_0,\cdots,x_{n-1}](x-x_0)\cdots(x-x_{n-1}) {\color{green}(**)}\\ %&=\cdots \\ %&=N_0(x)+f[x,x_0](x-x_0) \end{aligned} \]

在(*)和(**)式中，取$x=x_n$，则有

\[\begin{aligned} f(x_{n})&=N_{n-1}(x_{n})+f[x_{n},x_0,\cdots,x_{n-1}](x_{n}-x_0)\cdots(x_{n}-x_{n-1}) \\ &=N_{n}(x_{n}) \end{aligned} \]

所以，有$f(x_i)=N_i(x_i)=N_n(x_i),i=0,1,\cdots,n$。

这样，$N_n(x)$是$f(x)$关于节点$\{x_i\}_{i=0}^n$的插值多项式，称为Newton型插值多项式。

\[\begin{aligned} 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)\cdots(x-x_{n-1}) \end{aligned} \]

它的误差为

\[R_n(x)=f[x,x_0,\cdots,x_n](x-x_0)\cdots(x-x_n) \]

问题. 如何计算 Newton 插值 ？

  • 需要知道各阶差商
    \[f[x_0], f[x_0,x_1], \cdots, f[x_0,x_1,\cdots, x_n] \]
  • 可以利用差商表，来计算各阶差商。

例 3. 已知函数$y=f(x)$的值：$f(-1)=0$, $f(0)=4$, $f(1)=-2$, $f(2)=5$。 求满足如上插值条件的Newton型多项式。

解. 构造差商表

$x_i$ $f(x_i)$ 一阶差商 二阶差商 三阶差商
-1 0
0 -4 -4
1 -2 2 3
2 5 7 2.5 -1/6

则有

\[N_3(x)=0-4(x+1)+3(x+1)x-\frac{1}{6}(x+1)x(x-1) \]

伪代码

输入x[i],y[i],i=0,1,...,n
// 求差商表，各阶差商直接存在y[i]单元内
for i=1 to n
   for j=n to i
       y[j]=(y[j]-y[j-1])/(x[j]-x[j-i]) // 得到的i阶差商，直接存在y[j]单元上
   end for
end for
// 求值，在x处
t=y[n]
for i=n-1 to 0
   t = t*(x-x[i])+y[i]
end for
// 现在t 就是N_n(x)

问题. 上述代码的问题是： 增加一个节点，整个计算过程要重新计算。

这与Newton插值的承袭性是不符合的，可以改进吗？

思考：

已知节点组$x_0, x_1, \cdots, x_n$及各阶差商

\[f[x_0], f[x_0, x_1], \cdots, f[x_0,x_1, \cdots, x_n] \]

现在增加节点$(x_{n+1}, f(x_{n+1}))$，如何以最小的代价（存贮量和计算量）得到

\[f[x_0,x_1,\cdots,x_{n+1}] \]

从而得到高一阶的Newton插值多项式。

三种插值方法的比较，

  • 用待定系数法，Lagrange插值, Newton插值 都是n次多项式。 由插值多项式的存在唯一性，这三种方法得到的是同一个多项式。
  • 从线性空间的角度来看，三种方法只是取了$n$次多项式空间的不同基函数，
    • 待定系数法的基函数是$\{1,x,x^2,\cdots,x^n\}$
    • Lagrange插值的基函数是$\{l_0(x),\cdots,l_n(x)\}$
    • Newton插值的基函数是$\{1, (x-x_0),(x-x_0)(x-x_1),\cdots,\displaystyle\prod_{i=0}^{n-1}(x-x_i)\}$

注. $N_n(x)$是插值多项式，也可以通过下面的例子，直接证明它与Lagrange型多项式是相等的。

例 4. 记$\{x_i\}_{i=0}^n$上的Lagrange插值多项式为$L_n(x)$，若有

\[L_n(x_n)-L_{n-1}(x_n)=A(x_n-x_0)\cdots(x_n-x_{n-1}) \]

试证明

\[A=f[x_0,x_1,\cdots,x_n] \]

证明. 用Lagrange型的表达式，及差商的展开式即证。具体过程作为作业完成

由插值多项式的存在唯一性，$N_n(x)$与Lagrange型插值多项式是相等的，因而有相同的误差。 则有

\[\begin{aligned} f[x,x_0,\cdots,x_n](x-x_0)\cdots(x-x_n)\\ =\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)\cdots(x-x_n) \end{aligned} \]

因此，有

定理 3.
$n+1$个互不相同节点的$n$阶差商有如下关系

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

其中$\xi \in (\min(x_0,\cdots,x_n), \max(x_0,\cdots,x_n))$

利用前面的定理，可以把差商的概念再推广一点。

定义 2.
若$f(x)$在点$x_0$具有$n$阶导数，则定义

\[f[\underbrace{x_0,x_0\cdots,x_0}_{n+1}]=\frac{1}{n!}f^{(n)}(x_0) \]

进而，有

\[f[x_0,x_0,x_1]=\frac{f[x_0,x_0]-f[x_0,x_1]}{x_0-x_1}=\frac{\frac{f'(x_0)}{1!}-f[x_0,x_1]}{x_0-x_1} \]

例 5. 已知$f(x)=2 x^4+3x-1$，求

\[f[1,2,3,4,5]=?,\, \quad f[1,2,3,4,5,6]=? \]

解. 由差商与导数的关系，

\[f[1,2,3,4,5]=\frac{f^{(4)}(\xi)}{4!}=\frac{2\times 4!}{4!}=2 \]
\[f[1,2,3,4,5,6]=\frac{f^{(5)}(\xi)}{5!}=\frac{0}{5!}=0 \]

能否给出一般性的结论？

定理 4.
若$f(x)$是$k$次多项式，则有

\[f[x_0,\cdots,x_n]=\begin{cases} a_k, & k=n \\ 0, &k<n \end{cases} \]

其中$a_k$为$x^k$的系数。

定理 5.
如果$f(x)$的$k$阶差商$f[x,x_0,x_1,\cdots,x_{k-1}]$是$x$的$m$次多项式，则$f[x,x_0,x_1,\cdots,x_k]$是$x$的$m-1$次多项式

证明. 定义$m$次多项式

\[g(x)=f[x,x_0,x_1,\cdots,x_{k-1}]-f[x_0,x_1,\cdots,x_{k}] \]

则$g(x_k)=0$，即$x_k$是多项式$g(x)$的根。 由多项式的特性知，

\[g(x)=(x-x_k)h(x) \]

其中$h(x)$是$m-1$次多项式。

因此，

\[\begin{aligned} f[x,x_0,x_1,\cdots,x_k]=&\frac{f[x,x_0,x_1,\cdots,x_{k-1}]-f[x_0,x_1,\cdots,x_{k}]}{x-x_k} \\ =&h(x) \end{aligned} \]

更进一步，有

定理 6.
若$f(x)$是$n$次多项式，则$f[x,x_1,\cdots,x_m]$是$n-m$次多项式，其中$m\leq n$

证明. 利用定理5

谢谢

vertical slide 2

目录

本节读完

例 6.

6.