[引入]求作n次多项式
$N_n(x)=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)+...+c_n(x-x_0)(x-x_1)...(x-x_n-1)$
使满足
$\\N_n(x_i)=y_i=f(x_i)\qquad i=0,1,2,...,n$
为了简化，引入下列记号
$\begin{equation} \left\{ \begin{array}{lr} \varphi_0(x)=1\\ \varphi_1(x)=x-x_0\\ \varphi_i(x)=(x-x_{i-1})\varphi_{i-1}(x)\\ =(x-x_0)(x-x_1)...(x-x_{i－1}) \qquad i=0,1,2,...,n \end{array} \right. \end{equation}$
$\varphi_i(x)$ 就是多项式的第 i 项的非系数部分。
当 $c_i$ 是常数，且只与当前的插值节点相关时，再增加新的节点，只需计算 $c_{n+1}$ 和 $\varphi_{n＋1}(x)$

$c_0=f(x_0)$
$c_1=\frac{f(x_0)-f(x_1)}{x_0-x_1}$
$c_2=\frac{1}{x_0-x_2} (\frac{f(x_0)-f(x_1)}{x_0-x_1} - \frac{f(x_1)-f(x_2)}{x_1-x_2})$
此时，需要计算 $c_i$ ,引入差商的概念。

2.3.2 差商的概念

给定 $[a,b]$ 中互不相同的点 $x_0,x_1,x_2,..x_n$ ,以及函数 $f(x)$ 在这些点处对应的函数值 $f(x_0),f(x_1),f(x_2),...f(x_n)$ 。
$f(x)在x_0处的零阶差商$ $f[x_0]=f(x_0)$
$f(x)在x_0,x_1两点的一阶差商$ $f[x_0,x_1]=\frac{f(x_0)-f(x_1)}{x_0-x_1}$
$f(x)在x_0,x_1,x_2三点的二阶差商$ $f[x_0,x_1,x_2]=\frac{f[x_0-x_1]-f[x_1-x_2]}{x_0-x_2}$
...
$f(x)在x_0,x_1,...,x_n的n阶差商$ $f[x_0,x_1,...,x_n]=\frac{f[x_0,x_1,...,x_n]-f[x_1,x_2,...,x_n]}{x_0-x_n}$

综上，对于顺序排列的 $x_0,x_1,...x_n,\quad c_i=f[x_0,x_1,...x_i]$ ,由 $\varphi_i(x)和c_i,可计算出插值多项式。$

2.3.3 差商的性质

线性性
对称性
降次性

(1) $k阶差商f[x_0,x_1,...,x_k]是函数值f(x_0),f(x_1),...,f(x_k)的线性组合。$
$f[x_0,x_1,...,x_k]=\sum\limits_{j=0}^{k} \frac{f(x_j)}{(x_j-x_0)(x_j-x_1)...(x_j-x_{j－1})(x_j-x_{j＋1})...(x_j- x_k)}$

证明使用数学归纳法
$当k=1时,f[x_0,x_1]=\frac{f(x_0)}{x_0- x_1}+\frac{f(x_1)}{x_1- x_0}成立$
$设当k=m-1时成立$
$当k=m时，f[x_0,x_1,x_k]=\frac{1}{x_0-x_k} (f[x_0,x_1,...,x_{k－1}]- f[x_1,x_2,...,x_k])$
$=\frac{1}{x_0－x_k} (\frac{f(x_0)}{(x0-x_1)(x_0-x_2)...(x_0-x_{k－1})} -\frac{f(x_k)}{(x_k-x_1)(x_k-x_2)...(x_k－x_{k－1})} + \sum\limits_{i=1}^{k-1}(f(x_i)* \frac{x_0 - x_k}{(x_j-x_0)(x_j-x_1)...(x_j－x_k)} )$
$=\sum\limits_{j=0}^{k} \frac{f(x_j)}{(x_j-x_0)(x_j-x_1)...(x_j-x_{j－1})(x_j-x_{j＋1})...(x_j- x_k)}$

(2) $差商f[x_0,x_1,...,x_k]的值与插值点的内部排序无关，也称对称性$
由性质一线性组合即可证明。

(3) $若差商f[x,x_0,x_1,...,x_k]是x的m次多项式，则f[x,x_0,x_1,...,x_k,x_{k＋1}]是x的m-1次多项式$

证明:
$f[x,x_0,x_1,...,x_k,x_{k＋1}]=\frac{f[x,x_0,x_1,...,x_k]-f[x_{k+1},x_0,x_1,...,x_k]}{x-x_{k+1}}$
$(x-x_{k+1})* f[x,x_0,x_1,...,x_k,x_{k＋1}]= f[x,x_0,x_1,...,x_k]-f[x_{k+1},x_0,x_1,...,x_k]$
$右端为m次多项式(多项式＋常数差商)，左端也为m次多项式$
$当x=x_{k+1}时，右式为0,故说明右式带有系数(x-x_{k＋1}),两边同除(x-x_{k＋1})$
$可得f[x,x_0,x_1,...,x_k,x_{k＋1}]=\frac{f[x,x_0,x_1,...,x_k]-f[x_{k+1},x_0,x_1,...,x_k]}{x-x_{k+1}}为m-1次多项式$

推论：若 $f(x)为n次多项式,则f[x,x_0,x_1,...,x_n]恒等于0。$

2.3.4 Newton插值公式

由差商的定义
$f(x)=f(x_0)+f[x,x_0](x-x_0)$
$f[x,x_0]=f[x_0,x_1]+f[x,x_0,x_1](x-x_1)$
...
$f[x,x_0,x_1,...,x_n]=f[x_0,x_1,...,x_n]+f[x,x_0,...,x_n](x-x_n)$

逐个带入，可知
$f(x)=f(x_0)+ f[x_0,x_1](x-x_0)+...+f[x_0,x_1,...,x_n](x-x_0)(x-x_1)...(x-x_{n－1})$
$+f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$

故余项 $R_n(x)=f(x)-N_n(x)=f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$
遗憾的是，这个公式中的差商 $f[x,x_0,...,x_n]$ 因带有 $f(x)$ 而不能计算，只能得到解析表达式

解决方法:
利用 $Langrange插值余项公式 R_n(x)=f(x)-p_n(x)=\frac{f^{n+1}(\xi)}{(n+1)!} \prod\limits_{i=0} ^n (x-x_i)$
和余项 $R_n(x)=f(x)-N_n(x)=f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$
知，当 $f(x)在插值区间[a,b]上有n+1阶导数，且 \exists \xi \in[x_{i min},x_{i max}]$
使得 $\\f[x_0,x_1,...,x_n ]=\frac{f^{n}(\xi)}{n!}$
根据上述关系，可将Newton插值公式改写为
$N_n(x)=f(x_0)+f^{'}(\xi_1)(x-x_0)+\frac{f^{''}(\xi_2)}{2!}(x-x_0)(x-x_1)+......+\frac{f^{n}(\xi_n)}{n!}(x-x_0)(x-x_1)...(x-x_n)$

综上

牛顿插值的同式为 $\sum_{i=0} ^{n} \varphi_i(x)c_i$
$\varphi_0(x)=1 \qquad \varphi_n(x)=(x-x_0)(x-x_1)...(x-x_{n-1})$
可以利用差商的方法计算牛顿插值系数
$n阶差商$ $f[x_0,x_1,...,x_n]=\frac{f[x_0,x_1,...,x_n]-f[x_1,x_2,...,x_n]}{x_0-x_n}$
余项为 $R_n(x)=f(x)-N_n(x)=f[x,x_0,...,x_n](x-x_0)(x-x_1)...(x-x_n)$
遗憾的是，这个公式中的差商 $f[x,x_0,...,x_n]$ 因带有 $f(x)$ 而不能计算，只能得到解析表达式
知，当 $f(x)在插值区间[a,b]上有n+1阶导数，且 \exists \xi \in[x_{i min},x_{i max}]$
使得 $\\f[x_0,x_1,...,x_n ]=\frac{f^{n}(\xi)}{n!}$
根据上述关系，可将Newton插值公式改写为
$N_n(x)=f(x_0)+f^{'}(\xi_1)(x-x_0)+\frac{f^{''}(\xi_2)}{2!}(x-x_0)(x-x_1)+......+\frac{f^{n}(\xi_n)}{n!}(x-x_0)(x-x_1)...(x-x_n)$

引用

1.《计算方法　第二版》崔国华　许如初著

插值法和线性拟合　第二节

插值法和线性拟合　第二节

目录

2.1 插值多项式存在唯一性

2.2 Lagrange(拉格朗日)插值

2.3 Newton(牛顿)插值

2.4 Hermite(赫米特)插值

2.5 分段插值