给定$(x_0,y_0),\ldots,(x_n,y_n)$

设$f(x)$是以上数据的$n$次插值多项式，并增加数据$(x_{n+1},y_{n+1})$

取$g(x)=f(x)+\frac{y_{n+1}-f(x_{n+1})}{(x_{n+1}-x_0)\ldots(x_{n+1}-x_n)}(x-x_0)\ldots(x-x_n)$

$g(x)$是$(x_0,y_0),\ldots,(x_{n+1},y_{n+1})$的插值多项式（思考：为什么）

令$p_k(x)=(x-x_0)\ldots(x-x_{k-1})$

牛顿插值多项式具有如下形式
$f_n(x)=a_0+a_1p_1(x)+\ldots+a_np_n(x)$

$a_k=\left(y_k-f_{k-1}(x_k)\right)/p_k(x_k)$

给定$(x_0,y_0),\ldots,(x_n,y_n)$，且$x_0<\ldots<x_n$

令$f[x_k]=y_k$

$f[x_j,\ldots,x_{j+k}]=\frac{f[x_{j+1},\ldots,x_{j+k}]-f[x_j,\ldots,x_{j+k-1}]}{x_{j+k}-x_j}$

递归计算

一般用如下三角形逐行计算：
$f[x_0]$ $\quad \quad\quad \quad f[x_1]$ $\quad \quad \quad f[x_2]$
$f[x_0,x_1]$ $\quad\quad \; f[x_1,x_2]$
$f[x_0,x_1,x_2]$

例如： $f[x_0,x_1,x_2]=(f[x_1,x_2]-f[x_0,x_1])/(x_2-x_0)$

本单元格的值=（上一行右侧的值减去正上方的值）/两端节点之差

$x: 0,1,2$
$y:1,4,3$

$f[x_0]=1$, $\quad f[x_1]=4$, $\quad f[x_2]=3$

$f[x_0,x_1]=\frac{f[x_1]-f[x_0]}{x_1-x_0}=3$, $\quad f[x_1,x_2]=\frac{f[x_2]-f[x_1]}{x_2-x_1}=-1$

$f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=-2$

现增加一条数据$(3，4)$，即
$x: 0,1,2,3$
$y:1,4,3,4$
$f[x_0]=1$ $\quad \quad\quad \quad\quad f[x_1]=4$ $\quad \quad \quad f[x_2]=3$
$f[x_0,x_1]=3$ $\quad\quad\quad \; f[x_1,x_2]=-1$
$f[x_0,x_1,x_2]=-2$

求均差$f[x_0,x_1,x_2,x_3]$，并写出对应的牛顿插值多项式

引入牛顿插值的动机

牛顿插值多项式与拉格朗日插值多项式相同

定义和公式

均差的计算（重点！）