插值法

插值法的定义

设函数 $f(x)$ 在区间 $[a,b]$ 上有定义，已知其在 $n+1$ 个互异节点 $x_0,x_1,\dots,x_n$ 处的函数值

$$y_i=f(x_i),\quad i=0,1,\dots,n$$

构造函数 $g(x)$，满足

$$g(x_i)=y_i,\quad i=0,1,\dots,n$$

这称为插值法。

其中，$f(x)$ 为求插函数，$g(x)$ 为插值函数，$[a,b]$ 为插值区间，$x_0,x_1,\dots,x_n$ 为插值节点，$x$ 为插值点。

• $x$ 在插值区间内称为内插。
• $x$ 在插值区间外但仍用 $g(x)$ 近似 $f(x)$，称为外插或外推。

多项式插值的存在唯一性

设 $x_0,x_1,\dots,x_n$ 是 $n+1$ 个互异节点，给定函数值 $f(x_k)$，$k=0,1,\dots,n$。则存在唯一的次数不超过 $n$ 的多项式 $p_n(x)\in P_n$，使得

$$p_n(x_k)=f(x_k),\quad k=0,1,\dots,n$$

Lagrange 插值多项式

设 $x_0,x_1,\dots,x_n$ 是 $n+1$ 个互异节点。对每个 $i=0,1,\dots,n$，定义

$$l_i(x)=\prod_{\substack{j=0\\ j\ne i}}^n \frac{x-x_j}{x_i-x_j}$$

则有

$$l_i(x_k)=\delta_{ik},\quad i,k=0,1,\dots,n$$

其中 $\delta_{ik}$ 为 Kronecker 记号。由此构造

$$p_n(x)=\sum_{i=0}^n f(x_i)\,l_i(x)$$

称为 Lagrange 插值多项式，它满足

$$p_n(x_k)=f(x_k),\quad k=0,1,\dots,n$$

且次数不超过 $n$。Lagrange 基本多项式只依赖节点，与 $f(x)$ 无关。

Lagrange 插值多项式的余项公式

设 $f(x)$ 在区间 $[a,b]$ 上具有 $n$ 阶连续导数，且在 $(a,b)$ 内存在有界的 $n+1$ 阶导数。记

$$w_{n+1}(x)=\prod_{i=0}^n (x-x_i)$$

则对任意 $x\in [a,b]$，存在 $\xi\in (a,b)$，使得

$$r_n(x)=f(x)-p_n(x)$$

满足

$$r_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)$$

即

$$f(x)=p_n(x)+\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)$$

其中 $\xi$ 依赖于节点和插值点。

Lagrange 插值多项式的误差估计

插值误差

$$r_n(x)=f(x)-p_n(x)$$

由余项公式得

$$r_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)$$

其中

$$w_{n+1}(x)=\prod_{i=0}^n (x-x_i),\quad \xi\in(a,b)$$

若记

$$M_{n+1}=\max_{a\le x\le b}\left|f^{(n+1)}(x)\right|$$

则对任意 $x\in[a,b]$，有

$$|r_n(x)|\le \frac{M_{n+1}}{(n+1)!}\left|w_{n+1}(x)\right|$$

误差主要由 $f^{(n+1)}$ 和 $w_{n+1}(x)$ 决定。

等距节点插值误差的分布特征与 Runge 现象

当插值节点为等距节点时，记 $x=x_0+th$，则有

$$w_{n+1}(x)=h^{n+1}q(t),\qquad q(t)=t(t-1)\cdots(t-n)$$

由此

$$|r_n(x)|\le \frac{M_{n+1}}{(n+1)!}|w_{n+1}(x)|$$

误差大小与 $|q(t)|$ 的分布直接相关。

对等距节点，误差通常在区间中部较小、两端较大；外插距离越远，误差往往增长越快。

在等距节点上做高次多项式插值时，端点附近可能出现并随次数升高而加剧的振荡，这称为 Runge 现象。

差商的定义

设 $x_0,x_1,\dots,x_n$ 为互异节点。零阶差商定义为

$$f[x_i]=f(x_i),\quad i=0,1,\dots,n$$

一阶差商为

$$f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}$$

一般地，对 $k\ge 1$，

$$f[x_0,x_1,\dots,x_k]=\frac{f[x_1,x_2,\dots,x_k]-f[x_0,x_1,\dots,x_{k-1}]}{x_k-x_0}$$

$n$ 阶差商还可写为

$$w_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n)$$

则

$$f[x_0,x_1,\dots,x_n] = \sum_{i=0}^n \frac{f(x_i)}{\prod_{\substack{j=0\\j\ne i}}^n (x_i-x_j)} = \sum_{i=0}^n \frac{f(x_i)}{w_{n+1}'(x_i)}$$

该式表明 $n$ 阶差商对节点具有对称性。

Newton 插值多项式

设 $x_0,x_1,\dots,x_n$ 是 $n+1$ 个互异节点，$f$ 在这些节点上的函数值已知。以差商为系数构造

$$N_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,\dots,x_n](x-x_0)(x-x_1)\cdots(x-x_{n-1})$$

这称为 Newton 插值多项式，其一般项为

$$N_n(x)=\sum_{k=0}^n f[x_0,x_1,\dots,x_k]\prod_{j=0}^{k-1}(x-x_j)$$

其中约定当 $k=0$ 时空乘积为 $1$。并满足

$$N_n(x_i)=f(x_i),\quad i=0,1,\dots,n$$

它与 Lagrange 插值多项式本质相同，只是表示形式不同。

Newton 形式便于增点：增加节点 $x_{n+1}$ 时，只需补一项新的差商项。

Newton 插值多项式的余项

设 $x_0,x_1,\dots,x_n$ 是 $n+1$ 个互异节点，记

$$w_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n)$$

则

$$f(x)=N_n(x)+f[x_0,x_1,\dots,x_n,x]\,w_{n+1}(x)$$

其中 $f[x_0,x_1,\dots,x_n,x]$ 是关于节点 $x_0,x_1,\dots,x_n,x$ 的 $n+1$ 阶差商。

若 $f(x)$ 在区间 $[a,b]$ 上具有 $n+1$ 阶连续导数，则存在 $\xi\in(a,b)$，使得

$$f[x_0,x_1,\dots,x_n,x]=\frac{f^{(n+1)}(\xi)}{(n+1)!}$$

从而

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

因此其余项公式与 Lagrange 相同。

Newton 前差和后差插值公式

当插值节点等距时，设

$$x_i=x_0+ih,\quad i=0,1,\dots,n$$

前向差分为

$$\Delta f(x_i)=f(x_{i+1})-f(x_i),\quad \Delta^k f(x_i)=\Delta(\Delta^{k-1}f(x_i))$$

后向差分为

$$\nabla f(x_i)=f(x_i)-f(x_{i-1}),\quad \nabla^k f(x_i)=\nabla(\nabla^{k-1}f(x_i))$$

取

$$x=x_0+th,\qquad t=\frac{x-x_0}{h}$$

则 Newton 前差公式为

$$N_n(x)=N_n(x_0+th)=f(x_0)+t\Delta f(x_0)+\frac{t(t-1)}{2!}\Delta^2 f(x_0)+\cdots+\frac{t(t-1)\cdots(t-n+1)}{n!}\Delta^n f(x_0)$$

适合插值点靠近 $x_0$ 时使用。

取

$$x=x_n+th,\qquad t=\frac{x-x_n}{h}$$

则 Newton 后差公式为

$$N_n(x)=N_n(x_n+th)=f(x_n)+t\nabla f(x_n)+\frac{t(t+1)}{2!}\nabla^2 f(x_n)+\cdots+\frac{t(t+1)\cdots(t+n-1)}{n!}\nabla^n f(x_n)$$

适合插值点靠近 $x_n$ 时使用。

Hermite 插值多项式

设函数 $f(x)$ 在插值节点 $x_0,x_1,\dots,x_n\in [a,b]$ 处的函数值及一阶导数分别为 $f(x_i),f'(x_i)$，$i=0,1,\dots,n$。则存在唯一的多项式 $H_{2n+1}(x)\in P_{2n+1}$，满足

$$H_{2n+1}(x_i)=f(x_i),\quad H_{2n+1}'(x_i)=f'(x_i),\qquad i=0,1,\dots,n$$

设 $l_i(x)$ 为对应的 Lagrange 基本多项式，则

$$H_{2n+1}(x)=\sum_{i=0}^n f(x_i)\bigl[1-2(x-x_i)l_i'(x_i)\bigr]l_i^2(x)+\sum_{i=0}^n f'(x_i)(x-x_i)l_i^2(x)$$

这是一阶导数情形下的 Hermite 插值多项式。

Hermite 插值多项式的余项和误差估计

若 $f(x)$ 在 $[a,b]$ 上具有 $2n+2$ 阶连续导数，则对任意 $x\in [a,b]$，存在 $\xi\in(a,b)$，使得

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

即

$$f(x)=H_{2n+1}(x)+\frac{f^{(2n+2)}(\xi)}{(2n+2)!}\prod_{i=0}^n (x-x_i)^2$$

若记

$$M_{2n+2}=\max_{a\le x\le b}\left|f^{(2n+2)}(x)\right|$$

则有

$$|R_{2n+1}(x)|\le \frac{M_{2n+2}}{(2n+2)!}\left|\prod_{i=0}^n (x-x_i)^2\right|$$

进一步

$$\max_{a\le x\le b}|f(x)-H_{2n+1}(x)|\le \frac{M_{2n+2}}{(2n+2)!}\max_{a\le x\le b}\left|\prod_{i=0}^n (x-x_i)^2\right|$$

分段线性插值及其误差估计

设 $a=x_1<x_2<\cdots<x_{n+1}=b$ 为区间 $[a,b]$ 上的互异节点，已知函数值 $f_k=f(x_k)$，$k=1,2,\dots,n+1$。求分段函数 $g_1(x)$，使其在每个子区间 $[x_i,x_{i+1}]$ 上是线性多项式，且 $g_1(x)\in C[a,b]$，并满足

$$g_1(x_k)=f_k,\quad k=1,2,\dots,n+1$$

这称为 $f(x)$ 在 $[a,b]$ 上的分段线性插值函数。在每个子区间上

$$g_{1,i}(x)=f(x_i)+f[x_i,x_{i+1}](x-x_i),\quad x\in [x_i,x_{i+1}]$$

其中

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

并记

$$g_1(x)=g_{1,i}(x),\quad x\in [x_i,x_{i+1}],\quad i=1,2,\dots,n$$

令

$$h_i=x_{i+1}-x_i,\quad h=\max_{1\le i\le n} h_i$$

若 $f\in C^2[a,b]$，则在每个子区间上有

$$\max_{x_i\le x\le x_{i+1}} |f(x)-g_{1,i}(x)|\le \frac{h_i^2}{8}\max_{x_i\le x\le x_{i+1}} |f''(x)|$$

从而

$$\max_{a\le x\le b} |f(x)-g_1(x)|\le \frac{h^2}{8}M_2$$

其中

$$M_2=\max_{a\le x\le b}|f''(x)|$$

分段抛物线插值及其误差估计

设 $a=x_1<x_2<\cdots<x_{2m+1}=b$ 为区间 $[a,b]$ 上的互异节点，已知函数值 $f_k=f(x_k)$，$k=1,2,\dots,2m+1$。构造分段函数 $g_2(x)$，使其在每个区间 $[x_{2i-1},x_{2i+1}]$ 上为经过三点 $(x_{2i-1},f_{2i-1})$、$(x_{2i},f_{2i})$、$(x_{2i+1},f_{2i+1})$ 的二次插值多项式 $g_{2,i}(x)$，即

$$g_{2,i}(x_k)=f_k,\quad k=2i-1,2i,2i+1,\qquad i=1,2,\dots,m$$

并定义

$$g_2(x)=g_{2,i}(x),\quad x\in [x_{2i-1},x_{2i+1}],\qquad i=1,2,\dots,m$$

这称为 $f(x)$ 在 $[a,b]$ 上的分段抛物线插值函数。

记

$$h_i=x_{i+1}-x_i,\qquad h=\max_{1\le i\le 2m} h_i$$

若 $f\in C^3[a,b]$，并记

$$M_3=\max_{a\le x\le b}|f^{(3)}(x)|$$

则在每个区间上有

$$\max_{x_{2i-1}\le x\le x_{2i+1}}|f(x)-g_{2,i}(x)|\le \frac{M_3}{12}h^3$$

从而

$$\max_{a\le x\le b}|f(x)-g_2(x)|\le \frac{M_3}{12}h^3$$

因此分段抛物线插值的误差阶为 $O(h^3)$。

分段三次 Hermite 插值及其误差估计

设 $a=x_1<x_2<\cdots<x_{n+1}=b$ 为 $[a,b]$ 上的互异节点，已知节点函数值与导数值

$$f_k=f(x_k),\quad f_k'=f'(x_k),\qquad k=1,2,\dots,n+1$$

求分段函数 $S_h(x)$，使其在每个子区间 $[x_k,x_{k+1}]$ 上为三次多项式，且 $S_h(x)\in C^1[a,b]$，并满足

$$S_h(x_k)=f_k,\quad S_h'(x_k)=f_k',\qquad k=1,2,\dots,n+1$$

这称为 $f(x)$ 在 $[a,b]$ 上的分段三次 Hermite 插值函数。

在每个子区间 $[x_k,x_{k+1}]$ 上，$S_h(x)$ 是以端点 $x_k,x_{k+1}$ 及其一阶导数值构造的两点三次 Hermite 插值多项式，记为 $S_{h,k}(x)$，并记

$$S_h(x)=S_{h,k}(x),\qquad x\in[x_k,x_{k+1}],\quad k=1,2,\dots,n$$

记

$$h_k=x_{k+1}-x_k,\qquad h=\max_{1\le k\le n}h_k$$

若 $f\in C^4[a,b]$，则在每个子区间上有

$$\max_{x_k\le x\le x_{k+1}}|f(x)-S_{h,k}(x)| \le \frac{h_k^4}{384}\max_{x_k\le x\le x_{k+1}}|f^{(4)}(x)|$$

从而

$$\max_{a\le x\le b}|f(x)-S_h(x)| \le \frac{M_4}{384}h^4, \qquad M_4=\max_{a\le x\le b}|f^{(4)}(x)|$$

因此分段三次 Hermite 插值的误差阶为 $O(h^4)$。

样条函数的定义

设 $a=x_1<x_2<\cdots<x_{n+1}=b$ 为区间 $[a,b]$ 上的互异节点。若分段函数 $S(x)$ 满足：

• 在每个子区间 $[x_k,x_{k+1}]$ 上，$S(x)$ 都是 $k$ 次多项式
• $S(x)\in C^{k-1}[a,b]$

则称 $S(x)$ 为以 $x_1,x_2,\dots,x_{n+1}$ 为节点的 $k$ 次样条函数，简称 $k$ 次样条。

二次基样条插值

设节点为等距节点

$$x_i=a+(i-1)h,\quad i=1,2,\dots,n+1,\qquad h=\frac{b-a}{n}$$

取二次样条基函数

$$g_i(x)=\phi\!\left(\frac{x-x_i}{h}\right),\quad i=0,1,\dots,n+2$$

其中 $\phi(t)$ 为分段二次函数

$$\phi(t)=\frac{2}{3} \begin{cases} 0, & |t|>\frac{3}{2} \\ t^2+3t+\frac{9}{4}, & -\frac{3}{2}\le t<-\frac{1}{2} \\ -2t^2+\frac{3}{2}, & -\frac{1}{2}\le t<\frac{1}{2} \\ t^2-3t+\frac{9}{4}, & \frac{1}{2}\le t\le \frac{3}{2} \end{cases}$$

则二次基样条插值函数为

$$S(x)=\sum_{k=0}^{n+2}\alpha_k g_k(x)$$

其中 $\alpha_k$ 为待定系数。若已知节点函数值 $f_i=f(x_i)$，则插值条件

$$S(x_i)=f_i,\quad i=1,2,\dots,n+1$$

化为

$$\alpha_{i-1}+6\alpha_i+\alpha_{i+1}=6f_i,\quad i=1,2,\dots,n+1$$

再附加端点一阶导数条件

$$S'(a)=f'(a),\qquad S'(b)=f'(b)$$

则有

$$\alpha_0-\alpha_2=-\frac{3}{2}hf'(a),\qquad -\alpha_n+\alpha_{n+2}=\frac{3}{2}hf'(b)$$

联立即可唯一确定二次基样条插值函数。

三次样条插值

设节点组 $a=x_1<x_2<\cdots<x_{n+1}=b$，已知节点函数值 $f(x_i)=f_i$，$i=1,2,\dots,n+1$)。若分段函数

$$S(x)= \begin{cases} S_1(x), & x\in [x_1,x_2] \\ \cdots \\ S_i(x), & x\in [x_i,x_{i+1}] \\ \cdots \\ S_n(x), & x\in [x_n,x_{n+1}] \end{cases}$$

满足 $S(x)\in C^2[a,b]$，且每个 $S_i(x)$ 都是三次的多项式，并满足插值条件

$$S(x_i)=f_i,\quad i=1,2,\dots,n+1$$

则称 $S(x)$ 为函数 $f(x)$ 的三次样条插值函数。

三次样条插值的求解与边界条件

设

$$h_i=x_{i+1}-x_i,\quad b_i=\frac{f_{i+1}-f_i}{h_i},\qquad i=1,2,\dots,n$$

记

$$\alpha_i=S''(x_i),\qquad i=1,2,\dots,n+1$$

则在每个子区间 $[x_i,x_{i+1}]$ 上，三次样条可写为

$$S_i(x)=f_i+\left[b_i-\frac{h_i}{6}\left(2\alpha_i+\alpha_{i+1}\right)\right](x-x_i)+\frac{\alpha_i}{2}(x-x_i)^2+\frac{\alpha_{i+1}-\alpha_i}{6h_i}(x-x_i)^3$$

因此三次样条的求解可归结为确定 $\alpha_1,\alpha_2,\dots,\alpha_{n+1}$，对内点 $i=2,3,\dots,n$，有方程

$$\mu_i\alpha_{i-1}+2\alpha_i+\lambda_i\alpha_{i+1}=d_i$$

其中

$$\mu_i=\frac{h_{i-1}}{h_{i-1}+h_i},\qquad \lambda_i=\frac{h_i}{h_{i-1}+h_i}$$ $$d_i=\frac{6(b_i-b_{i-1})}{h_{i-1}+h_i}$$

这给出 $n-1$ 个内点方程，再配合边界条件即可唯一确定全部 $\alpha_i$，常用边界条件如下

• 自然边界条件

$$S''(x_1)=S''(x_{n+1})=0$$

即

$$\alpha_1=\alpha_{n+1}=0$$

此时将上式与内点方程联立，即可求得全部 $\alpha_i$。

• 完备边界条件

$$S'(a)=f'(a),\quad S'(b)=f'(b)$$

此时边界方程为

$$2\alpha_1+\alpha_2=d_1,\qquad \alpha_n+2\alpha_{n+1}=d_{n+1}$$

其中

$$d_1=\frac{6}{h_1}\bigl(b_1-f'(a)\bigr),\qquad d_{n+1}=\frac{6}{h_n}\bigl(f'(b)-b_n\bigr)$$

于是得到关于 $\alpha_1,\alpha_2,\dots,\alpha_{n+1}$ 的 $n+1$ 阶三对角线性方程组

$$\begin{pmatrix} 2 & 1 & & & \\ \mu_2 & 2 & \lambda_2 & & \\ & \mu_3 & 2 & \lambda_3 & \\ & & \ddots & \ddots & \ddots \\ & & & \mu_n & 2 & \lambda_n \\ & & & & 1 & 2 \end{pmatrix} \begin{pmatrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n \\ \alpha_{n+1} \end{pmatrix} = \begin{pmatrix} d_1 \\ d_2 \\ \vdots \\ d_n \\ d_{n+1} \end{pmatrix}$$

其系数矩阵强优对角，故方程组有唯一解。解出 $\alpha_i$ 后，再代入 $S_i(x)$ 的表达式即可得到三次样条的分段表示

完备三次样条的误差估计

设函数 $f(x)\in C^4[a,b]$，$S_C(x)$ 表示 $f(x)$ 在 $\{x_i\}_{i=1}^{n+1}$ 上的完备三次样条插值函数，则

$$\max_{a\le x\le b}|f(x)-S_C(x)|\le \frac{5}{384}M_4h^4$$ $$\max_{a\le x\le b}|f'(x)-S_C'(x)|\le \frac{1}{24}M_4h^3$$ $$\max_{a\le x\le b}|f''(x)-S_C''(x)|\le \frac{3}{8}M_4h^2$$

其中

$$M_4=\max_{a\le x\le b}|f^{(4)}(x)|,\qquad h=\max_{1\le i\le n}h_i$$