动机
函数值告诉我们曲线经过哪里;导数还告诉我们它怎样经过该点。若轨迹必须以指定速度到达,只匹配位置便不足够。Hermite 插值把导数条件视为真正数据。计算所需次数时必须把它们包括在内;重复节点代表额外导数信息,并非把同一条方程再抄一次。
面对长长的数值表,另有一个设计问题:不必让一个多项式在整段区间上不断增加次数,而可在小区间使用三次多项式,再平滑连接。接点把相邻片段联系起来,所以不能完全独立选取每段。自然三次样条借把两端二阶导数设为零,消除余下自由度。我们会推导其三对角系统,并证明所得曲线在全部二次连续可微插值函数中,最小化二阶导数平方的积分。
先前相异节点插值单元是预备知识。
定义
令 t0<⋯<ts 为相异实节点。在 ti 指定导数 di,j,阶数为 0≤j<μi,其中重数 μi≥1 为整数。记
N=i=0∑sμi,ω(x)=i=0∏s(x−ti)μi.Hermite 插值多项式的次数至多为 N−1,满足 p(j)(ti)=di,j。每个节点的条件包括由零阶至 μi−1 阶的全部导数;若跳过中间阶数,便属另一类需要重新分析存在性的条件。数据可以是任意实数;只有要求近似余项时,才需要背后有一个光滑函数。
重复节点差商记号以导数记录数据:
f[k+1 个t,…,t]=k!f(k)(t).
此记号并不要求除以零节点距离;导数值是给定数据。对多项式而言,此值也是在 t 的 Taylor 系数,不能直接把相异节点公式套入零分母。
样条构造使用有序节点 a=x0<⋯<xn=b,整数 n≥1,以及值 y0,…,yn。定义区间长度及割线斜率
hi=xi+1−xi>0,δi=hiyi+1−yi,0≤i<n.三次样条 S 属于 C2([a,b]),在每个 [xi,xi+1] 上都是次数至多三的多项式。若 S(xi)=yi,它便插值数据;若 S′′(a)=S′′(b)=0,则称为自然样条。自然条件不代表端点斜率为零。记 Mi=S′′(xi),并定义弯曲泛函
J(g)=∫ab[g′′(x)]2dx,g∈C2([a,b]).
这在指定坐标下惩罚二阶导数,并不是几何曲率按弧长的积分。我们会在明确指定的 C2 类中最小化它,不暗中使用弱导数或 Sobolev 空间定理。
定理/命题
定理 5.2.3
(Hermite 插值的存在、唯一性及重数余项)
这 N 个 Hermite 条件恰好决定一个次数至多 N−1 的多项式。再假设 di,j=f(j)(ti)、f∈CN([A,B]),其中闭区间包含全部节点及求值点 x。若 x 不是节点,则在全部节点与 x 所张成的区间内,存在 ξ 使
f(x)−p(x)=N!f(N)(ξ)ω(x).在节点处误差为零。特别地,若 ∣f(N)∣≤KN,则 ∣f(x)−p(x)∣≤KN∣ω(x)∣/N!。单靠有限数据表不能认证这个导数界。
对每个严格递增、n≥1 的节点列及任意实数数据,恰有一个自然三次插值样条。其二阶导数满足 M0=Mn=0,且
hi−1Mi−1+2(hi−1+hi)Mi+hiMi+1=6(δi−δi−1),1≤i<n.内部系统非奇异。对每个满足 g(xi)=yi 的 g∈C2([a,b]),即使 g 不满足自然端点条件,亦有
J(g)=J(S)+J(g−S)≥J(S).等号成立当且仅当 g=S。所以样条是整个 C2 插值函数类中的唯一极小者,而非只在分段三次多项式中最佳。
概念视角结构
选择余下自由度的三种不同方法
Hermite 插值用给定导数固定一个多项式。三次样条连接条件联系相邻片段,边界条件再固定余下全局自由度。最小弯曲定理则解释,在只给定函数值时,为何自然边界选择有特殊变分地位。此解释不会提供缺失的物理斜率,也不承诺保形或完整的样条误差理论。
证明思路或证明
把导数条件计作带重数的零点
若多项式 q 满足 q(j)(ti)=0、0≤j<μi,则 (x−ti)μi 整除 q;这由在 ti 展开有限 Taylor 多项式可见。不同节点的因子互质,故其乘积 ω 整除 q。两个候选 Hermite 多项式之差正是这种次数至多 N−1 的 q;被次数为 N 的多项式整除,只能为零。
存在性方面,把次数至多 N−1 的 N 维多项式空间,映射到所要求的 N 个导数值。此映射线性,刚才的论证表明其核为零。同维有限维空间之间的单射线性映射也是满射,故任意指定数据均可达到。若没有这个独立性论证,单纯数方程条数并不能证明存在性。
余项所需的是计入重数的 Rolle 定理。设足够可微的函数在相异有序点有零点,指定重数为 r1,…,rℓ。在 rj≥2 的点,导数继承重数 rj−1;Rolle 定理又在每个相邻开间隙提供一个零点,共 ℓ−1 个,且与继承零点相异。因此按重数共有 R=j∑rj 个零点,便使导数至少有 R−1 个按重数计的零点。在足够可微下可重复使用;节点位于端点时,采用单侧延拓的端点导数值仍然成立。
固定非节点 x,令 c=(f(x)−p(x))/ω(x)。函数 q(t)=f(t)−p(t)−cω(t) 在节点具有总重数 N 的零点,并在 x 多出一个零点。把上述 Rolle 论证用 N 次,在所得某个 ξ 处有
0=q(N)(ξ)=f(N)(ξ)−cN!,因 p(N)=0,且 ω 是首一 N 次多项式,余项公式得证。ξ 可以依赖 x,却不是已知可微的 x 函数;不能把它当作常数来微分余项。
端点值及斜率给出明确三次基底
对 a<b,令 h=b−a、t=(x−a)/h,定义
H00=2t3−3t2+1,H10=t3−2t2+t,H01=−2t3+3t2,H11=t3−t2.
给定值 ya,yb 及相对于 x 的斜率 va,vb,插值式为
p(x)=yaH00(t)+hvaH10(t)+ybH01(t)+hvbH11(t).
在 t=0,1,值基函数取得所需值且 t 导数为零;H10,H11 的端点值均为零,并分别具有相应的单位 t 导数。因 d/dx=h−1d/dt,乘上 h 才把给定斜率换成正确单位。这些检查加上唯一性,便证明公式。
若数据来自 f∈C4([a,b]),其余项为
f(x)−p(x)=24f(4)(ξ)(x−a)2(x−b)2,∥f−p∥∞≤384K4h4.
写成 t=(x−a)/h 后,有 t2(1−t)2≤1/16。对 f(x)=(x−a)2(x−b)2,四个 Hermite 数据全为零,p=0、f(4)=24,故界可达到。此主张使用精确端点导数数据,并不把从含噪声函数值估计的导数当作精确值。
对线性二阶导数积分,构造每个样条片段
三次多项式的二阶导数是仿射函数。若端点二阶导数为 Mi,Mi+1,积分两次再匹配两个端点值,得到
Si(x)=6hiMi(xi+1−x)3+6hiMi+1(x−xi)3+(yi−6Mihi2)hixi+1−x+(yi+1−6Mi+1hi2)hix−xi.直接代入得 Si(xi)=yi、Si(xi+1)=yi+1 及两个指定二阶导数。这四个条件唯一决定一个三次多项式:齐次差的二阶导数为仿射函数,在两端为零,故二阶导数恒零;差本身因而仿射,再由两端零值可知它恒零。
此片段的端点斜率为
Si′(xi)=δi−6hi(2Mi+Mi+1),Si′(xi+1)=δi+6hi(Mi+2Mi+1).把 Si−1′(xi) 与 Si′(xi) 设为相等,整理后正好得到上述三对角方程。函数值本已连续相接,二阶导数亦在共同的 Mi 相接;这些方程再使一阶导数相等,故拼合函数确实属于 C2。三阶导数可以跳变,定义容许这点。
非均匀系统有唯一解
若 n=1,没有内部未知数;M0=M1=0,样条便是通过两个值的直线。以下设 n≥2。内部系数矩阵 T 对称,对角为 2(hi−1+hi),相邻元素为 hi。把内部向量 z 延伸为 z0=zn=0,其二次型为
zTTz=2i=0∑n−1hi(zi2+zizi+1+zi+12)≥i=0∑n−1hi(zi2+zi+12)>0当内部 z 非零时严格为正,因 a2+ab+b2≥(a2+b2)/2 且每个 hi>0。故 T 正定且非奇异。解出二阶导数后,片段公式构造出存在的样条;反之,每个自然插值样条均须满足同一系统和片段公式,所以唯一。
直接精确算术构造只需线性数量的运算。令 ai=2(hi−1+hi)、bi=6(δi−δi−1),以 q1=a1、c1=b1 起步;对 2≤i<n 消去前一个未知数:
qi=ai−qi−1hi−12,ci=bi−qi−1hi−1ci−1.然后 Mn−1=cn−1/qn−1,再对 i=n−2,…,1 回代 Mi=(ci−hiMi+1)/qi。主元均非零:q1>h1,而 qi−1>hi−1 推出 qi>hi−1+2hi>hi。这证明精确算术中的除法有定义。浮点实现仍需数据缩放及舍入分析;递推本身并非普遍准确度保证。
证明透视
方程与未知数的计数
先计数:内部二阶导数共有 n−1 个,每个内部节点各有一条斜率相等的方程,共 n−1 条;自然条件 M0=Mn=0 去掉两个端点未知数,所以系统是方阵。斜率方程是 C1 连续性唯一进入的地方;函数值及二阶导数的一致由各段的构造保证。每个 hi 为正这一点用了两次:在二次型中,以及在主元界 qi>hi 中,因此没有隐藏等距假设。若重复节点使 hi=0,片段公式便无定义;若去掉自然条件,就会留下两个自由参数,下文单一区间的反例正说明这一点。
最小弯曲来自正交交叉项
取任意 C2 插值函数 g,令 e=g−S,则 e(xi)=0。在一段上分部积分两次,使用该片段三阶导数的单侧值:
∫xixi+1Si′′e′′dx=[Si′′e′−Si′′′e]xixi+1.剩下的积分含 Si(4)=0,所以消失。这只要求 e∈C2 及 Si 为多项式,不需要 g 有三阶导数。含 e 的边界项因每个节点 e=0 而消失。在内部节点,左右两段的 S′′e′ 项因 S′′ 及 e′ 连续而抵消;最外端项则因 S′′(a)=S′′(b)=0 消失。因此 ∫abS′′e′′=0。
展开 g′′=S′′+e′′ 即得 J(g)=J(S)+J(e)。若等号成立,连续非负函数 (e′′)2 的积分为零,故 e′′ 处处为零。于是 e 仿射;它在两个相异端点为零,迫使 e=0。注意竞争函数的端点斜率和二阶导数从未受限制。自然条件属于极小样条,负责消除端点交叉项;若要求每个竞争者也满足自然条件,只会证明较弱的主张。
证明透视
每个假设消去哪一种边界项
真正的想法是:误差 e=g−S 在积分内积下与 S′′ 正交,所以 J 像勾股和一样分解。每个假设消去一类边界项:e(xi)=0 消去所有 Si′′′e 项,尽管 S′′′ 在节点处跳跃;S′′ 与 e′ 连续使内部的 S′′e′ 项相互抵消;S′′(a)=S′′(b)=0 消去最外两项。没有自然条件时,交叉项为 S′′(b)e′(b)−S′′(a)e′(a)。若 S′′(b)=0,取在各节点为零且 w′(a)=0=w′(b) 的 w∈C2,则 J(S+ϵw)=J(S)+2ϵS′′(b)w′(b)+ϵ2J(w),取符号合适的小 ϵ 即低于 J(S)。最后,J(e)=0 与两个端点零点一起给出唯一性。
算例
对 [0,1] 上的 f(x)=x4,端点数据为 f(0)=f′(0)=0、f(1)=1、f′(1)=4,Hermite 三次多项式是
p(x)=H01(x)+4H11(x)=2x3−x2,f(x)−p(x)=x2(x−1)2.在 x=1/2,p=0、f=1/16。由 f(4)=24,一致余项界为 24/384=1/16,在中点达到。三次多项式甚至在 1/4 取负值 p(1/4)=−1/32,虽然 f 非负。匹配函数值和斜率并不自动保留中间的正负号。
取节点 0,1,3 及值 0,1,0。此时 h0=1、h1=2、δ0=1、δ1=−1/2。唯一内部方程是 6M1=−9,故 M1=−3/2,而 M0=M2=0。代入得
S(x)={(5x−x3)/4,(3−x)−(3−x)3/8,0≤x≤1,1≤x≤3.接点两侧函数值均为一,一阶导数均为 1/2,二阶导数均为 −3/2。两个最外端二阶导数为零;但 S′(0)=5/4、S′(3)=−1,确认“自然”并非端点水平。这不是单一全局三次多项式,因两段三阶导数分别为 −3/2 和 3/4。
例题 5.2.7
(与全局插值二次多项式比较弯曲量)
同一数据亦由二次多项式 q(x)=x(3−x)/2 插值。其 q′′=−1,故 J(q)=3。样条则在 [0,1] 上有 S′′=−3x/2,在 [1,3] 上有 S′′=3(x−3)/4,所以
J(S)=∫0149x2dx+∫13169(x−3)2dx=43+23=49.变分恒等式因而给出 J(q−S)=3/4。极小曲线的二阶导数平方代价,小于这个更光滑的全局多项式。最小弯曲比较的是此特定泛函,并非多项式次数或存在多少阶导数。
常见错误
反例模式
边界条件不足会留下解族;相互矛盾的额外条件使问题无解
只有一段 [0,1]、端点值均为零时,每个三次多项式 p(x)=x(1−x)(A+Bx) 均插值,留下两个自由参数;没有内部接点条件去消除它们。自然端点条件选出零函数。
改为端点值零和一时,自然条件迫使仿射函数 p′′ 在两端为零,故 p′′=0、p=x,端点斜率均为一。再加 p′(0)=p′(1)=0 便不相容。匹配这两个固定斜率的三次多项式是 3x2−2x3,端点二阶导数为 6、−6。自然与固定斜率条件描述不同插值问题,同时施加未必可行。
即使边界条件彼此相容,自然样条也只回答它被构造来回答的问题。
反例模式
自然样条不会自动承袭端点 Hermite 余项界,也不保证单调
对单一区间 [0,h] 上的 f(x)=x2、h>0,自然样条为直线 S(x)=hx,最大绝对误差是 h2/4,但 f(4)=0。含四阶导数的三次 Hermite 余项不能使用,因这条直线没有插值真正的端点斜率。
又如节点 0,1,2 与非递减数据 0,0,1,自然样条有 M1=3/2,第一段为 (x3−x)/4,在 0<x<1 为负,在 1/2 等于 −3/32。最小弯曲不是非负或单调限制;保形插值需要额外设计选择。
端点导数是独立数据;没有额外假设,不能从两个相近函数值精确恢复它。若以差商代替所指定的斜率,问题及其误差分析都随之改变。
重复节点插值不会平均互相矛盾的函数值:同一阶导数若被指定两个不同值,条件直接不相容。
三次样条精确插值样本,并非平滑样条,也不会自动移除测量噪声。若样本带有误差,样条会在节点处把误差原样重现。
小结
Hermite 插值把导数计作独立条件及带重数的零点,在明确的全局光滑假设下由重数 Rolle 论证得到余项。自然三次样条则在任意正节点间距上,解正定三对角系统来决定二阶导数。所得 C2 曲线在全部 C2 插值函数中唯一最小化二阶导数平方积分。边界选择、精确导数数据、近似误差及保形条件仍是不同问题。
练习
快速检查
(指定 p(0)=1、p′(0)=0、p(1)=2,求 Hermite 多项式及节点乘积。若数据来自 f∈C3([0,1]) 且 ∣f′′′∣≤6,给出 x=1/2 的误差界。解释为何重复零点处的函数值条件不能代替导数条件。)
设 p=a+bx+cx2,代入三个条件。
解答 · 答案
共有 N=3 个条件,零点处重数二、一点处重数一。写 p=a+bx+cx2,得 a=1、b=0、c=1,所以 p=1+x2。节点乘积为 ω(x)=x2(x−1)。在 1/2 的余项界为 6∣(1/2)2(−1/2)∣/3!=1/8。再写一次 p(0)=1 只重复同一线性方程,不限制 b,仍留下二次插值式解族。
快速检查
(在 [2,4],指定端点值分别为一和三,斜率分别为零和一。用 t=(x−2)/2 写出 Hermite 三次式,求在三的值,并检查两端相对 x 的导数。若 ∣f(4)∣≤24,在所需光滑假设下给出一致余项界。)
取 h=2,并保留斜率项上的因子 h。
解答 · 答案
区间长度为二,故 p=H00+3H01+2H11=1+4t2−2t3。在 x=3,t=1/2,得到 p=7/4。导数为 p′(x)=(8t−6t2)/2=4t−3t2,在 t=0 为零,在 t=1 为一。若数据来自 f∈C4([2,4]),一致界为 24(24)/384=1。右端斜率项若忘记乘以区间长度,便无法通过导数检查。
快速检查
(构造通过 (0,1),(1,0),(2,1) 的自然样条。求内部二阶导数、两段三次式、接点共同斜率及弯曲泛函,再与二次式 (x−1)2 比较。)
当 h0=h1=1,内部方程为 4M1=6(δ1−δ0)。
解答 · 答案
此时 h0=h1=1、δ0=−1、δ1=1,故 4M1=12,即 M1=3。两段为 [0,1] 上的 S0(x)=1−3x/2+x3/2,及 [1,2] 上的 S1(x)=1−3(2−x)/2+(2−x)3/2。接点的值为零、斜率为零、二阶导数为三,外端二阶导数为零。两段二阶导数是 3x、3(2−x),故 J(S)=3+3=6。二次式的二阶导数为二,弯曲量八,比样条多二,正好等于 J((x−1)2−S)。
快速检查
(对算例中通过 (0,0),(1,1),(3,0) 的样条 S,令 gϵ(x)=S(x)+ϵx(x−1)(x−3),其中 ϵ 为实数。证明它们是容许的 C2 竞争者,并精确求 J(gϵ)。使用极小化定理是否要求它们端点二阶导数为零?)
所加的多项式 x(x−1)(x−3) 在每个节点都为零。
解答
多项式 w=x(x−1)(x−3) 在三个节点均为零,所以每个 gϵ 都是 C2 插值函数。由 w′′=6x−8,
J(w)=∫03(6x−8)2dx=324−432+192=84.与 S 的交叉项由已证恒等式消失,故 J(gϵ)=9/4+84ϵ2,唯一最小点为零。竞争者的端点二阶导数分别为 −8ϵ、10ϵ,一般不为零,但仍被容许:交叉项论证只需要极小样条满足自然端点条件。