插值法

函数插值是对函数的离散数据建立简单的数学模型

设函数y=f(x)在区间[a,b]上的节点x₀,x₁,…x_n上的函数值为y₀,y₁,…y_n，构造一个次数不超过n次的代数多项式

$$P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$$

几何意义：通过已知的n+1个相异节点(x_i,y_i)，i=0,1,…n，构造出一条代数多项式曲线y=P(x)，使其近似于被插值函数曲线y=f(x)

拉格朗日插值

线性插值

过(x₀, y₀), (x₁, y₁)的直线为

$$L(x) = \frac{x - x_1}{x_0 - x_1} y_0 + \frac{x - x_0}{x_1 - x_0} y_1$$

记

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

l₀(x)与l₁(x)称为线性插值基函数，且有性质

$$l_0(x_0) = 1, \quad l_0(x_1) = 0,\quad l_1(x_0) = 0, \quad l_1(x_1) = 1$$

抛物线插值

$$l_{0}(x) = \frac{(x - x_{1})(x - x_{2})}{(x_{0} - x_{1})(x_{0} - x_{2})}$$

$$l_{1}(x) = \frac{(x - x_{0})(x - x_{2})}{(x_{1} - x_{0})(x_{1} - x_{2})}$$

$$l_{2}(x) = \frac{(x - x_{0})(x - x_{1})}{(x_{2} - x_{0})(x_{2} - x_{1})}$$

因此有

$$L(x) = \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$$

拉格朗日插值多项式

$$l_k(x) = \prod_{\substack{i=0 \\ i \neq k}}^n \frac{x - x_i}{x_k - x_i}$$

$$L(x) = \sum_{k=0}^{n} l_k(x) y_k$$

余项

设f(x)在区间[a,b]上有n+1阶导数，则n次插值多项式L(x)对任意x∈[a,b]，有插值余项

$$R(x) = f(x) - L(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \omega(x)$$

其中

$$\omega(x) = \prod_{i=0}^{n} (x - x_i),a<\xi<b$$

且依赖于x

小结

1. 插值多项式L(x)只与数据x_i，f(x_i)有关，与节点排列顺序无关，与f(x)无关，但余项R(x)与f(x)有关
2. f(x)是次数不超过n次的多项式，取n+1个节点插值时，插值多项式就是其自身
3. 基函数之和为1，l₀(x)+l₁(x)+…+l_n(x)=1
4. n+1个节点的插值多项式不超过n次，不超过n+1项，可求插值区间[a,b]上任一点函数的近似值
5. 内插比外推精度高。当给定m个点，取n+1个节点(n+1≤m)构造插值多项式，求x点的函数值时，n+1个节点取尽可能靠近x时，余项小，近似程度高
6. 当节点数变化时，需重新计算全部基函数，因为基函数和每一个节点都有关
7. n=1时是线性插值，n=2时是抛物线插值

牛顿插值

差商

• 一阶差商

$$f[x_{i}, x_{i+1}]=\frac{f(x_{i+1}) - f(x_i)}{x_{i+1} - x_i}$$

• 二阶差商

$$f[x_{i}, x_{i+1}, x_{i+2}]=\frac{f[x_{i+1}, x_{i+2}] - f[x_{i}, x_{i+1}]}{x_{i+2} - x_{i}}$$

• n阶差商

$$f[x_0, x_1, \cdots, x_m] = \frac{f[x_1, x_2, \cdots, x_m] - f[x_0, x_1, \cdots, x_{m-1}]}{x_m - x_0}$$

• 差商表

• 牛顿插值

令

$$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)(x - x_1)\cdots(x - x_{n-1})$$

$$R(x) = f[x_0, x_1, \cdots, x_n, x](x - x_0)(x - x_1)\cdots(x - x_n)$$

有f(x)=N(x)+R(x)，其中N(x)是f(x)的前n+1项，是x的n次多项式，称为牛顿插值多项式，可看出牛顿插值多项式是上表对角线上的元素与右端同行因子的乘积之和，R(x)是f(x)的最后一项，称之为牛顿插值余项

小结

1. 牛顿插值多项式N(x)的次数不超过n次，项数不超过n+1项，各项系数是各阶差商

2. 在节点上牛顿插值多项式N(x)等于被插值函数f(x)，即N(x_i)=f(x_i),i=0,1,2,…,n，此时余项R(x_i)=0

3. 增加一个节点时，只需N(x)再增加一项，N(x)原有各项均不变

   当n=1时，取x₀,x₁进行插值，有N(x)=f(x₀)+f[x₀,x₁](x-x₀)

   当n=2时，取x₀,x₁,x₂进行插值，有N(x)=f(x₀)+f[x₀,x₁](x-x₀)+f[x₀,x₁,x₂](x-x₀)(x-x₁)

   可见，增加一个节点x₂时，只是增加了f[x₀,x₁,x₂](x-x₀)(x-x₁)这一项

   更一般地，设N_n(x)是节点x₀,x₁,…,x_n上的牛顿插值多项式，那么节点x₀,x₁,…,x_n,x_n+1上的牛顿插值多项式N_n+1(x)为

   N_n+1(x)=N_n(x)+f[x₀,x₁,…,x_n,x_n+1](x-x₀)(x-x₁)…(x-x_n)

   上式为N_n+1(x)与N_n(x)的递推关系，即增加一个节点时，只要增加一项即可，而原来的计算结果仍然有用

4. 用差商表示的余项式R(x)比用导数表示的插值余项适用范围更广，并且在f(x)的导数不存在，甚至f(x)不连续时仍有意义

埃尔米特插值

不少问题不但要求在节点上函数值相等，而且还要求它的导数值也相等（即要求在节点上具有一阶光滑度），甚至要求高阶导数也相等，满足这种要求的插值多项式就是埃尔米特（Hermite）插值多项式

$$\left\{ \begin{array}{l} H(x_i)=y_i \\ H'(x_i)=y_i' \end{array} \right.$$

• 埃尔米特插值多项式

$$H_{2n+1}(x) = \sum_{j=0}^{n} \left[ 1 - 2(x - x_j) \sum_{\substack{k=0 \\ k \neq j}}^{n} \frac{1}{x_j - x_k} \right] l_j^2(x) f(x_j) + \sum_{j=0}^{n} (x - x_j) l_j^2(x) f'(x_j)$$

• 插值余项

$$R_{2n+1}(x) = f(x) - H_{2n+1}(x) = \frac{f^{(2n+2)}(\xi)}{(2n+2)!} \omega^2(x)$$

其中ξ∈(a,b)，且与x无关，ω(x)=(x-x₀)(x-x₁)…(x-x_n)

几何意义：曲线y=H_2n+1(x)与曲线y=f(x)在插值节点处有公切线

高次插值的龙格现象