1 拉格朗日插值

1.1 多项式插值

用多项式作为研究插值的工具，称为代数插值，其基本问题是：已知函数$f(x)$在区间$[a,b]$上$n+1$个不同点$x_0,x_1,\dots ,x_n$处的函数值$y_i=f(x_i)(i=0,1,\dots ,n)$，求一个至多$n$次的多项式：

$${\phi }_n(x)=a_0+a_{1}x+\cdots +a_n{x}^n(5-1)$$

使其在给定点处与$f(x)$同值，即满足插值条件

$${\phi }_n(x_i)=f(x_i)=y_i(i=0,1,\dots ,n)(5-2)$$

${\phi }_n(x)$称为插值多项式，$x_i(i=0,1,\dots ,n)$称为插值节点，简称节点，[a,b]称为插值区间。

待补充 124

1.2 插值多项式的误差估计

插值多项式与被插函数之间的差：

$$R_n(x)=f(x)-{\phi }_n(x)$$

称为截断误差，又称为插值余项。

假定 $f(x)$ 在区间 $[a,b]$ 上 $n+1$ 次连续可导，对 $[a,b]$ 上任意点 $x$ ，且 $x\ne x_i(i=0,1,\dots ,n)$ ，构造辅助函数：

$$\psi (t)=f(t)-{\phi }_n(t)-\frac{R_n(x)}{w_{n+1}(x)}{w}_{n+1}(t)(5-4)$$

其中$w_{n+1}(t)=\prod _{j=0}^n(t-x_j)$，显然：

$$\psi (x)=f(x)-{\phi }_n(x)-\frac{R_n(x)}{w_{n+1}(x)}{w}_{n+1}(x)=0$$

由插值条件（5-2），$R_n(x_i)=0(i=0,1,\dots ,n)$，故函数 $\psi (t)$ 在区间 $[a,b]$ 内至少有 $n+2$ 个零点 $x,x_0,x_1,\dots ,x_n$ 。由罗尔（Rolle）定理，函数：

$${\psi }^{\prime }(t)=f^{\prime }(t)-{\phi }_n^{\prime }(t)-\frac{R_n(x)}{w_{n+1}(x)}{w}_{n+1}^{\prime }(t)$$

在$(a,b)$内至少有$n+1$个零点。反复使用罗尔定理，可以得出：

$${\psi }^{(n+1)}(t)=f^{(n+1)}(t)-{\phi }_n^{(n+1)}(t)-\frac{R_n(x)}{w_{n+1}(x)}{w}_{n+1}^{(n+1)}(t)$$

在$(a,b)$内至少有一个零点，设为$\xi$，即：

$${\psi }^{(n+1)}(\xi )=0$$

因为${\phi }_n(t)$为至多$n$次多项式，$w_{(n+1)}(t)$为最高次项系数为1的$n+1$次多项式，因而：

$${\phi }_n^{(n+1)}(t)\equiv 0,w_{(n+1)}^{(n+1)}(t)=(n+1)!$$

于是有：

$${\psi }^{(n+1)}(\xi )=f^{(n+1)}(\xi )-\frac{R_n(x)}{w_{n+1}(x)}(n+1)!=0$$

所以：

$$R_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}{w}_{n+1}(x),\xi \in (a,b)(5-5)$$

定理5.1

设$x_0,x_1,\dots ,x_n$是区间$[a,b]$上的互异节点，${\phi }_n(x)$是过这组节点的$n$次插值多项式。如果$f(x)$在$[a,b]$上$n+1$次连续可导，则对$[a,b]$内任意点$x$，插值余项为：

$$R_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}{w}_{n+1}(x),\xi \in (a,b)(5-5)$$

1.3 Lagrange插值多项式

先讨论只有两个节点 $x_0,x_1(n=1)$ 的插值多项式。此时插值多项式应设为 ${\phi }_1(x)=a_0+a_{1}x$，且满足插值条件：

$$\begin{gathered} {\phi }_1(x_0)=a_0+a_1{x}_0=y_0=f(x_0) \\ {\phi }_1(x_1)=a_0+a_1{x}_1=y_1=f(x_1) \end{gathered}$$

解此方程组得：

$$a_0=\frac{y_1{x}_0-y_0{x}_1}{x_0-x_1},a_1=\frac{y_0-y_1}{x_0-x_1}$$

所以，两个节点的一次插值多项式为：

$${\phi }_1(x)=\frac{y_1{x}_0-y_0{x}_1}{x_0-x_1}+\frac{y_0-y_1}{x_0-x_1}x(5-6)$$

此时是用过两点$(x_0,y_0),(x_1,y_1)$的直线$y={\phi }_1(x)$近似曲线$y=f(x)$，故这种插值又称为线性插值。

如果将式（5-6）改写成以下形式：

$${\phi }_1(x)=y_0\frac{x-x_1}{x_0-x_1}+y_1\frac{x-x_0}{x_1-x_0}x(5-7)$$

式（5-7）中，${\phi }_1(x)$被表示为两个线性函数的线性组合，记：

$$l_0(x)=\frac{x-x_1}{x_0-x_1},l_1(x)=\frac{x-x_0}{x_1-x_0}$$

显然，它们满足：

$$\begin{gathered} l_0(x_0)=1,l_0(x_1)=0 \\ {l}_1(x_0)=0,l_1(x_1)=1 \end{gathered}$$

即 $l_i(x)(i=0,1)$在对应的插值点$x_i$处取值为1，在其他点处取值为0。不难想象，以对应点处的函数值为系数对它们作线性组合所得的函数，不仅仍是线性的，且必定满足插值条件。由此得到启发，当节点增多到n+1时，可以先构造n次多项式$l_i(x)(i=0,1,\cdots ,n)$，它们满足：

$$l_i(x_j)=\{\begin{array}{l}0,j\ne i\\ 1,j=i\end{array}(5-8)$$

然后以对应点处的函数值为系数作线性组合，即得所要求的插值多项式。下面推导$l_i(x)(i=0,1,\cdots ,n)$的表达式。

由式（5-8），多项式$l_i(x)$有n个根$x_j(j=0,1,\cdots ,n,j\ne i)$，且$l_i(x_i)=1$，故它必定是以下形式：

$$l_i(x)=\frac{(x-x_0)\cdots (x-x_{i-1})(x-x_{i+1})\cdots (x-x_n)}{(x_i-x_0)\cdots (x_i-x_{i-1})(x_i-x_{i+1})\cdots (x_i-x_n)}=\prod _{j=0,j\ne i}^n\frac{x-x_j}{x_i-x_j}(i=0,1,\cdots ,n)(5-9)$$

这些函数称为Lagrange插值基函数。利用它们立即得出插值问题的解：

$${\phi }_n(x)=\sum _{i=0}^n{y}_i{l}_i(x)=\sum _{i=0}^n{y}_i\prod _{j=0,j\ne i}^n\frac{x-x_j}{x_i-x_j}(5-10a)$$

事实上，因为每个插值函数$l_i(x)(i=0,1,\dots ,n)$都是$n$次多项式，故${\phi }_n(x)$是至多$n$次多项式。由式（5-8）又得：

$${\phi }_n(x_k)=\sum _{i=0}^n{y}_i{l}_i(x_k)=y_k(k=0,1,\dots ,n)$$

即${\phi }_n(x)$满足插值条件（5-2）。

式(5-10a)称为$n$次Lagrange插值多项式。为了便于区别，我们常用$L_n(x)$代替${\phi }_n(x)$，以突出这是由Lagrange插值所得到的插值多项式，即：

$$L_n(x)=\sum _{i=0}^n{y}_i{l}_i(x)(5-10b)$$

2 牛顿（Newton）插值

2.1 差商

定义5.1

设有函数$f(x),x_0,x_1,x_2,\dots$为一系列互不相等的点，称$\frac{f(x_i)-f(x_j)}{x_i-x_j}$为$f(x)$关于点$x_i,x_j$的一阶差商（也称均差），记为$f[x_i,x_j]$，即：

$$$$

2.3 差分

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

定义5.2

4 埃尔米特（Hermite）插值

如果对插值函数，不仅要求它在节点处与函数同值，而且要求它与函数有相同的一阶、二阶甚至更高阶的导数值，这就是Hermite插值问题。本节主要讨论在节点处插值函数与函数的值及一阶导数值均相等的Hermite插值。

4.1 Hermite插值