Chapter5：插值法

概述#

这一章的核心是：

已知函数在若干节点上的信息，用一个更容易计算的函数去近似原函数。

这里的“信息”可以有两类：

只知道函数值：得到 Lagrange 插值、Newton 插值、分段线性插值、样条插值等。
同时知道函数值和导数值：得到 Hermite 插值、分段三次 Hermite 插值等。

插值法的基本目标是：

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

如果还要求导数也匹配，则变成：

H(x_i)=f(x_i),\qquad H'(x_i)=f'(x_i)

本章课上反复强调的思想是：

插值多项式存在且唯一，但表达形式可以不同。
Lagrange 形式对称，适合理论分析。
Newton 形式可以逐步增加节点，适合查表和实际计算。
高次插值未必更好，实际计算更常用低次、分段的方法。
样条插值用一组低次多项式拼接出光滑曲线，是工程中很常见的曲线构造方式。

插值问题的基本形式#

多项式插值问题#

已知一组互异节点：

x_0,x_1,\dots,x_n

以及这些节点上的函数值：

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

要求一个次数不超过 $n$ 的多项式 $P_n(x)$ ，使得：

P_n(x_i)=y_i\qquad (i=0,1,\dots,n)

这个 $P_n(x)$ 就叫做 $f(x)$ 关于节点 $x_0,x_1,\dots,x_n$ 的 插值多项式。

存在唯一性#

次数不超过 $n$ 的多项式可以写成：

P_n(x)=a_0+a_1x+\cdots+a_nx^n

代入 $n+1$ 个插值条件，得到关于 $a_0,a_1,\dots,a_n$ 的线性方程组：

\begin{cases} a_0+a_1x_0+\cdots+a_nx_0^n=y_0\\ a_0+a_1x_1+\cdots+a_nx_1^n=y_1\\ \qquad\vdots\\ a_0+a_1x_n+\cdots+a_nx_n^n=y_n \end{cases}

系数矩阵是 Vandermonde 矩阵：

A=\begin{pmatrix} 1&x_0&x_0^2&\cdots&x_0^n\\ 1&x_1&x_1^2&\cdots&x_1^n\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^n \end{pmatrix}

它的行列式为：

\det A=\prod_{0\le i<j\le n}(x_j-x_i)

由于节点互异，所以 $\det A\ne 0$ ，方程组有唯一解。于是插值多项式存在且唯一。

TIP
存在唯一性告诉我们：

Lagrange 插值多项式

Newton 插值多项式

其他基函数写出来的插值多项式

只要满足同一组插值条件，它们就是同一个多项式，只是写法不同。

插值误差余项#

记

\omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j)

若 $f(x)\in C^{n+1}[a,b]$ ，且所有节点都在 $[a,b]$ 内，则对任意 $x\in[a,b]$ ，有：

R_n(x)=f(x)-P_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)

其中 $\xi$ 位于 $a,b$ 之间。

这个公式来自 Rolle 定理。核心思路是构造辅助函数：

\varphi(t)=f(t)-P_n(t)-K\omega_{n+1}(t)

其中 $K$ 取成让 $\varphi(x)=0$ 的值。这样 $\varphi(t)$ 在 $x_0,x_1,\dots,x_n,x$ 处共有 $n+2$ 个零点。反复使用 Rolle 定理，得到 $\varphi^{(n+1)}(\xi)=0$ ，从而推出上面的余项公式。

这个误差公式说明插值误差由两部分共同决定：

$f^{(n+1)}(\xi)$ ：函数高阶导数的大小。
$\omega_{n+1}(x)$ ：节点位置与待求点位置共同决定的乘积项。

WARNING
插值点增多不一定意味着误差变小。
如果高阶导数增长很快，或者 $\omega_{n+1}(x)$ 在区间边缘变得很大，高次插值可能反而产生严重振荡。

Lagrange 插值#

Lagrange 插值基函数#

Lagrange 方法先构造一组特殊的基函数 $l_i(x)$ ：

l_i(x)=\prod_{\substack{0\le j\le n\\ j\ne i}}\frac{x-x_j}{x_i-x_j}\qquad (i=0,1,\dots,n)

它满足：

l_i(x_j)= \begin{cases} 1,&i=j\\ 0,&i\ne j \end{cases}

也就是 $l_i(x)$ 只在自己的节点 $x_i$ 上取 $1$ ，在其他节点上取 $0$ 。

所以 $l_i(x)$ 可以理解为：

第 $i$ 个节点的“开关函数”。

Lagrange 插值公式#

有了这些基函数后，插值多项式可以直接写成：

L_n(x)=\sum_{i=0}^{n}y_i l_i(x)

因为在 $x=x_k$ 时：

L_n(x_k)=\sum_{i=0}^n y_i l_i(x_k)=y_k

所以它满足所有插值条件。

此外还有一个常用性质：

\sum_{i=0}^n l_i(x)=1

原因很简单：对常函数 $f(x)=1$ 做插值，所有节点函数值都是 $1$ ，其插值多项式仍然是 $1$ 。

例：用 Lagrange 插值估计 ln 11.5#

已知函数表：

$x$	10	11	12	13	14
$\ln x$	2.3026	2.3979	2.4849	2.5649	2.6391

线性插值#

取节点 $x_0=11,x_1=12$ 。

基函数为：

l_0(x)=\frac{x-12}{11-12}=-(x-12),\qquad l_1(x)=\frac{x-11}{12-11}=x-11

所以：

L_1(x)=-2.3979(x-12)+2.4849(x-11)

代入 $x=11.5$ ：

\ln 11.5\approx L_1(11.5)=2.3979\times 0.5+2.4849\times 0.5=2.4414

误差余项为：

R_1(x)=\frac{(\ln x)''|_{\xi}}{2!}(x-11)(x-12)

由于：

(\ln x)''=-\frac{1}{x^2}

在 $[11,12]$ 上有：

|(\ln x)''|\le \frac{1}{11^2}=0.0082645

所以：

|R_1(11.5)|\le \frac{1}{2}\times 0.0082645\times 0.5\times 0.5 =1.03306\times 10^{-3}

二次插值#

取节点 $11,12,13$ ，得到：

L_2(11.5)=2.44275

对应误差估计：

|R_2(11.5)|\le 9.3938\times 10^{-5}

查表可得：

\ln 11.5\approx 2.442347

这个例子说明：在局部光滑且节点选择合理时，二次插值通常比线性插值更准确。

Lagrange 插值的优点与问题#

Lagrange 形式的优点：

写法对称。
公式直观。
适合理论推导。
对插值多项式做积分、求导时比较方便。

Lagrange 形式的问题：

每增加一个新节点，原来所有基函数都要重新构造。
对查表类问题不方便。
高次时计算量和数值稳定性都不理想。

老师课上给出的实际判断是：

如果只是查表并逐步增加精度，优先考虑 Newton 插值。

Newton 插值#

差商#

Newton 插值的核心是差商。

零阶差商定义为函数值：

f[x_i]=f(x_i)

一阶差商定义为：

f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j}\qquad (i\ne j)

高阶差商递推定义为：

f[x_i,x_{i+1},\dots,x_{i+k}] = \frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}

一阶差商类似平均斜率，高阶差商可以理解为继续对“变化率”做差商。

如果 $f$ 足够光滑，则有：

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

其中 $\xi$ 位于这些节点之间。

Newton 插值公式#

Newton 插值多项式写成：

N_n(x)=f[x_0]+(x-x_0)f[x_0,x_1] +(x-x_0)(x-x_1)f[x_0,x_1,x_2]+\cdots

一般形式为：

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

也就是：

N_n(x)=f[x_0]+(x-x_0)f[x_0,x_1]+\cdots+(x-x_0)\cdots(x-x_{n-1})f[x_0,\dots,x_n]

差商表的计算#

Newton 插值通常先列差商表。

节点	函数值	一阶差商	二阶差商	三阶差商
$x_0$	$f[x_0]$
$x_1$	$f[x_1]$	$f[x_0,x_1]$
$x_2$	$f[x_2]$	$f[x_1,x_2]$	$f[x_0,x_1,x_2]$
$x_3$	$f[x_3]$	$f[x_2,x_3]$	$f[x_1,x_2,x_3]$	$f[x_0,x_1,x_2,x_3]$

Newton 插值多项式只用差商表中的对角线项：

f[x_0],\quad f[x_0,x_1],\quad f[x_0,x_1,x_2],\quad \dots

如果后来多给了一个新节点 $x_{n+1}$ ，只需要继续向下补差商表，再在原多项式后面加一项：

(x-x_0)(x-x_1)\cdots(x-x_n)f[x_0,x_1,\dots,x_{n+1}]

原来已经算好的部分都能保留。

例：用 Newton 插值估计 ln 11.5#

仍用前面的表格。

取节点 $11,12,13$ ，差商表为：

$x_i$	$y_i=\ln x_i$	一阶差商	二阶差商
11	2.3979
12	2.4849	0.0870
13	2.5649	0.0800	-0.0035

所以：

N_2(x)=2.3979+0.0870(x-11)-0.0035(x-11)(x-12)

代入 $x=11.5$ ：

\ln 11.5\approx N_2(11.5) =2.3979+0.0870\times 0.5+0.0035\times0.5\times0.5 =2.442275

如果继续加入 $x=10,14$ ，可得到四次 Newton 插值：

\ln 11.5\approx N_4(11.5)=2.4423522

Newton 与 Lagrange 的比较#

方法	优点	缺点	更适合的场景
Lagrange 插值	结构对称，公式直观，适合理论分析	新增节点时要重算	推导、积分、求导、理论讨论
Newton 插值	可以逐步增加节点，差商表可复用	表达式不如 Lagrange 对称	查表、逐步提高精度、程序计算

TIP
课堂上的一句话可以概括：
查表时优先用 Newton。想看多项式整体结构、要做理论分析时，Lagrange 更顺手。

等距节点与差分#

差分的定义#

当节点等距时：

x_k=x_0+kh\qquad (k=0,1,\dots,n)

其中 $h$ 为步长。

这时差商可以进一步简化为差分。

向前差分定义为：

\Delta f_k=f_{k+1}-f_k

高阶向前差分递推定义为：

\Delta^m f_k=\Delta^{m-1}f_{k+1}-\Delta^{m-1}f_k

向后差分定义为：

\nabla f_k=f_k-f_{k-1}

差商与差分之间有关系：

f[x_0,x_1,\dots,x_m]=\frac{\Delta^m f_0}{m!h^m}

Newton 前插公式#

令：

t=\frac{x-x_0}{h}

则：

N_n(x)=f_0+t\Delta f_0+\frac{t(t-1)}{2!}\Delta^2 f_0+ \cdots+ \frac{t(t-1)\cdots(t-n+1)}{n!}\Delta^n f_0

这个公式适合 $x$ 靠近表头 $x_0$ 的情形。

Newton 后插公式#

若 $x$ 靠近表尾 $x_n$ ，令：

t=\frac{x-x_n}{h}

则常用向后差分：

N_n(x)=f_n+t\nabla f_n+\frac{t(t+1)}{2!}\nabla^2 f_n+ \cdots+ \frac{t(t+1)\cdots(t+n-1)}{n!}\nabla^n f_n

TIP
差分公式本质上是 Newton 插值在等距节点下的简化。
差商适用于任意互异节点；差分要求节点等距。

高次插值与龙格现象#

很多人会有一个直觉：节点越多，多项式次数越高，插值效果越好。

这个直觉在一般情况下不可靠。

课堂上用 龙格现象（Runge phenomenon） 说明了这一点。典型函数为：

f(x)=\frac{1}{1+x^2},\qquad x\in[-5,5]

如果在 $[-5,5]$ 上取等距节点，然后做高次多项式插值，会发现：

中间区域可能看起来还可以。
区间两端会出现明显振荡。
节点继续增多时，振荡可能变得更严重。

从误差公式看，问题来自：

R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)

这里的 $\omega_{n+1}(x)$ 在区间两端可能很大，高阶导数也可能放大误差。

课堂上的实际经验判断：

工程计算中通常不用很高次的整体多项式。
常见的是零次、一次、二次局部近似。
三次已经很常用。
更高次通常只在问题确实需要时使用。

分段线性插值#

高次整体插值容易振荡，一个自然的改进是把区间切成许多小段，在每一小段上只做一次插值。

设：

x_i\le x\le x_{i+1},\qquad h_i=x_{i+1}-x_i

分段线性插值为：

S(x)=y_i\frac{x_{i+1}-x}{h_i}+y_{i+1}\frac{x-x_i}{h_i}

它的图像就是折线。

分段线性插值的优点：

计算简单。
稳定。
每段只依赖相邻两个节点。
当最大步长 $h=\max h_i\to 0$ 时，折线会越来越接近原函数。

问题也很明显：

函数连续。
导数通常不连续。
图像会有“折角”。

如果只用于粗略查表或画图，分段线性插值很实用。若需要更光滑的曲线，就要引入 Hermite 插值或样条插值。

Hermite 插值#

Hermite 插值问题#

Lagrange / Newton 插值只要求函数值匹配。

Hermite 插值进一步要求导数值也匹配。

已知：

y_i=f(x_i),\qquad y_i'=f'(x_i)\qquad (i=0,1,\dots,n)

要求多项式 $H_{2n+1}(x)$ 满足：

H_{2n+1}(x_i)=y_i, \qquad H'_{2n+1}(x_i)=y_i'

一共有 $2n+2$ 个条件，因此最高可以确定一个 $2n+1$ 次多项式。

WARNING
Hermite 插值在数学上自然，但工程上常常受限。
函数值比较容易测量，导数值通常不容易直接测量。速度、斜率这类量往往要通过局部平均或传感器间接估计，因此会额外引入误差。

Hermite 插值的基函数形式#

设 $l_i(x)$ 是 Lagrange 插值基函数。定义：

h_i(x)=\left[1-2(x-x_i)l_i'(x_i)\right]l_i^2(x)

H_i(x)=(x-x_i)l_i^2(x)

则 Hermite 插值多项式可以写成：

H_{2n+1}(x)=\sum_{i=0}^n \left[y_i h_i(x)+y_i'H_i(x)\right]

这组基函数满足：

h_i(x_j)=\delta_{ij},\qquad h_i'(x_j)=0

H_i(x_j)=0, \qquad H_i'(x_j)=\delta_{ij}

所以 $h_i(x)$ 负责匹配函数值， $H_i(x)$ 负责匹配导数值。

Hermite 插值误差为：

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

用重节点差商做 Hermite 插值#

课堂上更推荐用 Newton 插值的思想做 Hermite 插值。

关键观察是：

f[x_i,x_i]=f'(x_i)

也就是说，导数可以看成“重节点的一阶差商”。

如果有两个节点 $x_0,x_1$ ，并且已知函数值和导数值，就把节点表写成：

节点	函数值
$x_0$	$f(x_0)$
$x_0$	$f(x_0)$
$x_1$	$f(x_1)$
$x_1$	$f(x_1)$

然后按差商表继续计算。遇到 $f[x_i,x_i]$ 时，直接填入 $f'(x_i)$ 。

这种方法的好处是：

不需要硬背 Hermite 基函数公式。
和 Newton 插值完全统一。
增加节点时仍然可以继续扩展差商表。

例：两个节点的三次 Hermite 插值#

已知：

$x_i$	0	1
$y_i$	0	1
$y_i'$	3	9

构造重节点差商表：

节点	函数值	一阶差商	二阶差商	三阶差商
0	0
0	0	3
1	1	1	-2
1	1	9	8	10

解释：

f[0,0]=f'(0)=3

f[1,1]=f'(1)=9

f[0,1]=\frac{1-0}{1-0}=1

继续按差商递推得到二阶差商 $-2,8$ ，三阶差商 $10$ 。

于是 Newton-Hermite 形式为：

H_3(x)=0+3x-2x^2+10x^2(x-1)

化简：

H_3(x)=10x^3-12x^2+3x

检查：

H_3(0)=0, \quad H_3(1)=1

H_3'(x)=30x^2-24x+3

H_3'(0)=3, \quad H_3'(1)=9

完全满足条件。

分段三次 Hermite 插值#

整体 Hermite 插值仍然可能有高次振荡。更常用的做法是在每个小区间上单独做三次 Hermite 插值。

在 $[x_i,x_{i+1}]$ 上已知：

f(x_i),\quad f(x_{i+1}),\quad f'(x_i),\quad f'(x_{i+1})

这四个条件刚好确定一个三次多项式。

令：

h_i=x_{i+1}-x_i, \qquad t=\frac{x-x_i}{h_i}

分段三次 Hermite 插值可写为：

H_i(x)=(1-3t^2+2t^3)y_i+(3t^2-2t^3)y_{i+1} +h_i(t-2t^2+t^3)y_i' +h_i(-t^2+t^3)y_{i+1}'

它在每个节点处满足：

H_i(x_i)=y_i, \quad H_i(x_{i+1})=y_{i+1}

H_i'(x_i)=y_i', \quad H_i'(x_{i+1})=y_{i+1}'

由于相邻区间在公共节点处使用同一个导数值，所以整体函数的一阶导数连续。

分段三次 Hermite 插值的特点：

每段只用两个端点的信息。
曲线比折线光滑。
一阶导数连续。
导数数据不易获得，这是主要限制。

样条插值#

样条函数的直观来源#

样条（spline）最早来自工程制图中的细木条或细金属条。

做法是：

先用钉子固定一些给定点。
再让一根有弹性的细条自然弯曲通过这些点。
两端可以用夹具控制方向，也可以自然放开。

数学上，这对应一条分段多项式曲线：

每段都是低次多项式。
相邻段在节点处接起来。
函数值、一阶导数、二阶导数都连续。

这就是三次样条插值的核心思想。

三次样条插值的定义#

给定区间划分：

a=x_0<x_1<\cdots<x_n=b

已知节点值：

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

三次样条插值函数 $S(x)$ 满足：

过所有节点：

S(x_i)=y_i\qquad (i=0,1,\dots,n)

在每个小区间 $[x_j,x_{j+1}]$ 上， $S(x)$ 是三次多项式，记为 $S_j(x)$ 。
在整个区间 $[a,b]$ 上， $S(x)$ 具有连续二阶导数，即：

S(x)\in C^2[a,b]

这意味着在每个内部节点 $x_j$ 处：

S_{j-1}(x_j)=S_j(x_j)

S_{j-1}'(x_j)=S_j'(x_j)

S_{j-1}''(x_j)=S_j''(x_j)

每一段是三次多项式，有 $4n$ 个待定系数。函数值连续、一阶导连续、二阶导连续提供大部分条件，但最后还差两个条件，所以需要额外给定两个边界条件。

三弯矩方程#

课堂上主要讲的是以二阶导数为未知量的推导，也叫 三弯矩方程。

设：

M_j=S''(x_j),\qquad h_j=x_{j+1}-x_j

在 $[x_j,x_{j+1}]$ 上，三次样条可以写成：

S_j(x)=M_j\frac{(x_{j+1}-x)^3}{6h_j} +M_{j+1}\frac{(x-x_j)^3}{6h_j} +\left(y_j-\frac{M_jh_j^2}{6}\right)\frac{x_{j+1}-x}{h_j} +\left(y_{j+1}-\frac{M_{j+1}h_j^2}{6}\right)\frac{x-x_j}{h_j}

这个式子满足：

S_j(x_j)=y_j, \quad S_j(x_{j+1})=y_{j+1}

S_j''(x_j)=M_j, \quad S_j''(x_{j+1})=M_{j+1}

接下来利用一阶导数在内部节点连续：

S_{j-1}'(x_j)=S_j'(x_j)

可以得到：

\frac{h_{j-1}}{6}M_{j-1}+\frac{h_{j-1}+h_j}{3}M_j+ \frac{h_j}{6}M_{j+1} = \frac{y_{j+1}-y_j}{h_j}-\frac{y_j-y_{j-1}}{h_{j-1}}

对 $j=1,2,\dots,n-1$ 成立。

为了写得更紧凑，令：

\alpha_j=\frac{h_{j-1}}{h_{j-1}+h_j}, \qquad \beta_j=\frac{h_j}{h_{j-1}+h_j}

c_j=\frac{6}{h_{j-1}+h_j} \left( \frac{y_{j+1}-y_j}{h_j}-\frac{y_j-y_{j-1}}{h_{j-1}} \right)

则内部方程写成：

\alpha_jM_{j-1}+2M_j+\beta_jM_{j+1}=c_j \qquad (j=1,2,\dots,n-1)

这是一个三对角结构的线性方程组。未知量是：

M_0,M_1,\dots,M_n

内部节点只给 $n-1$ 个方程，所以还需要两个边界条件。

三类常见边界条件#

第一类边界条件：给端点一阶导数#

给定：

S'(a)=y_0',\qquad S'(b)=y_n'

这相当于用夹具控制细条两端的切线方向。

对应补充方程为：

2M_0+M_1=\frac{6}{h_0}\left(\frac{y_1-y_0}{h_0}-y_0'\right)

M_{n-1}+2M_n=\frac{6}{h_{n-1}}\left(y_n'-\frac{y_n-y_{n-1}}{h_{n-1}}\right)

加入这两个方程后，可以求出所有 $M_j$ 。

第二类边界条件：给端点二阶导数#

给定：

S''(a)=y_0'',\qquad S''(b)=y_n''

也就是：

M_0=y_0'',\qquad M_n=y_n''

特别地，如果：

M_0=0, \qquad M_n=0

称为 自然样条（natural spline）。

自然样条的直观含义是：端点不施加额外弯矩，曲线在两端自然放开。

周期边界条件#

若函数是周期函数，并且：

y_0=y_n

则可以要求样条也周期延拓：

S'(a+0)=S'(b-0)

S''(a+0)=S''(b-0)

这通常用于画封闭曲线。

例如画一个封闭轮廓，可以把曲线参数化为：

x=x(t),\qquad y=y(t)

然后分别对 $x(t)$ 和 $y(t)$ 做周期样条插值。

周期样条的方程组仍然可以求解，但矩阵会在左下角和右上角出现额外非零元素，所以它不再是普通三对角方程组。

三次样条的计算流程#

计算三次样条可以按下面做：

输入节点 $x_i$ 和函数值 $y_i$ 。
计算区间长度：

h_i=x_{i+1}-x_i

根据内部节点方程建立三弯矩方程：

\alpha_jM_{j-1}+2M_j+\beta_jM_{j+1}=c_j

根据题目给出的边界条件补上两个方程。
解线性方程组，得到 $M_0,M_1,\dots,M_n$ 。
把 $M_j$ 代入每段的表达式 $S_j(x)$ 。
最终得到分段定义的样条函数。

TIP
如果是普通三对角方程组，可以用追赶法求解。
如果是周期样条，系数矩阵带有周期耦合项，要用对应的循环三对角求解方法。

本章课堂范围说明#

这三次课主要讲了 Chapter 5 中的以下内容：

插值问题与误差余项
Lagrange 插值
Newton 插值、差商、差分
龙格现象与高次插值的风险
分段线性插值
Hermite 插值与重节点差商方法
分段三次 Hermite 插值
三次样条插值、三弯矩方程、第一类 / 第二类 / 自然 / 周期边界条件

课本中后面关于 快速傅里叶变换（FFT） 的内容，老师课上明确表示不讲。后面提到的曲面样条、AI 辅助写程序、编程方法讨论等，属于课堂延伸或后续内容，本笔记没有纳入 Chapter 5 正文。