引言

许多实际问题都用函数y=f(x)来表示某种内在规律的数量关系，其中相当一部分函数是通过实验或计算得到的，并且只是[a,b]上一系列点$x_i$的函数值 $y_i=f(x_i)(i=0,1,...,n)$ 这只是一张函数表。有的问题虽有解析表达式，但由于计算复杂，使用不方便，通常也造一个函数表，比如平方根表、立方根表、对数表和三角函数表等等。为了研究函数的变化规律，往往需要求不在表上的函数值。因此，我们希望根据给定的函数表做一个既能反映函数f(x)的特性，又便于计算的简单函数p(x)，用p(x)近似f(x)。

函数逼近问题：许多实际问题都用函数来表示某种内在规律的数量关系，但函数表达式无法给出，只有通过实验或观测得到的数据表，如何根据这些数据推测或估计其它点的函数值？

如：通常用代数多项式或分段代数多项式作为p(x)，并使 $p(x_i)=f(x_i)$ 对$i=0,1,...,n$成立。这样确定的p(x)就是我们希望得到的插值函数。

插值法定义：设函数y=f(x)在区间[a,b]上有定义，且 $a\le x_0<x_1<...<x_n\le b$，已知在点 $x_0,x_1,...,x_n$ 上的值 $y_0,y_1,...,y_n$。若存在一简单函数p(x)，使 $p(x_i)=y_i$，$i=0,1,2,...,n$ 成立，就称p(x)为f(x)的插值函数，点 $x_0,x_1,...,x_n$ 称为插值节点，包含插值节点的区间[a,b]称为插值区间，$p(x_i)=y_i$ 称为插值条件，求插值函数p(x)的方法称为插值法。

常用插值法：

• 多项式插值：若p(x)为次数不超过n的代数多项式，即 $p(x)=a_0+a_1x+...+a_nx^n$，其中$a_i$为实数，就称P(x)为插值多项式。————最常用的插值函数

• 分段插值：若P(x)为分段多项式

• 三角插值：若P(x)为三角多项式

  ……

插值多项式的存在唯一性：设p(x)是形如 $p(x)=a_0+a_1x+...+a_nx^n$ 的插值多项式，用$H_n$代表所有次数不超过n的多项式集合，于是 $P(x)\in H_n$。所谓插值多项式p(x)存在且唯一，就是指在集合$H_n$中有且只有一个p(x)满足插值条件 $p(x_i)=y_i$，$i=0,1,2,...,n$。

由插值条件可得一个关于 $a_0,a_1,...,a_n$ 的 n+1 元线性方程组。要证明插值多项式的存在唯一性，只要证明 n+1 元线性方程组存在唯一解，也就是证明方程组的系数行列式的值不为零。其系数行列式为(Vandermond行列式)

利用行列式性质可得 $V_n(x_0,x_1,...,x_n)=\prod\limits_{0\le j<i\le n}(x_i-x_j)$，由于 $i\neq j$ 时 $x_i\neq x_j$，故所有因子 $x_i-x_j\neq0$，于是 $V_n(x_0,x_1,...,x_n)\neq0$，故方程组存在唯一的一组解。

以上论述可写成下列定理：(唯一性) 满足 $p(x_i)=y_i$，$i=0,1,2,...,n$ 次数不超过n的插值多项式是唯一存在的。

若不将多项式次数限制为n，则插值多项式不唯一。例如 $P(x)=P_n(x)+k(x)\prod_{i=0}^n(x-x_i)$ 也是一个插值多项式，其中p(x)可以是任意多项式。

拉格朗日多项式

求n次多项式 $L_n(x)=y_0l_0(x)+y_1l_1(x)+...+y_nl_n(x)$ 使得 $L_n(x_i)=y_i,i=0,1,2,...,n$。条件：无重合节点，即 $i\ne j\Rightarrow x_i\ne x_j$

n=1时：已知$x_0,x_1;y_0,y_1$，求 $L_1(x)=y_0l_0(x)+y_1l_1(x)$ 使得 $L_1(x_0)=y_0,L_1(x_1)=y_1$ 可见$L_1(x)$是过$(x_0,y_0)$和$(x_1,y_1)$两点的直线。可得 $\Large L_1(x)=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0)=[\frac{x-x_1}{x_0-x_1}]y_0+[\frac{x-x_0}{x_1-x_0}]y_1=\sum^1_{i=0}l_i(x)y_i$

其中 $[\frac{x-x_1}{x_0-x_1}]$ 为$l_0(x)$，$[\frac{x-x_0}{x_1-x_0}]$ 为$l_1(x)$。$l_i(x)$ 称为拉氏基函数，满足条件 $l_i(x_j)=\delta_{ij}$

Kronecker Delta函数$\delta_{ij}$，当 $i=j$ 时，$\delta_{ij}=1$；当 $i\ne j$ 时，$\delta_{ij}=0$。

n≥1时：希望找到 $l_i(x),i=0,...,n$ 使得 $l_i(x_j)=\delta_{ij}$；然后令 $L_n(x)=\sum^n_{i=0}l_i(x)y_i$，则显然有 $L_n(x_i)=y_i$。

对于 $l_i(x)$，每个$l_i$有n个零点 $x_0...\hat{x_i}...x_n$ → $l_i(x)=C_i(x-x_0)...\hat{(x-x_i)}...(x-x_n)=C_i\Large\prod^n_{j\ne i,j=0}(x-x_j)$；又有条件 $l_i(x_i)=1$ → $C_i=\Large\prod\limits_{j\ne i}\frac{1}{(x_i-x_j)}$。所以

$l_i(x)$与节点有关，而与f无关。$\sum\limits_il_i(x)=1$，（特别的，f(x)=1）

特别地，一点零次插值多项式为 $L_0(x)=y_0$；两点一次插值（线性插值）多项式为 $L_1(x)=\Large [\frac{x-x_1}{x_0-x_1}]y_0+[\frac{x-x_0}{x_1-x_0}]y_1$；三点二次插值（抛物插值）多项式为 $L_2(x)=\Large\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}y_0+\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}y_1+\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}y_2$

插值余项(插值误差)：设节点 $a\le x_0<x_1<...<x_n\le b$，且f满足条件 $f\in C^n[a,b]$，$f^{(n+1)}$在[a,b]内存在，考察截断误差 $R_n(x)=f(x)-L_n(x)$。因为有n+1个插值节点，所以$R_n(x)$至少有n+1个零点 → $R_n(x)=K(x)\large\prod^n_{i=0}(x-x_i)$。

任意固定 $x\ne x_i(i=0,...,n)$，考察 $\phi(t)=R_n(t)-K(x)\large\prod^n_{i=0}(t-x_i)$。$\phi(t)$有n+2个不同的零点$x_0...x_nx$ → $\phi^{(n+1)}(\xi_x)=0,\xi_x\in(a,b)$ → $R^{(n+1)}_n(\xi_x)-K(x)(n+1)!=f^{(n+1)}(\xi_x)-L^{(n+1)}_n(\xi_x)-K(x)(n+1)!=0$ → $K(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}$

通常不能确定 $\xi_x$，而是估计 $|f^{(n+1)}(x)|\le M_{n+1}$，$\forall x\in(a,b)$ 将 $\large\frac{M_{n+1}}{(n+1)!}\prod^n_{i=0}|x-x_i|$ 作为误差估计上限。当f(x)为任一个次数≤n的多项式时，$f^{(n+1)}(x)\equiv0$，可知 $R_n(x)\equiv0$，即插值多项式对于次数≤n的多项式是精确的。

当n=1时，$R_1(x)=\frac{1}{2}f''(\xi)(x-x_0)(x-x_1)$，$\xi\in[x_0,x_1]$

当n=2时，抛物插值余项为 $R_2(x)=\frac{1}{6}f'''(\xi)(x-x_0)(x-x_1)(x-x_2)$，$\xi\in[x_0,x_2]$

当插值点落在插值节点之外时，称为外推；当插值点落在插值节点之内时，称为内插。内插通常优于外推。选择要计算的x所在的区间的端点，插值效果较好。

高次插值通常优于低次插值，但绝对不是次数越高就越好。

牛顿插值

问题：拉格朗日插值简单易用，但若要增加或减少节点时，全部基函数$l_k(x)$都需重新计算，不太方便。

解决方法：设计一个可以逐次生成插值多项式的算法，即 $p_n(x)=p_{n-1}(x)+u_n(x)$ 其中$p_n(x)$和$p_{n-1}(x)$分别为n次和n-1次插值多项式。将$L_n(x)$改写成$c_0+c_1(x-x_0)+...+c_n(x-x_0)...(x-x_{n-1})$的形式，每加一个节点时，只附加一项上去即可，这就是牛顿插值。

差商(均差)：

• 1阶差商：$f[x_i,x_j]=\large\frac{f(x_i)-f(x_j)}{x_i-x_j}$，$(i\ne j,x_i\ne x_j)$
• 2阶差商：$f[x_i,x_j,x_k]=\Large\frac{f[x_i,x_j]-f[x_j,x_k]}{x_i-x_k}$，$(i\ne k)$
• (k+1)阶差商：$f[x_0,...,x_{k+1}]=\Large\frac{f[x_0,...,x_{k}]-f[x_1,...,x_{k+1}]}{x_0-x_{k+1}}=\frac{f[x_0,...,x_{k}]-f[x_0,...,x_{k-1},x_{k+1}]}{x_{k}-x_{k+1}}$

k阶差商必须由k+1个节点构成，k个节点是构造不出k阶差商的。为统一起见，补充定义函数$f(x_0)$为零阶差商。差商的值与$x_i$的顺序无关

差商性质：

• k阶差商可表为函数值$f(x_0),f(x_1),...,f(x_k)$的线性组合，即 $f[x_0,...,x_{k}]=\sum^k_{j=0}\Large\frac{f(x_j)}{(x_j-x_0)...(x_j-x_{j-1})(x_j-x_{j+1})...(x_j-x_{k})}$$=\sum^k_{j=0}\Large\frac{f(x_j)}{\omega_{k+1}'(x_j)}$

  定义 $\omega_{k+1}(x)=\prod^k_{i=0}(x-x_i)$，则 $\omega_{k+1}'(x)=[(x-x_j)·\prod^k_{i=0,i\ne j}(x-x_i)]'=\prod^k_{i=0,i\ne j}(x-x_i)+(x-x_j)·[\prod^k_{i=0,i\ne j}(x-x_i)]'$

• 差商具有对称性，即 $f[x_0,x_1,...,x_{k}]=f[x_1,x_0,x_2,...,x_{k}]=...=f[x_1,...,x_{k},x_0]$

• 若f(x)在[a,b]上有n阶导数，且节点 $x_i\in[a,b](i=0,1,...,n)$，则n阶差商与n阶导数有如下关系式：$f[x_0,x_1,...,x_{n}]=\Large\frac{f^{(n)}(\xi)}{n!}$, $\xi\in[a,b]$

• 若f(x)是n次多项式，则其k阶差商 $f[x_0,x_1,...,x_{k-1},x]$，当$k\le n$时是一个n-k次多项式，而当k>n时恒为零。

牛顿插值：牛顿插值是通过选取特殊的基函数来实现的，这时，取 $\phi_0(x)=1$，$\phi_{i+1}(x)=(x-x_i)\phi_i(x)$，$i=0,1,...,n-1$ 作为牛顿插值的以 $x_0,x_1,...,x_{n}$ 为节点的基函数，而次数不超过n的多项式$N_n(x)$可表示为 $N_n(x)=c_0+c_1(x-x_0)+...+c_n(x-x_0)...(x-x_{n-1})$，其中 $c_0,c_1,...,c_{n}$ 是待定系数，由插值条件决定。

$f(x_0)=N_n(x_0)=c_0$，$f(x_1)=N_n(x_1)=c_0+c_1(x_1-x_0)=f(x_0)+c_1(x_1-x_0)$，得 $c_1=\frac{f(x_1)-f(x_0)}{x_1-x_0}=f[x_0,x_1]$

通过插值条件运用数学归纳法可以求得 $c_k=f[x_0,x_1,...,x_{k}]$ (k阶差商)。因此就得到下列的满足插值条件的n次插值多项式

$f(x)=N_n(x)+R_n(x)$，插值余项$R_n(x)=f[x,x_0,...,x_{n}](x-x_0)...(x-x_{n-1})(x-x_n)$

由唯一性可知 $N_n(x)\equiv L_n(x)$，只是算法不同，故其余项也相同，即 $f[x,x_0,...,x_{n}]\omega_{n+1}(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\omega_{n+1}(x)$ → $f[x_0,...,x_k]=\large\frac{f^{(k)}(\xi)}{k!}$，$\xi\in(x_{min},x_{max})$

等距节点公式：

当节点等距分布时 $x_i=x_0+ih$ (i=0,...,n)

• 向前差分：$\Delta f_i=f_{i+1}-f_i$ (1阶向前差分)；$\Delta^kf_i=\Delta(\Delta^{k-1}f_i)=\Delta^{k-1}f_{i+1}-\Delta^{k-1}f_i$ (k阶向前差分)

  牛顿前插公式：设$x=x_0+th(0\le t\le1)$，则$N_n(x)=N_n(x_0+th)=\sum^n_{k=0}\left(\begin{array}{c}t\\k\end{array}\right)\Delta^kf(x_0)$，$R_n(x)=\large\frac{f^{(n+1)}(\xi)}{(n+1)!}t(t-1)...(t-n)h^{n+1}$，$\xi\in(x_0,x_n)$

• 向后差分：$\nabla f_i=f_{i}-f_{i-1}$ (1阶向后差分)；$\nabla^kf_i=\nabla^{k-1}f_{i}-\nabla^{k-1}f_{i-1}$ (k阶向后差分)

  牛顿后插公式：设$x=x_n+th(-1\le t\le0)$，则$N_n(x)=N_n(x_n+th)=\sum^n_{k=0}(-1)^k\left(\begin{array}{c}-t\\k\end{array}\right)\nabla^kf(x_n)$，$R_n(x)=\large\frac{f^{(n+1)}(\xi)}{(n+1)!}t(t+1)...(t+n)h^{n+1}$，$\xi\in(x_0,x_n)$

  一般当x靠近$x_0$时用前插，靠近$x_n$时用后插，故两种公式亦称为表初公式和表末公式。

• 中心差分：$\delta^k f_i=\delta^{k-1}f_{i+\frac{1}{2}}-\delta^{k-1}f_{i-\frac{1}{2}}$，其中 $f_{i\pm\frac{1}{2}}=f(x_i\pm\frac{h}{2})$