留痕数值分析

CHAPTER 02

第二章 · 插值

只知道函数在几个点上的值,要在中间取值,靠的就是插值。这一章的主线是「怎么构造」和「构造出来可不可靠」,后者往往才是考点。

本页目录

2.1 插值问题

已知函数 f(x)f(x) 在 n+1n+1 个互异节点 x0,x1,…,xnx_0,x_1,\ldots,x_n 上的函数值 f(xi)f(x_i),要求一个次数不超过 nn 的多项式 Pn(x)P_n(x),满足

Pn(xi)=f(xi),i=0,1,…,nP_n(x_i)=f(x_i),\qquad i=0,1,\ldots,n

称 PnP_n 为 ff 的插值多项式,xix_i 为节点,ff 为被插函数。节点之间的 xx 称为插值点,xx 在节点范围之外时称为外推。

存在唯一性 这样的多项式存在且唯一。把条件写成线性方程组,系数矩阵是范德蒙德矩阵,其行列式为

∏0≤j<i≤n(xi−xj)\prod_{0\le j<i\le n}(x_i-x_j)

节点互异时行列式非零,方程组有唯一解。

理论上可以直接解这个 n+1n+1 阶方程组,实际中不这么做:计算量 O(n3)O(n^3),而且范德蒙德矩阵条件数随 nn 迅速变坏。拉格朗日与牛顿公式都是绕开解方程组的构造方法。

插值多项式唯一,不代表插值公式唯一。拉格朗日形式和牛顿形式是同一个多项式的两种写法,系数不同、计算方式不同,代入同一个 xx 必须得到同一个值。考试让你「用两种方法验证」,考的就是这一点。

2.2 拉格朗日插值

先构造一组「开关」函数:第 ii 个基函数在自己的节点上取 11,在其他节点上取 00。

li(x)=∏j=0j≠inx−xjxi−xj,li(xj)=δij={1,i=j0,i≠jl_i(x)=\prod_{\substack{j=0\\ j\ne i}}^{n}\frac{x-x_j}{x_i-x_j},\qquad l_i(x_j)=\delta_{ij}=\begin{cases}1,& i=j\\ 0,& i\ne j\end{cases}

把它们按函数值加权求和,就得到拉格朗日插值多项式:

Ln(x)=∑i=0nf(xi) li(x)L_n(x)=\sum_{i=0}^{n}f(x_i)\,l_i(x)

每个基函数是 nn 次多项式,乘以系数后相加的次数不超过 nn;在节点 xkx_k 处只有第 kk 项存活,值正好是 f(xk)f(x_k)。唯一性保证了它就是要找的那个多项式。

图 2-1 5 个等距节点上的拉格朗日基函数。每条曲线在自己的节点取 1、在其余节点取 0,求和恒等于 1。节点越密,基函数的峰越尖,节点外侧的旁瓣越大。

例 2-1(课件例题) 已知 sin⁡x\sin x 在 1.0,1.5,2.01.0,1.5,2.0 处的值,用二次拉格朗日插值求 sin⁡1.2\sin 1.2。

xix_i 1.01.0 1.51.5 2.02.0
sin⁡xi\sin x_i 0.84150.8415 0.99750.9975 0.90930.9093

三个基函数为

l0(x)=(x−1.5)(x−2.0)(1.0−1.5)(1.0−2.0),l1(x)=(x−1.0)(x−2.0)(1.5−1.0)(1.5−2.0),l2(x)=(x−1.0)(x−1.5)(2.0−1.0)(2.0−1.5)l_0(x)=\frac{(x-1.5)(x-2.0)}{(1.0-1.5)(1.0-2.0)},\quad l_1(x)=\frac{(x-1.0)(x-2.0)}{(1.5-1.0)(1.5-2.0)},\quad l_2(x)=\frac{(x-1.0)(x-1.5)}{(2.0-1.0)(2.0-1.5)}

代入 x=1.2x=1.2:

l0(1.2)=(−0.3)(−0.8)0.5=0.48,l1(1.2)=(0.2)(−0.8)−0.25=0.64,l2(1.2)=(0.2)(−0.3)0.5=−0.12l_0(1.2)=\frac{(-0.3)(-0.8)}{0.5}=0.48,\quad l_1(1.2)=\frac{(0.2)(-0.8)}{-0.25}=0.64,\quad l_2(1.2)=\frac{(0.2)(-0.3)}{0.5}=-0.12
L2(1.2)=0.8415×0.48+0.9975×0.64+0.9093×(−0.12)=0.9332L_2(1.2)=0.8415\times 0.48+0.9975\times 0.64+0.9093\times(-0.12)=0.9332

与真值 sin⁡1.2=0.9320\sin 1.2=0.9320 相比,误差约 1.2×10−31.2\times 10^{-3}。

截断误差

设 f∈Cn+1[a,b]f\in C^{n+1}[a,b],则插值余项为

Rn(x)=f(x)−Ln(x)=f(n+1)(ξ)(n+1)! ωn+1(x),ωn+1(x)=∏i=0n(x−xi)R_n(x)=f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega_{n+1}(x),\qquad \omega_{n+1}(x)=\prod_{i=0}^{n}(x-x_i)

其中 ξ\xi 依赖于 xx,位于包含 xx 与所有节点的最小区间内。ξ\xi 未知,所以实际只能估界:

∣Rn(x)∣≤Mn+1(n+1)!∣ωn+1(x)∣,Mn+1=max⁡[a,b]∣f(n+1)∣\lvert R_n(x)\rvert\le \frac{M_{n+1}}{(n+1)!}\lvert\omega_{n+1}(x)\rvert,\qquad M_{n+1}=\max_{[a,b]}\lvert f^{(n+1)}\rvert

例 2-2(接例 2-1) 估计 L2(1.2)L_2(1.2) 的截断误差限。

sin⁡x\sin x 的三阶导数绝对值不超过 11,故 M3=1M_3=1。节点为 1.0,1.5,2.01.0,1.5,2.0,

∣ω3(1.2)∣=∣(0.2)(−0.3)(−0.8)∣=0.048\lvert\omega_3(1.2)\rvert=\lvert(0.2)(-0.3)(-0.8)\rvert=0.048
∣R2(1.2)∣≤13!×0.048=0.008\lvert R_2(1.2)\rvert\le \frac{1}{3!}\times 0.048=0.008

这个界针对用精确节点值做插值的截断误差。表中节点值四舍五入到四位小数,还会带来至多 0.00005(0.48+0.64+0.12)=0.0000620.00005(0.48+0.64+0.12)=0.000062 的误差。若要一起估计,两项相加得 0.0080620.008062。答题时写「误差限为 0.0080.008」即可,不要把它当成真实误差。

余项公式里的 ωn+1(x)\omega_{n+1}(x) 只与节点和插值点有关,f(n+1)f^{(n+1)} 才与被插函数有关。求误差限时先算 ω\omega,再乘 Mn+1/(n+1)!M_{n+1}/(n+1)!,顺序不要反。如果题目没有给出 Mn+1M_{n+1},就用题目给的函数求导后取最大绝对值。

2.3 牛顿插值

拉格朗日的缺点是:增加一个节点,所有基函数都要重算。牛顿形式把多项式写成「逐项增加」的结构,新增节点只需在末尾加一项。

差商

称

f[xi,xj]=f(xj)−f(xi)xj−xif[x_i,x_j]=\frac{f(x_j)-f(x_i)}{x_j-x_i}

为 ff 关于 xi,xjx_i,x_j 的一阶差商,二阶及以上的差商递推定义为

f[x0,x1,…,xk]=f[x1,…,xk]−f[x0,…,xk−1]xk−x0f[x_0,x_1,\ldots,x_k]=\frac{f[x_1,\ldots,x_k]-f[x_0,\ldots,x_{k-1}]}{x_k-x_0}

计算时列差商表:第一列是节点和函数值,之后每一列由左上方两个数相减、再除以对应的节点差得到。

例 2-3(接例 2-1) 对 1.0,1.5,2.01.0,1.5,2.0 三点作差商表。

xix_i f(xi)f(x_i) 一阶差商 二阶差商
1.01.0 0.84150.8415
1.51.5 0.99750.9975 0.31200.3120
2.02.0 0.90930.9093 −0.1764-0.1764 −0.4884-0.4884

其中 f[x0,x1]=(0.9975−0.8415)/0.5=0.3120f[x_0,x_1]=(0.9975-0.8415)/0.5=0.3120,f[x1,x2]=(0.9093−0.9975)/0.5=−0.1764f[x_1,x_2]=(0.9093-0.9975)/0.5=-0.1764,

f[x0,x1,x2]=−0.1764−0.31202.0−1.0=−0.4884f[x_0,x_1,x_2]=\frac{-0.1764-0.3120}{2.0-1.0}=-0.4884

差商有三条常用性质:

  1. 对称性:f[x0,x1,…,xk]f[x_0,x_1,\ldots,x_k] 与节点的排列顺序无关。
  2. 与导数的关系:若 f∈Ckf\in C^k,则存在 ξ\xi 使 f[x0,…,xk]=f(k)(ξ)k!f[x_0,\ldots,x_k]=\dfrac{f^{(k)}(\xi)}{k!}。
  3. 多项式判据:若 ff 是 mm 次多项式,则 k≤mk\le m 时 kk 阶差商是 m−km-k 次多项式,k>mk>m 时差商恒为 00;mm 阶差商等于首项系数。

牛顿公式

Nn(x)=f(x0)+∑k=1nf[x0,x1,…,xk]∏i=0k−1(x−xi)N_n(x)=f(x_0)+\sum_{k=1}^{n}f[x_0,x_1,\ldots,x_k]\prod_{i=0}^{k-1}(x-x_i)

展开前几项就是

Nn(x)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)+⋯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

代入例 2-3 的数据:

N2(x)=0.8415+0.3120(x−1.0)−0.4884(x−1.0)(x−1.5)N_2(x)=0.8415+0.3120(x-1.0)-0.4884(x-1.0)(x-1.5)

N2(1.2)=0.8415+0.0624+0.0293=0.9332N_2(1.2)=0.8415+0.0624+0.0293=0.9332,与拉格朗日结果完全一致。

新增节点 x3x_3 时,只需算出差商表最后一列的新值 f[x0,x1,x2,x3]f[x_0,x_1,x_2,x_3],在公式末尾加一项,前面的项不动。这是牛顿形式在实际计算中更常用的原因。

等距节点与差分

节点等距 xi=x0+ihx_i=x_0+ih 时,差商可以用差分表示。称

Δfi=fi+1−fi,Δkfi=Δk−1fi+1−Δk−1fi\Delta f_i=f_{i+1}-f_i,\qquad \Delta^k f_i=\Delta^{k-1}f_{i+1}-\Delta^{k-1}f_i

为向前差分,则

f[x0,x1,…,xk]=Δkf0k! hkf[x_0,x_1,\ldots,x_k]=\frac{\Delta^k f_0}{k!\,h^k}

令 x=x0+thx=x_0+th,牛顿向前插值公式为

Nn(x0+th)=∑k=0n(tk)Δkf0=f0+tΔf0+t(t−1)2!Δ2f0+⋯N_n(x_0+th)=\sum_{k=0}^{n}\binom{t}{k}\Delta^k f_0 =f_0+t\Delta f_0+\frac{t(t-1)}{2!}\Delta^2f_0+\cdots

从节点末端向前推,用向后差分 ∇fi=fi−fi−1\nabla f_i=f_i-f_{i-1},令 x=xn+thx=x_n+th:

Nn(xn+th)=∑k=0n(t+k−1k)∇kfn=fn+t∇fn+t(t+1)2!∇2fn+⋯N_n(x_n+th)=\sum_{k=0}^{n}\binom{t+k-1}{k}\nabla^k f_n =f_n+t\nabla f_n+\frac{t(t+1)}{2!}\nabla^2f_n+\cdots

差分表与差商表结构相同,只是少了除以阶乘和 hkh^k 的步骤。等距节点、插值点靠近表头时用向前公式,靠近表尾时用向后公式。

2.4 埃尔米特插值

如果不仅知道函数值,还知道导数值,就能构造同时匹配函数值和导数的插值多项式。给 n+1n+1 个节点上的函数值与一阶导数,共 2n+22n+2 个条件,可唯一确定一个次数不超过 2n+12n+1 的多项式 H2n+1(x)H_{2n+1}(x)。

基函数形式为

H2n+1(x)=∑i=0n[f(xi)αi(x)+f′(xi)βi(x)]H_{2n+1}(x)=\sum_{i=0}^{n}\left[f(x_i)\alpha_i(x)+f'(x_i)\beta_i(x)\right]
αi(x)=[1−2li′(xi)(x−xi)]li2(x),βi(x)=(x−xi)li2(x)\alpha_i(x)=\left[1-2l_i'(x_i)(x-x_i)\right]l_i^2(x),\qquad \beta_i(x)=(x-x_i)l_i^2(x)

其中 lil_i 是拉格朗日基函数,li′(xi)=∑j≠i1xi−xjl_i'(x_i)=\sum_{j\ne i}\dfrac{1}{x_i-x_j}。αi\alpha_i 负责函数值,βi\beta_i 负责导数,两者在自己的节点上分别取 11 和 00。

余项为

R2n+1(x)=f(2n+2)(ξ)(2n+2)! ωn+12(x)R_{2n+1}(x)=\frac{f^{(2n+2)}(\xi)}{(2n+2)!}\,\omega_{n+1}^2(x)

注意 ω\omega 是平方,这正是导数条件带来的额外精度。

例 2-4(补充) 已知 f(0)=0f(0)=0,f′(0)=1f'(0)=1,f(1)=1f(1)=1,f′(1)=3f'(1)=3,求三次埃尔米特插值多项式。

用重节点差商法,把每个节点写两次,导数放在一阶差商的斜线上:

ziz_i f(zi)f(z_i) 一阶差商 二阶差商 三阶差商
00 00
00 00 11
11 11 11 00
11 11 33 22 22

按牛顿公式读出系数 0,1,0,20,1,0,2:

H3(x)=0+1(x−0)+0(x−0)2+2(x−0)2(x−1)=x+2x3−2x2H_3(x)=0+1(x-0)+0(x-0)^2+2(x-0)^2(x-1)=x+2x^3-2x^2

验证:H3(0)=0H_3(0)=0,H3(1)=1H_3(1)=1,H3′(x)=1−4x+6x2H_3'(x)=1-4x+6x^2,故 H3′(0)=1H_3'(0)=1,H3′(1)=3H_3'(1)=3,四个条件全部满足。

重节点差商表的规则:节点写两遍,重复节点之间的一阶差商填导数值,其余格子照常做差商。这样不必背 αi,βi\alpha_i,\beta_i 的公式也能写出多项式,考场上更快。

2.5 分段插值与龙格现象

提高插值次数并不一定提高精度。最著名的反例是龙格函数

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

在等距节点上做高次插值,节点越密,端点附近的振荡反而越剧烈,这种现象称为龙格现象。

图 2-2 龙格现象。n=10,15n=10,15 时端点已出现明显上冲;n=20n=20 时振荡幅度达到数十,超出纵轴范围的部分没有显示。加密节点不能让插值多项式收敛到 ff。

原因是高次插值的余项中含 f(n+1)(ξ)f^{(n+1)}(\xi) 与 ωn+1(x)\omega_{n+1}(x)。节点加密时 ω\omega 在端点附近不一定变小,而高阶导数可能增长得很快,两者相乘导致误差不收敛。此外,高次插值的基函数在端点附近绝对值很大,舍入误差也被放大,数值上不稳定。

实践中的做法是降低次数、分段插值:

分段线性插值 在每个子区间 [xi−1,xi][x_{i-1},x_i] 上用直线连接两个端点:

Lh(x)=x−xixi−1−xif(xi−1)+x−xi−1xi−xi−1f(xi)L_h(x)=\frac{x-x_i}{x_{i-1}-x_i}f(x_{i-1})+\frac{x-x_{i-1}}{x_i-x_{i-1}}f(x_i)

它只保证连续(C0C^0),节点处导数一般不连续,但收敛性有保证。设 h=max⁡(xi−xi−1)h=\max(x_i-x_{i-1}),则

∣f(x)−Lh(x)∣≤h28max⁡[a,b]∣f′′(x)∣=O(h2)\lvert f(x)-L_h(x)\rvert\le \frac{h^2}{8}\max_{[a,b]}\lvert f''(x)\rvert=O(h^2)

误差随 hh 平方下降,稳定、简单,缺点是曲线在节点处有折角。

2.6 三次样条插值

分段线性不够光滑。工程上更常用三次样条:既保留分段低次的稳定性,又让曲线在节点处光滑过渡。

定义 给定节点 a=x0<x1<⋯<xn=ba=x_0<x_1<\cdots<x_n=b 和函数值 fif_i,若 S(x)S(x) 满足

  1. S(x)S(x) 在 [a,b][a,b] 上二阶连续可导,即 S∈C2[a,b]S\in C^2[a,b];
  2. 在每个子区间 [xi−1,xi][x_{i-1},x_i] 上 S(x)S(x) 是三次多项式;
  3. S(xi)=fiS(x_i)=f_i,i=0,1,…,ni=0,1,\ldots,n,

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

有 nn 个子区间,每段 44 个系数,共 4n4n 个未知量。每段两端的插值条件共 2n2n 个,内节点处 S′,S′′S',S'' 连续各提供 n−1n-1 个条件,共 4n−24n-2 个方程,还差 22 个,需要补充边界条件:

类型 条件 适用
弯矩边界 S′′(x0)=M0S''(x_0)=M_0,S′′(xn)=MnS''(x_n)=M_n 已知端部弯矩;取 M0=Mn=0M_0=M_n=0 称为自然边界
转角边界 S′(x0)=m0S'(x_0)=m_0,S′(xn)=mnS'(x_n)=m_n 已知端部斜率
周期边界 S′(x0+)=S′(xn−)S'(x_0^+)=S'(x_n^-),S′′(x0+)=S′′(xn−)S''(x_0^+)=S''(x_n^-) 端点函数值相同(f0=fnf_0=f_n)

三弯矩法

记 Mi=S′′(xi)M_i=S''(x_i),hi=xi−xi−1h_i=x_i-x_{i-1}。利用一阶导数在节点处连续,可导出内节点方程

μiMi−1+2Mi+λiMi+1=di,i=1,2,…,n−1\mu_iM_{i-1}+2M_i+\lambda_iM_{i+1}=d_i,\qquad i=1,2,\ldots,n-1
μi=hihi+hi+1,λi=1−μi,di=6f[xi−1,xi,xi+1]\mu_i=\frac{h_i}{h_i+h_{i+1}},\qquad \lambda_i=1-\mu_i,\qquad d_i=6f[x_{i-1},x_i,x_{i+1}]

这是 n−1n-1 个方程、n+1n+1 个未知量 M0,…,MnM_0,\ldots,M_n,加上两个边界条件正好封闭。弯矩边界和转角边界得到三对角方程组,可用追赶法在 O(n)O(n) 时间内求解。周期边界会把首尾未知量连起来,通常得到循环三对角方程组,不能直接用普通追赶法。

自然边界 M0=Mn=0M_0=M_n=0 时,方程组只剩 M1,…,Mn−1M_1,\ldots,M_{n-1}。解出弯矩后,每个子区间上的表达式为

S(x)=Mi−1(xi−x)36hi+Mi(x−xi−1)36hi+(fi−1−Mi−1hi26)xi−xhi+(fi−Mihi26)x−xi−1hiS(x)=\frac{M_{i-1}(x_i-x)^3}{6h_i}+\frac{M_i(x-x_{i-1})^3}{6h_i} +\left(f_{i-1}-\frac{M_{i-1}h_i^2}{6}\right)\frac{x_i-x}{h_i} +\left(f_i-\frac{M_ih_i^2}{6}\right)\frac{x-x_{i-1}}{h_i}
图 2-3 同一组节点上的分段线性与三次样条。分段线性在节点处只连续,样条的一、二阶导数都连续,曲线没有折角;代价是要解一个三对角方程组。
三次样条的光滑性是**整体** C2C^2,不是每段单独光滑。答题时三个条件要写全:二阶连续可导、每段三次、过节点值。只写「分段三次多项式」不构成样条定义。

2.7 本章小结

方法 光滑性 余项或误差 适用与代价
拉格朗日 C∞C^\infty f(n+1)(ξ)(n+1)!ωn+1(x)\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x) 公式对称,节点增多需全部重算
牛顿 C∞C^\infty 同上 增加节点只加一项,适合逐步加密
埃尔米特 C∞C^\infty f(2n+2)(ξ)(2n+2)!ωn+12(x)\dfrac{f^{(2n+2)}(\xi)}{(2n+2)!}\omega_{n+1}^2(x) 需要导数,能同时匹配函数值和导数
分段线性 C0C^0 ≤h28max⁡∣f′′∣\le \dfrac{h^2}{8}\max\lvert f''\rvert 稳定、简单,节点处有折角
三次样条 C2C^2 O(h4)O(h^4)(内点) 光滑,方程组的结构取决于边界条件
这一章的题基本落在五种问法上: ① 给节点表,求拉格朗日或牛顿插值多项式并算某点的值——两种方法结果必须一致,可用差商表省计算; ② 估计截断误差限——先算 ∣ωn+1∣\lvert\omega_{n+1}\rvert,再乘 Mn+1/(n+1)!M_{n+1}/(n+1)!; ③ 差商或差分填空——注意对称性和 f[x0,…,xk]=Δkf0/(k!hk)f[x_0,\ldots,x_k]=\Delta^kf_0/(k!h^k); ④ 带导数的插值——用重节点差商表最快,注意次数是 2n+12n+1; ⑤ 样条——写定义、判断边界条件类型、列三弯矩方程组,通常不要求手算整个方程组。
两章之间的联系:插值余项里的 ωn+1(x)\omega_{n+1}(x) 与误差限,和第一章的有效数字是同一套语言。考试若问「要提高精度」,答案不是无限加密节点,而是选对方法(分段、样条、埃尔米特)并控制舍入误差。