为什么要对插值多项式微分?
有限差分公式用附近的一小组数值估计导数。多项式谱方法采用另一条路:先找出一个通过全部数值的多项式,再对这个多项式作精确微分,最后在原来的节点计算导数。所得公式仍然是用一个矩阵乘以数值向量。矩阵通常是稠密的,因为每个插值基底多项式都依赖整个网格。
“精确微分”必须说清楚微分的对象。在精确算术下,我们精确地微分插值多项式。其导数未必等于提供样本的原函数的导数。未被网格分辨的振荡、高次多项式,甚至很小的测量误差,都可能令看来准确的函数值产生差异很大的导数。我们先证明代数结论,再指出哪些额外假设足以支持导数逼近。
本节的数据和函数均取实值,先在 [−1,1] 上讨论。以 Pn 表示次数至多为 n 的多项式空间。上一节使用 n 个内部高斯(Gauss)节点,插值多项式属于 Pn−1。本节的 n 则表示次数上限:共有 n+1 个洛巴托(Lobatto)节点,包括两个端点。这两种网格及其系数公式不能混用。
网格、插值多项式与矩阵定义
固定整数 n≥1,设
θj=njπ,xj=cosθj,j=0,…,n.因此 x0=1>x1>⋯>xn=−1。给定向量 v=(v0,…,vn)T,以 pv∈Pn 表示唯一满足 pv(xj)=vj 的插值多项式。令 ℓj 为满足 ℓj(xi)=δij 的基底多项式,则 pv=j=0∑nvjℓj。定义
Dij=ℓj′(xi),0≤i,j≤n.
余弦在 [0,π] 上严格递减,所以节点互异。拉格朗日(Lagrange)公式给出插值多项式的存在性;非零的 Pn 多项式不可能有 n+1 个互异零点,故插值唯一。因此,对每个数值向量,D 的定义都有意义,不必预先假定向量来自光滑函数。
尚未计算任何矩阵元素,线性性已经给出核心等式:
(Dv)i=j=0∑nℓj′(xi)vj=pv′(xi).
接下来要将定义化成明确的元素公式,尤其是对角元素。分母的正负将由上述节点递减的次序决定。
推导非对角元素
回顾 Tk(cosθ)=cos(kθ)。当 0<θ<π,微分得
Tn′(cosθ)=nsinθsin(nθ).
所以 Tn′ 在内部节点 x1,…,xn−1 为零。取极限得到端点值
Tn′(1)=n2,Tn′(−1)=(−1)n−1n2.
这些结论在 n=1 时仍然成立,只是此时没有内部节点。因此可选择以下节点多项式:
W(x)=(x2−1)Tn′(x).
它的次数是 n+1,零点恰好是 n+1 个互异节点 xj。确实,Tn′ 的次数是 n−1,所列的 n−1 个互异内部零点已是其全部零点,且都是单零点;又有 Tn′(±1)=0,所以端点因子补上其余两个单零点。首项系数并不重要:将 W 乘以非零常数,不会改变以下基底公式:
ℓj(x)=(x−xj)W′(xj)W(x).
在 xj 看似存在的奇点可以消去。用 x−xj 除 W 得到多项式,其在 xj 的值正是 W′(xj)。
为计算节点处的 W′,先推导切比雪夫(Chebyshev)微分方程。对 Tn(cosθ)=cos(nθ) 两次使用链式法则,得到
(1−x2)Tn′′(x)−xTn′(x)+n2Tn(x)=0.(1)
起初这个等式在 −1<x<1 成立。两边都是多项式,故它其实处处成立。在内部节点,Tn′(xj)=0,式 (1) 给出
W′(xj)=(xj2−1)Tn′′(xj)=n2Tn(xj)=n2(−1)j.
在端点,改用 W′(x)=2xTn′(x)+(x2−1)Tn′′(x),得到 W′(1)=2n2 及 W′(−1)=2(−1)nn2。定义 c0=cn=2,而 1≤j≤n−1 时 cj=1,便可合写为
W′(xj)=n2cj(−1)j.(2)
当 i=j,微分基底公式并利用 W(xi)=0,即得
Dij=(xi−xj)W′(xj)W′(xi)=cjcixi−xj(−1)i+j.(3)
等价地,重心插值权重可取为 λj=(−1)j/cj 的共同非零倍数,式 (3) 就是 Dij=λj/[λi(xi−xj)]。
式 (3) 中的因子是 ci/cj,即比值 λj/λi,而不是它的倒数。写成 cj/ci 只会改变端点所在行或列的元素,因此不容易发现。对 n=2,这会给出 D01=−1/2 而不是 −2,第 0 行之和变成 3/2−1/2+1/2=3/2。下面证明的恒等式 D1=0 能立即暴露这个错误:正确矩阵的每一行之和都为零。
对角元素与端点的符号
在单零点 xi 附近,对基底公式作泰勒(Taylor)展开得
ℓi(x)=1+2W′(xi)W′′(xi)(x−xi)+⋯,Dii=2W′(xi)W′′(xi).(4)
对内部节点,先将式 (1) 微分:
(1−x2)Tn′′′−3xTn′′+(n2−1)Tn′=0.(5)
由 W′′=2Tn′+4xTn′′+(x2−1)Tn′′′、式 (5) 及 Tn′(xi)=0,得到 W′′(xi)=xiTn′′(xi)。将它和 W′(xi)=(xi2−1)Tn′′(xi) 代入式 (4),便有 Dii=−xi/[2(1−xi2)]。这里可以除以 Tn′′(xi):式 (2) 说明 W′(xi)=0,而 xi2−1=0。
对 x0=1,将 1 代入式 (5) 得
Tn′′(1)=3n2(n2−1).
所以 W′′(1)=2n2+4n2(n2−1)/3。将它和 W′(1)=2n2 代入式 (4),得到 D00=(2n2+1)/6。反射对称性则给出 xn=−1 处相反的符号。确实,由基底的唯一性,ℓn(x)=ℓ0(−x),故 ℓn′(−1)=−ℓ0′(1)。
对 n≥1 及网格 xj=cos(jπ/n),由基底微分定义的矩阵,其非对角元素由式 (3) 给出,对角元素为
D00=62n2+1,Dnn=−62n2+1,Dii=−2(1−xi2)xi(1≤i≤n−1).(6)此矩阵满足 D1=0。对每个 q∈Pn,
D(q(x0),…,q(xn))T=(q′(x0),…,q′(xn))T.(7)
式 (3)–(6) 已由定义中的基底多项式推得。若向量是 q∈Pn 的样本,唯一性说明其插值多项式就是 q;对这个多项式恒等式求导便证明式 (7)。取 q=1 得 D1=0。特别地,对角元素也可由下式计算:
Dii=−j=i∑Dij(8)这是恒等式,不是另一个近似公式。
证明透视
精确插值为何能推出精确微分?
证明只有一个关键步骤:把关于 n+1 个数的陈述换成多项式恒等式。假设 q∈Pn 只用到一次,即用唯一性把样本的插值多项式认定为 q 本身。此后两者的导数处处相同,在节点上自然也相同;式 (7) 只是把核心等式 (Dv)i=pv′(xi) 用于这个 v。行和恒等式是 q=1 的特例,无需另外计算。去掉这个假设,这一认定就不成立:在 n+1 个点相等不能推出两个函数恒等,有限个等式也不能求导。在 n=2 的网格上,x3 与 x 的样本相同,端点导数却不同。剩下的结论只是:D 给出插值多项式的导数。
最小的网格已经能检验式 (3) 和 (6) 中的每个符号。
当 n=1 时没有内部节点,且 c0=c1=2。在节点 (1,−1) 上,式 (3) 和 (6) 给出
D=21(11−1−1).每一行之和为零,符合 D1=0。q(x)=x 的样本是 (1,−1)T,而 D(1,−1)T=(1,1)T 与两个节点处的 q′=1 一致。由于 1 和 x 张成 P1,这两项检查已在该网格上完整验证了式 (7)。
若节点按递增顺序存储,须同时反转矩阵的行和列:新矩阵为 PDP−1,其中 P 是反序置换矩阵。这里不会多出负号,因为求导仍然是对 x 进行的。对 n=1,递增节点 (−1,1) 给出 PDP−1=21(−1−111),它把 x 的样本 (−1,1)T 映为 (1,1)T。若把矩阵取负,得到的导数就成了 −1。
完整的小例子与边界方程
例题 6.2.4
(三个节点、一阶导数与狄利克雷(Dirichlet)问题)
当 n=2,节点为 1,0,−1。式 (3) 和 (6) 给出
D=3/21/2−1/2−2021/2−1/2−3/2,D2=111−2−2−2111.取 q(x)=1−x2,其数值向量是 u=(0,1,0)T。直接相乘得 Du=(−2,0,2)T 及 D2u=(−2,−2,−2)T,与 q′=−2x 和 q′′=−2 一致。
现在用同一网格,以配点法处理 (−1,1) 上的 −u′′=2,并要求 u(1)=u(−1)=0。先将端点数值设为零,再于唯一的内部节点要求微分方程成立:
−(D2u)1=−u0+2u1−u2=2.因此 u1=1。插值多项式恰好是 1−x2,即这个特定边界问题的解。精确解属于 P2,所以其样本满足配点方程,而这个只有一个未知数的系统有唯一解 u1=1。这些事实解释了此处的精确恢复;它们并不是一般配点法的误差估计。
可以重复微分,因为 pv′∈Pn−1⊂Pn,所以其导数样本的插值多项式就是 pv′ 本身。归纳可得:对每个整数 m≥0,都有 (Dmv)i=pv(m)(xi),其中 D0 是单位矩阵。在精确算术下,Dn+1=0,因为每个 Pn 多项式的 n+1 阶导数均为零。这个代数事实并不表示反复做浮点矩阵乘法就没有误差问题。
概念视角代数
切比雪夫系数基下的同一算子
在节点基下 D 是稠密矩阵。写 pv=k=0∑nakTk,并令 V 为元素 Vjk=Tk(xj)=cos(jkπ/n) 的 (n+1)×(n+1) 矩阵,则 v=Va;插值的唯一性保证 V 可逆。每个 Tk′ 都是满足 m<k 且 k−m 为奇数的 Tm 的线性组合,所以求导在系数向量上由一个严格上三角矩阵 M 表示。因此
D=VMV−1.这个相似关系立即说明,在精确算术下为什么 Dn+1=0,以及为什么 D 的特征值全为零:两者在 M 上一目了然。对 n=1,V=(111−1)、M=(0010),而 VMV−1 正是上面的两节点矩阵。
对一般区间 [a,b],假设 a<b,使用 t=(a+b)/2+(b−a)x/2。对 t 的一阶微分矩阵是 2D/(b−a),二阶微分矩阵是 4D2/(b−a)2。映射后的节点仍由 b 递减至 a,缩放因子为正。
反例模式
先删边界再平方会丢失信息
一个看似自然的做法是先从 D 删去端点的行和列,再将余下的矩阵平方,以近似零边界值下的二阶导数。对 n=2,这个内部矩阵是 (0),平方仍是 (0)。但 D2 的内部元素为 −2,正是例子需要的系数。函数 1−x2 在端点的一阶导数并不为零;删去这些中间导数值,便会丢失它们对二阶导数的贡献。应先形成完整的二阶微分算子,再从二阶方程消去已知的函数值。指定 u 的值,不等于指定 u′ 的值。
混叠与一个充分收敛条件
以 Lnf 表示 f 在洛巴托节点上、属于 Pn 的插值多项式。在节点角度处,2nθj=2jπ。对整数 k≥0,写成 k=2nq+s,其中 0≤s<2n,并定义
rn(k)={s,2n−s,0≤s≤n,n<s<2n.
于是 cos(kθj)=cos(rn(k)θj),由唯一性得
LnTk=Trn(k).(9)
与上一节的内部高斯网格不同,这个网格折叠指标时没有额外负号。特别地,LnT2n=1。因此,将微分矩阵作用于 T2n 的样本会得到零,但 T2n′(1)=4n2。这是网格未能分辨原函数,不是次数至多为 n 的多项式精确性失效。
收敛论证必须同时控制未被分辨的项及其导数。式 (9) 直接给出一个精确的充分条件。
假设
f(x)=2a0+k=1∑∞akTk(x),k=1∑∞k2∣ak∣<∞.(10)此级数在 [−1,1] 定义一个连续可微函数,端点取单侧导数,而且
∥f′−(Lnf)′∥∞≤2k>n∑k2∣ak∣⟶0.(11)所以在假设 (10) 下,由 D 给出的数值在各自的网格上一致逼近真正的导数。
由导数公式和 ∣sin(kθ)∣≤k∣sinθ∣,得 ∥Tk′∥∞≤k2。例如,将 e2ikθ−1 分解为 (e2iθ−1)h=0∑k−1e2ihθ,再用三角不等式,便证明上述正弦不等式。由连续性,导数界也适用于端点。因此,在 (10) 下,函数值级数和导数级数均一致收敛。为证明可以逐项微分,可从一个固定点积分一致收敛的导数级数;微积分基本定理加上该固定点的级数收敛,就将所得积分与 f 联系起来。这证明可微性,亦证明导数可连续延伸至端点,给出单侧导数。
对固定的 n,插值算子是有限个点值与基底多项式的线性组合。因此,一致收敛级数可通过这个固定算子逐项插值及微分。用式 (9),并注意 k≤n 时 rn(k)=k,得
f′−(Lnf)′=k>n∑ak(Tk′−Trn(k)′).因为尾和内 rn(k)≤n<k,其一致范数不超过 k>n∑∣ak∣(k2+rn(k)2)≤2k>n∑k2∣ak∣。加权级数收敛,所以尾和趋零。最后,在 (Dv)i=pv′(xi) 中取 v=(f(x0),…,f(xn))T,便知所得向量正是 (Lnf)′ 的节点值。
证明透视
权重 k 平方的用途
(10) 中的权重与 ∥Tk′∥∞≤k2 相配,用了两次:一次用来逐项微分 f 的级数,一次用来估计尾项。关键一步是:Ln 是点值的固定线性组合,因此可以穿过收敛的和;混叠规则 (9) 再把每个尾项送到某个 Trn(k),其中 rn(k)≤n<k,其导数不会更大,于是得到因子二。k≤n 的项恰好抵消。仅有 ∑∣ak∣<∞ 只能控制函数值,不能控制导数。
条件 (10) 是充分条件,并非必要条件;它比函数值系数绝对可和更强。仅有函数值插值误差的估计,不能自动推出导数估计。尤其不能在一般插值余项中,将未明确指定的中间点当成常数后直接微分。导数收敛需要独立论证,例如上面的系数尾和证明。
噪声与有限精度
假设测量向量为 v+e,其中 ∣ej∣≤ε。即使矩阵乘法完全精确,由数据误差产生的导数误差仍是 De,每一行均满足
∣(De)i∣≤εj=0∑n∣Dij∣.(12)
在 x0=1,由于 1−xj>0,非对角元素 D0j 的符号为 (−1)j,而对角元素为正。又因 Tn(xj)=(−1)j,对 Tn 的精确性给出
j=0∑n∣D0j∣=j=0∑nD0j(−1)j=Tn′(1)=n2.
反射对称性给出 xn=−1 处相同的绝对行和。取容许的扰动 ej=ε(−1)j,其插值多项式为 εTn,便达到端点误差界 εn2。因此,端点微分可将有界数值误差按 n 的平方放大。常数扰动的导数为零,所以这是最坏情况结论,不是每个误差序列的预测。
当 n=2 时,D 的第 0 行是 (3/2,−2,1/2),各元素绝对值之和为 4=n2;中间一行 (1/2,0,−1/2) 的绝对值之和为 1。取 e=ε(1,−1,1)T,即 εT2=ε(2x2−1) 的样本,则
De=ε(23+2+21, 21−21, −21−2−23)T=ε(4,0,−4)T,与 εT2′(x)=4εx 在节点处的值一致。两个端点行都达到式 (12) 的界 εn2=4ε,而内部误差为零,低于该行的界 ε。同样大小的常数扰动 ε(1,1,1)T 则给出 De=0。
形成及应用 D 时也会有算术误差。端点附近节点聚集,令 1−x1=2sin2(π/(2n)) 为 n−2 的量级;直接将靠近 1 的已舍入余弦值相减,可能损失相对精度。恒等式
xi−xj=−2sin2n(i+j)πsin2n(i−j)π
避免了这一处相减,但其数值计算仍须注意有限精度。用式 (8) 计算对角元素,可在构造矩阵时落实常数函数的恒等式;其后的内积运算仍可能留下舍入残差。在精确算术下,等价的作用公式是
(Dv)i=j=i∑Dij(vj−vi).
这种写法把常数数据的抵消直接呈现出来。这些重排都不能消除式 (12) 证明的数据敏感性,本节也没有建立任何具体实现的后向误差界。加密网格时,必须同时考虑逼近尾和、数据误差及算术误差。
练习
练习 6.2.7
(在 n=2 的网格上,将上面列出的矩阵作用于 f(x)=x3 的样本。与三个节点处真正的导数比较,并求出插值多项式。)
基础
解答(3)
1由样本认出插值多项式
x3 的样本为 (1,0,−1)T,与 x 的样本相同。因此 L2f=x。
2作用矩阵
D(1,0,−1)T=(1,1,1)T,即 x 在三个节点处的导数。
3与真正的导数比较
真正的导数向量为 (3,0,3)T,所以节点处的差 f′−(L2f)′ 是 (2,−1,2)T。采样无法区分这两个原多项式;只有其中一个的次数至多为二。
练习 6.2.8
(证明对每个 n≥1,都有 LnT2n−1=T1。计算 x=1 处真正导数与插值导数之差。)
核心
解答(2)
1在节点角度处折叠指标
关键一步
因为 (2n−1)θj=2jπ−θj,其余弦等于 cosθj。因此 T2n−1 与 T1=x 在每个节点取值相同,由插值的唯一性得 LnT2n−1=x。
2比较端点处的导数
在 1 处的导数差是 T2n−1′(1)−1=(2n−1)2−1=4n(n−1)。当 n=1 时,此差为零,与预期一致:此时原多项式是 T1,属于所表示的空间。
练习 6.2.9
(对 [0,2] 上的 −u′′=6t 及边界条件 u(0)=u(2)=0,使用映射后的 n=2 网格,只在内部节点要求微分方程成立。求出配点多项式,与精确解比较,并解释为什么两者节点值相同,导数却不同。)
核心
解答(5)
1映射网格
映射后节点为 t=2,1,0,而 2/(b−a)=1,所以对 t 的导数仍用上面列出的 D2。
2解内部配点方程
端点值为零,内部方程就是 2u1=6,得到 u1=3。插值多项式为 q(t)=3t(2−t),满足 −q′′=6,因此在 t=1 处满足原方程。
3求精确解
将 u′′=−6t 积分两次并代入边界条件,得精确解 u(t)=4t−t3。它在网格上同样取值 (0,3,0),但 u′(1)=1,而 q′(1)=0。
4解释节点值为什么相同
关键一步
步长为一的中心二阶差分 v0−2v1+v2,对每个三次多项式都等于其在 t=1 处的精确二阶导数;只需对 1,t,t2,t3 逐一验证,再用线性性即可。因此,三次精确解的样本满足同一内部方程和边界值,而单个未知数的方程组的唯一性迫使节点值相同。
5分清函数值与导数
也可以直接看出 u(t)−q(t)=−t(t−1)(t−2) 在三个节点处均为零,但它的导数在那里不必为零。二次配点多项式并非在每一点都满足微分方程。
练习 6.2.10
(假设 f 有式 (10) 的级数表示,且对 k≥1 有 ∣ak∣≤Ck−p,其中 C>0、p>3。验证加权可和性,并由式 (11) 推导明确的幂次界。另外,选择有界的节点误差,使端点导数误差达到 εn2。)
综合
解答(4)
1验证加权可和的假设
由系数假设得 ∑k2∣ak∣≤C∑k2−p<∞,故可用 (10)。
依据: 级数 ∑k2−p 恰在 p>3 时收敛。
2用积分比较尾和
因为 x2−p 在 [n,∞) 上递减且可积,
2k>n∑k2∣ak∣≤2Ck=n+1∑∞k2−p≤2C∫n∞x2−pdx=p−32Cn3−p.这估计的是精确数据下插值多项式的导数误差。
3构造达到上界的数据误差
关键一步
取 ej=εTn(xj)=ε(−1)j,则每项的绝对值为 ε,而 (De)0=εTn′(1)=εn2。
4分开两种误差来源
第一个估计不包含测量误差;逼近尾和与数据误差必须分别计入。
与其他笔记的联系
上一节的切比雪夫笔记介绍余弦变量代换、连续系数,以及内部高斯节点的另一套混叠规则。有限元笔记则提供从边界方程建立有限维系统的另一条路。本节处理的是一种特定的多项式微分构造及一个简单配点例子。一般谱边值问题的稳定性、多维算子、解析函数的收敛率及浮点稳定性分析仍需另外讨论。