CHAPTER 02
第二章 · 插值
只知道函数在几个点上的值,要在中间取值,靠的就是插值。这一章的主线是「怎么构造」和「构造出来可不可靠」,后者往往才是考点。
本页目录
2.1 插值问题
已知函数 f ( x ) f(x) f ( x ) 在 n + 1 n+1 n + 1 个互异节点 x 0 , x 1 , … , x n x_0,x_1,\ldots,x_n x 0 , x 1 , … , x n 上的函数值 f ( x i ) f(x_i) f ( x i ) ,要求一个次数不超过 n n n 的多项式 P n ( x ) P_n(x) P n ( x ) ,满足
称 P n P_n P n 为 f f f 的插值多项式 ,x i x_i x i 为节点,f f f 为被插函数。节点之间的 x x x 称为插值点,x x x 在节点范围之外时称为外推。
存在唯一性 这样的多项式存在且唯一。把条件写成线性方程组,系数矩阵是范德蒙德矩阵,其行列式为
节点互异时行列式非零,方程组有唯一解。
理论上可以直接解这个 n + 1 n+1 n + 1 阶方程组,实际中不这么做:计算量 O ( n 3 ) O(n^3) O ( n 3 ) ,而且范德蒙德矩阵条件数随 n n n 迅速变坏。拉格朗日与牛顿公式都是绕开解方程组的构造方法。
插值多项式唯一,不代表插值公式唯一。拉格朗日形式和牛顿形式是同一个多项式的两种写法,系数不同、计算方式不同,代入同一个
x x x 必须得到同一个值。考试让你「用两种方法验证」,考的就是这一点。
2.2 拉格朗日插值
先构造一组「开关」函数:第 i i i 个基函数在自己的节点上取 1 1 1 ,在其他节点上取 0 0 0 。
把它们按函数值加权求和,就得到拉格朗日插值多项式:
每个基函数是 n n n 次多项式,乘以系数后相加的次数不超过 n n n ;在节点 x k x_k x k 处只有第 k k k 项存活,值正好是 f ( x k ) f(x_k) f ( x k ) 。唯一性保证了它就是要找的那个多项式。
图 2-1 5 个等距节点上的拉格朗日基函数。每条曲线在自己的节点取 1、在其余节点取 0,求和恒等于 1。节点越密,基函数的峰越尖,节点外侧的旁瓣越大。
例 2-1(课件例题) 已知 sin x \sin x sin x 在 1.0 , 1.5 , 2.0 1.0,1.5,2.0 1.0 , 1.5 , 2.0 处的值,用二次拉格朗日插值求 sin 1.2 \sin 1.2 sin 1.2 。
x i x_i x i
1.0 1.0 1.0
1.5 1.5 1.5
2.0 2.0 2.0
sin x i \sin x_i sin x i
0.8415 0.8415 0.8415
0.9975 0.9975 0.9975
0.9093 0.9093 0.9093
三个基函数为
代入 x = 1.2 x=1.2 x = 1.2 :
与真值 sin 1.2 = 0.9320 \sin 1.2=0.9320 sin 1.2 = 0.9320 相比,误差约 1.2 × 10 − 3 1.2\times 10^{-3} 1.2 × 1 0 − 3 。
截断误差
设 f ∈ C n + 1 [ a , b ] f\in C^{n+1}[a,b] f ∈ C n + 1 [ a , b ] ,则插值余项为
其中 ξ \xi ξ 依赖于 x x x ,位于包含 x x x 与所有节点的最小区间内。ξ \xi ξ 未知,所以实际只能估界:
例 2-2(接例 2-1) 估计 L 2 ( 1.2 ) L_2(1.2) L 2 ( 1.2 ) 的截断误差限。
sin x \sin x sin x 的三阶导数绝对值不超过 1 1 1 ,故 M 3 = 1 M_3=1 M 3 = 1 。节点为 1.0 , 1.5 , 2.0 1.0,1.5,2.0 1.0 , 1.5 , 2.0 ,
这个界针对用精确节点值做插值的截断误差。表中节点值四舍五入到四位小数,还会带来至多 0.00005 ( 0.48 + 0.64 + 0.12 ) = 0.000062 0.00005(0.48+0.64+0.12)=0.000062 0.00005 ( 0.48 + 0.64 + 0.12 ) = 0.000062 的误差。若要一起估计,两项相加得 0.008062 0.008062 0.008062 。答题时写「误差限为 0.008 0.008 0.008 」即可,不要把它当成真实误差。
余项公式里的
ω n + 1 ( x ) \omega_{n+1}(x) ω n + 1 ( x ) 只与节点和插值点有关,
f ( n + 1 ) f^{(n+1)} f ( n + 1 ) 才与被插函数有关。求误差限时先算
ω \omega ω ,再乘
M n + 1 / ( n + 1 ) ! M_{n+1}/(n+1)! M n + 1 / ( n + 1 )! ,顺序不要反。如果题目没有给出
M n + 1 M_{n+1} M n + 1 ,就用题目给的函数求导后取最大绝对值。
2.3 牛顿插值
拉格朗日的缺点是:增加一个节点,所有基函数都要重算。牛顿形式把多项式写成「逐项增加」的结构,新增节点只需在末尾加一项。
差商
称
为 f f f 关于 x i , x j x_i,x_j x i , x j 的一阶差商 ,二阶及以上的差商递推定义为
计算时列差商表 :第一列是节点和函数值,之后每一列由左上方两个数相减、再除以对应的节点差得到。
例 2-3(接例 2-1) 对 1.0 , 1.5 , 2.0 1.0,1.5,2.0 1.0 , 1.5 , 2.0 三点作差商表。
x i x_i x i
f ( x i ) f(x_i) f ( x i )
一阶差商
二阶差商
1.0 1.0 1.0
0.8415 0.8415 0.8415
1.5 1.5 1.5
0.9975 0.9975 0.9975
0.3120 0.3120 0.3120
2.0 2.0 2.0
0.9093 0.9093 0.9093
− 0.1764 -0.1764 − 0.1764
− 0.4884 -0.4884 − 0.4884
其中 f [ x 0 , x 1 ] = ( 0.9975 − 0.8415 ) / 0.5 = 0.3120 f[x_0,x_1]=(0.9975-0.8415)/0.5=0.3120 f [ x 0 , x 1 ] = ( 0.9975 − 0.8415 ) /0.5 = 0.3120 ,f [ x 1 , x 2 ] = ( 0.9093 − 0.9975 ) / 0.5 = − 0.1764 f[x_1,x_2]=(0.9093-0.9975)/0.5=-0.1764 f [ x 1 , x 2 ] = ( 0.9093 − 0.9975 ) /0.5 = − 0.1764 ,
差商有三条常用性质:
对称性 :f [ x 0 , x 1 , … , x k ] f[x_0,x_1,\ldots,x_k] f [ x 0 , x 1 , … , x k ] 与节点的排列顺序无关。
与导数的关系 :若 f ∈ C k f\in C^k f ∈ C k ,则存在 ξ \xi ξ 使 f [ x 0 , … , x k ] = f ( k ) ( ξ ) k ! f[x_0,\ldots,x_k]=\dfrac{f^{(k)}(\xi)}{k!} f [ x 0 , … , x k ] = k ! f ( k ) ( ξ ) 。
多项式判据 :若 f f f 是 m m m 次多项式,则 k ≤ m k\le m k ≤ m 时 k k k 阶差商是 m − k m-k m − k 次多项式,k > m k>m k > m 时差商恒为 0 0 0 ;m m m 阶差商等于首项系数。
牛顿公式
展开前几项就是
代入例 2-3 的数据:
N 2 ( 1.2 ) = 0.8415 + 0.0624 + 0.0293 = 0.9332 N_2(1.2)=0.8415+0.0624+0.0293=0.9332 N 2 ( 1.2 ) = 0.8415 + 0.0624 + 0.0293 = 0.9332 ,与拉格朗日结果完全一致。
新增节点 x 3 x_3 x 3 时,只需算出差商表最后一列的新值 f [ x 0 , x 1 , x 2 , x 3 ] f[x_0,x_1,x_2,x_3] f [ x 0 , x 1 , x 2 , x 3 ] ,在公式末尾加一项,前面的项不动。这是牛顿形式在实际计算中更常用的原因。
等距节点与差分
节点等距 x i = x 0 + i h x_i=x_0+ih x i = x 0 + ih 时,差商可以用差分 表示。称
为向前差分,则
令 x = x 0 + t h x=x_0+th x = x 0 + t h ,牛顿向前插值公式为
从节点末端向前推,用向后差分 ∇ f i = f i − f i − 1 \nabla f_i=f_i-f_{i-1} ∇ f i = f i − f i − 1 ,令 x = x n + t h x=x_n+th x = x n + t h :
差分表与差商表结构相同,只是少了除以阶乘和 h k h^k h k 的步骤。等距节点、插值点靠近表头时用向前公式,靠近表尾时用向后公式。
2.4 埃尔米特插值
如果不仅知道函数值,还知道导数值,就能构造同时匹配函数值和导数的插值多项式。给 n + 1 n+1 n + 1 个节点上的函数值与一阶导数,共 2 n + 2 2n+2 2 n + 2 个条件,可唯一确定一个次数不超过 2 n + 1 2n+1 2 n + 1 的多项式 H 2 n + 1 ( x ) H_{2n+1}(x) H 2 n + 1 ( x ) 。
基函数形式为
其中 l i l_i l i 是拉格朗日基函数,l i ′ ( x i ) = ∑ j ≠ i 1 x i − x j l_i'(x_i)=\sum_{j\ne i}\dfrac{1}{x_i-x_j} l i ′ ( x i ) = ∑ j = i x i − x j 1 。α i \alpha_i α i 负责函数值,β i \beta_i β i 负责导数,两者在自己的节点上分别取 1 1 1 和 0 0 0 。
余项为
注意 ω \omega ω 是平方,这正是导数条件带来的额外精度。
例 2-4(补充) 已知 f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 ,f ′ ( 0 ) = 1 f'(0)=1 f ′ ( 0 ) = 1 ,f ( 1 ) = 1 f(1)=1 f ( 1 ) = 1 ,f ′ ( 1 ) = 3 f'(1)=3 f ′ ( 1 ) = 3 ,求三次埃尔米特插值多项式。
用重节点差商法,把每个节点写两次,导数放在一阶差商的斜线上:
z i z_i z i
f ( z i ) f(z_i) f ( z i )
一阶差商
二阶差商
三阶差商
0 0 0
0 0 0
0 0 0
0 0 0
1 1 1
1 1 1
1 1 1
1 1 1
0 0 0
1 1 1
1 1 1
3 3 3
2 2 2
2 2 2
按牛顿公式读出系数 0 , 1 , 0 , 2 0,1,0,2 0 , 1 , 0 , 2 :
验证:H 3 ( 0 ) = 0 H_3(0)=0 H 3 ( 0 ) = 0 ,H 3 ( 1 ) = 1 H_3(1)=1 H 3 ( 1 ) = 1 ,H 3 ′ ( x ) = 1 − 4 x + 6 x 2 H_3'(x)=1-4x+6x^2 H 3 ′ ( x ) = 1 − 4 x + 6 x 2 ,故 H 3 ′ ( 0 ) = 1 H_3'(0)=1 H 3 ′ ( 0 ) = 1 ,H 3 ′ ( 1 ) = 3 H_3'(1)=3 H 3 ′ ( 1 ) = 3 ,四个条件全部满足。
重节点差商表的规则:节点写两遍,重复节点之间的一阶差商填导数值,其余格子照常做差商。这样不必背
α i , β i \alpha_i,\beta_i α i , β i 的公式也能写出多项式,考场上更快。
2.5 分段插值与龙格现象
提高插值次数并不一定提高精度。最著名的反例是龙格函数
在等距节点上做高次插值,节点越密,端点附近的振荡反而越剧烈,这种现象称为龙格现象 。
图 2-2 龙格现象。n = 10 , 15 n=10,15 n = 10 , 15 时端点已出现明显上冲;n = 20 n=20 n = 20 时振荡幅度达到数十,超出纵轴范围的部分没有显示。加密节点不能让插值多项式收敛到 f f f 。
原因是高次插值的余项中含 f ( n + 1 ) ( ξ ) f^{(n+1)}(\xi) f ( n + 1 ) ( ξ ) 与 ω n + 1 ( x ) \omega_{n+1}(x) ω n + 1 ( x ) 。节点加密时 ω \omega ω 在端点附近不一定变小,而高阶导数可能增长得很快,两者相乘导致误差不收敛。此外,高次插值的基函数在端点附近绝对值很大,舍入误差也被放大,数值上不稳定。
实践中的做法是降低次数、分段插值 :
没有普适的安全次数上限,要看函数和节点;
节点多时用分段低次插值,或三次样条;
需要统一公式时用牛顿形式,便于逐点增加节点。
分段线性插值 在每个子区间 [ x i − 1 , x i ] [x_{i-1},x_i] [ x i − 1 , x i ] 上用直线连接两个端点:
它只保证连续(C 0 C^0 C 0 ),节点处导数一般不连续,但收敛性有保证。设 h = max ( x i − x i − 1 ) h=\max(x_i-x_{i-1}) h = max ( x i − x i − 1 ) ,则
误差随 h h h 平方下降,稳定、简单,缺点是曲线在节点处有折角。
2.6 三次样条插值
分段线性不够光滑。工程上更常用三次样条:既保留分段低次的稳定性,又让曲线在节点处光滑过渡。
定义 给定节点 a = x 0 < x 1 < ⋯ < x n = b a=x_0<x_1<\cdots<x_n=b a = x 0 < x 1 < ⋯ < x n = b 和函数值 f i f_i f i ,若 S ( x ) S(x) S ( x ) 满足
S ( x ) S(x) S ( x ) 在 [ a , b ] [a,b] [ a , b ] 上二阶连续可导,即 S ∈ C 2 [ a , b ] S\in C^2[a,b] S ∈ C 2 [ a , b ] ;
在每个子区间 [ x i − 1 , x i ] [x_{i-1},x_i] [ x i − 1 , x i ] 上 S ( x ) S(x) S ( x ) 是三次多项式;
S ( x i ) = f i S(x_i)=f_i S ( x i ) = f i ,i = 0 , 1 , … , n i=0,1,\ldots,n i = 0 , 1 , … , n ,
则称 S ( x ) S(x) S ( x ) 为三次样条插值函数。
有 n n n 个子区间,每段 4 4 4 个系数,共 4 n 4n 4 n 个未知量。每段两端的插值条件共 2 n 2n 2 n 个,内节点处 S ′ , S ′ ′ S',S'' S ′ , S ′′ 连续各提供 n − 1 n-1 n − 1 个条件,共 4 n − 2 4n-2 4 n − 2 个方程,还差 2 2 2 个,需要补充边界条件 :
类型
条件
适用
弯矩边界
S ′ ′ ( x 0 ) = M 0 S''(x_0)=M_0 S ′′ ( x 0 ) = M 0 ,S ′ ′ ( x n ) = M n S''(x_n)=M_n S ′′ ( x n ) = M n
已知端部弯矩;取 M 0 = M n = 0 M_0=M_n=0 M 0 = M n = 0 称为自然边界
转角边界
S ′ ( x 0 ) = m 0 S'(x_0)=m_0 S ′ ( x 0 ) = m 0 ,S ′ ( x n ) = m n S'(x_n)=m_n S ′ ( x n ) = m n
已知端部斜率
周期边界
S ′ ( x 0 + ) = S ′ ( x n − ) S'(x_0^+)=S'(x_n^-) S ′ ( x 0 + ) = S ′ ( x n − ) ,S ′ ′ ( x 0 + ) = S ′ ′ ( x n − ) S''(x_0^+)=S''(x_n^-) S ′′ ( x 0 + ) = S ′′ ( x n − )
端点函数值相同(f 0 = f n f_0=f_n f 0 = f n )
三弯矩法
记 M i = S ′ ′ ( x i ) M_i=S''(x_i) M i = S ′′ ( x i ) ,h i = x i − x i − 1 h_i=x_i-x_{i-1} h i = x i − x i − 1 。利用一阶导数在节点处连续,可导出内节点方程
这是 n − 1 n-1 n − 1 个方程、n + 1 n+1 n + 1 个未知量 M 0 , … , M n M_0,\ldots,M_n M 0 , … , M n ,加上两个边界条件正好封闭。弯矩边界和转角边界得到三对角方程组,可用追赶法在 O ( n ) O(n) O ( n ) 时间内求解。周期边界会把首尾未知量连起来,通常得到循环三对角方程组,不能直接用普通追赶法。
自然边界 M 0 = M n = 0 M_0=M_n=0 M 0 = M n = 0 时,方程组只剩 M 1 , … , M n − 1 M_1,\ldots,M_{n-1} M 1 , … , M n − 1 。解出弯矩后,每个子区间上的表达式为
图 2-3 同一组节点上的分段线性与三次样条。分段线性在节点处只连续,样条的一、二阶导数都连续,曲线没有折角;代价是要解一个三对角方程组。
三次样条的光滑性是**整体**
C 2 C^2 C 2 ,不是每段单独光滑。答题时三个条件要写全:二阶连续可导、每段三次、过节点值。只写「分段三次多项式」不构成样条定义。
2.7 本章小结
方法
光滑性
余项或误差
适用与代价
拉格朗日
C ∞ C^\infty C ∞
f ( n + 1 ) ( ξ ) ( n + 1 ) ! ω n + 1 ( x ) \dfrac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x) ( n + 1 )! f ( n + 1 ) ( ξ ) ω n + 1 ( x )
公式对称,节点增多需全部重算
牛顿
C ∞ C^\infty C ∞
同上
增加节点只加一项,适合逐步加密
埃尔米特
C ∞ C^\infty C ∞
f ( 2 n + 2 ) ( ξ ) ( 2 n + 2 ) ! ω n + 1 2 ( x ) \dfrac{f^{(2n+2)}(\xi)}{(2n+2)!}\omega_{n+1}^2(x) ( 2 n + 2 )! f ( 2 n + 2 ) ( ξ ) ω n + 1 2 ( x )
需要导数,能同时匹配函数值和导数
分段线性
C 0 C^0 C 0
≤ h 2 8 max ∣ f ′ ′ ∣ \le \dfrac{h^2}{8}\max\lvert f''\rvert ≤ 8 h 2 max ∣ f ′′ ∣
稳定、简单,节点处有折角
三次样条
C 2 C^2 C 2
O ( h 4 ) O(h^4) O ( h 4 ) (内点)
光滑,方程组的结构取决于边界条件
这一章的题基本落在五种问法上:
① 给节点表,求拉格朗日或牛顿插值多项式并算某点的值——两种方法结果必须一致,可用差商表省计算;
② 估计截断误差限——先算
∣ ω n + 1 ∣ \lvert\omega_{n+1}\rvert ∣ ω n + 1 ∣ ,再乘
M n + 1 / ( n + 1 ) ! M_{n+1}/(n+1)! M n + 1 / ( n + 1 )! ;
③ 差商或差分填空——注意对称性和
f [ x 0 , … , x k ] = Δ k f 0 / ( k ! h k ) f[x_0,\ldots,x_k]=\Delta^kf_0/(k!h^k) f [ x 0 , … , x k ] = Δ k f 0 / ( k ! h k ) ;
④ 带导数的插值——用重节点差商表最快,注意次数是
2 n + 1 2n+1 2 n + 1 ;
⑤ 样条——写定义、判断边界条件类型、列三弯矩方程组,通常不要求手算整个方程组。
两章之间的联系:插值余项里的
ω n + 1 ( x ) \omega_{n+1}(x) ω n + 1 ( x ) 与误差限,和第一章的有效数字是同一套语言。考试若问「要提高精度」,答案不是无限加密节点,而是选对方法(分段、样条、埃尔米特)并控制舍入误差。