动机
当函数只能在选定的点求值时,插值用一个在这些点取相同值的多项式代替函数;数值积分则用有限个函数值的加权和近似积分。二者密切相关:对插值多项式积分便得到一个求积公式。这解释了权重及其多项式精确度,但不能单凭节点上的吻合就保证高次多项式在节点之间也准确。
应区分三种误差。插值误差比较精确函数和穿过精确数据的多项式;求积截断误差比较精确积分和精确加权和;浮点舍入及测量数据误差则会影响实际计算。下文的界在精确算术下成立,并要求列出的导数存在且有界,不能直接作为程序舍入误差的证明。
定义
定义 7.1.1
(插值多项式与 Lagrange 基函数)
给定互异节点 x0,…,xn 和数值 y0,…,yn,插值多项式是满足 p(xi)=yi、次数至多为 n 的多项式。令
ℓi(x)=0≤j≤nj=i∏xi−xjx−xj,p(x)=i=0∑nyiℓi(x).当 i=j 时 ℓi(xj)=1,否则为零;节点互异确保分母非零。若两个次数至多为 n 的多项式插值相同数据,其差有 n+1 个互异零点,故恒为零。这同时说明上式给出的插值多项式存在且唯一。
对互异节点,定义 f[xi]=f(xi),并递归定义
f[xi,…,xj]=xj−xif[xi+1,…,xj]−f[xi,…,xj−1].同一插值多项式可以写成
pn(x)=f[x0]+k=1∑nf[x0,…,xk]j=0∏k−1(x−xj).节点次序会改变系数,但不会改变最终多项式。新节点加入时可以保留前面的项,只需增加一个差商项。
Aitken–Neville 插值可直接计算某个目标点的值。令 Pi,i(x)=yi,对于 i<j 递归地设
Pi,j(x)=xj−xi(x−xi)Pi+1,j(x)−(x−xj)Pi,j−1(x).
两个低阶插值式在每个共同节点 xk 处都等于 yk,两项权重之和为一;在另外两个端点,适当的系数为零。归纳可知 Pi,j 的次数至多为 j−i,因此它插值第 i 至 j 个数据点,唯一性证明了递推式。只需一个目标值时,三角数组很方便;若需在很多点求值,可以考虑能反复使用的表示。
计算 Neville 表
要把递推式用于计算,需要明确更新顺序。固定目标 t,简写 Pi,j=Pi,j(t)。从数据 Pi,i=yi 出发,先算所有 j−i=1 的项,再算 j−i=2 的项,如此继续,直到得到 P0,n。每个新项组合上一层的两个结果。总共需要 n(n+1)/2 次更新,即一个目标点需 O(n2) 次算术运算,不计获取原始数据的开销。换一个目标点要重新计算表。
设节点两两互异,数组 A0,…,An 最初存放 y0,…,yn。对每个 k=1,…,n,按 i=0,1,…,n−k 递增的顺序更新:
Ai←xi+k−xi(t−xi)Ai+1−(t−xi+k)Ai.则第 k 层之后,每个 i≤n−k 的 Ai 都等于 Pi,i+k(t),最后的 A0 就是 P0,n(t),只需 n+1 个存储位置。
第 1 层之前 Ai=Pi,i。设第 k 层之前,i≤n−k+1 的 Ai=Pi,i+k−1。本层此前的更新只改动下标小于 i 的元素,所以更新 Ai 之前,Ai=Pi,i+k−1、Ai+1=Pi+1,i+k。因此递推式把 Pi,i+k 存入 Ai。对两个下标归纳,最后的 A0 就是所求值。这里假定精确算术与节点两两互异,故分母非零;这并非浮点误差界的证明。
取节点 0,1,3,对应值 1,2,10,在 t=2 求值。第一层为
P0,1=1−0(2−0)2−(2−1)1=3,P1,2=3−1(2−1)10−(2−3)2=6.下一层得到 P0,2=[(2−0)6−(2−3)3]/(3−0)=5。事实上,数据位于 1+x2 上,它在 2 处的值为 5。单数组算法中,依次保留的有效元素为 (1,2,10)、(3,6)、(5)。若第一层从右向左更新,旧值 A1=2 在供 A0 使用前已被 6 覆盖,便得到 A0=11,最终错误结果为 23/3。
表格能告诉我们什么
差值 P0,k(t)−P0,k−1(t) 比较的是采用不同数据集的两个插值多项式。加入节点后数值发生变化可以提醒我们注意,但这个差值并不是未知函数误差的保证上界。例如所有 yi=0,而 f(x)=j=0∏n(x−xj),则表中每项均为零,但在节点之外 f(t)=0。要认证函数误差,仍需下文余项定理中的导数界等额外信息。
即使计算完全精确,输入数据的误差也可能被放大。若 ∣δyi∣≤ε,由线性性及 Lagrange 公式可知
∣δp(t)∣≤εi=0∑n∣ℓi(t)∣.
上例在 t=2 的三个权重为 −1/3,1,1/3,故放大因子为 5/3;取与各权重同号、大小均为 ε 的扰动便达到上界。目标点虽在全部节点范围内,仍有一个权重为负。这里讨论的是精确插值对数据的敏感度;表格计算的舍入误差还需另行分析。因此,层间差值小或者目标点位于节点范围内,都不能单独保证准确。
快速检查
(对节点 0,1,2 和数值 1,0,3,计算 t=3 时的 Neville 表。若每个数据都增加 0.1,结果如何变化?)
解答 · 答案
第一层为 P0,1=−2、P1,2=6;于是 P0,2=(3⋅6−1⋅(−2))/2=10。在 3 处的权重为 1,−3,3,总和为 1,所以精确算术下所有数据共同增加 0.1 时结果恰增加 0.1。这种共同平移并非最坏扰动:各数据独立误差均不超过 0.1 时,结果最多可改变 0.7。
求积公式的精确度
区间 [a,b] 上的求积公式 Q(f)=i∑wif(xi) 若对所有次数至多为 d 的多项式精确,并对至少一个 d+1 次多项式不精确,则称其代数精确度为 d。这是代数性质;对一般函数建立误差界还需要正则性和相应导数的估计。
定理/命题
设 x0,…,xn 为 [a,b] 中互异点,f∈Cn+1([a,b])。对任意非节点 x∈[a,b],在包含 x 及全部节点的最小区间的内部存在 ξ,使
f(x)−pn(x)=(n+1)!f(n+1)(ξ)j=0∏n(x−xj).在节点处误差为零。因此若区间上 ∣f(n+1)∣≤M,误差绝对值至多为 Mj∏∣x−xj∣/(n+1)!。
定理 7.1.7
(复合梯形与 Simpson 公式)
令 a<b,h=(b−a)/N,xj=a+jh。复合梯形公式为
TN=h[2f(x0)+f(xN)+j=1∑N−1f(xj)].若 f∈C2([a,b]) 且 ∣f′′∣≤M2,则
∫abf(x)dx−TN≤12(b−a)h2M2.当 N 为偶数时,复合 Simpson 公式为
SN=3hf(x0)+f(xN)+41≤j<Nj 为奇数∑f(xj)+22≤j<Nj 为偶数∑f(xj).若 f∈C4([a,b]) 且 ∣f(4)∣≤M4,则
∫abf(x)dx−SN≤180(b−a)h4M4.
这里的阶数指固定积分区间和导数界、逐步细化网格时的行为。h 减半分别使上述界变为原来的四分之一和十六分之一;某一次实际误差不一定恰好按该比例变化。Simpson 公式虽由二次插值积分得到,对称性却使它对三次多项式也精确。
定理 7.1.8
(两点 Gauss–Legendre 公式)
在 [−1,1] 上,
G2(f)=f(−1/3)+f(1/3)对所有次数至多为三的多项式精确。若 f∈C4([−1,1]),存在 ξ∈(−1,1) 使
∫−11f(t)dt−G2(f)=135f(4)(ξ).对 [a,b],换元 x=(a+b)/2+(b−a)t/2,并将求积结果乘以 (b−a)/2。若 f∈C4([a,b]),误差为 (b−a)5f(4)(ξ)/4320,其中 ξ∈(a,b)。
证明思路
固定不等于任何节点的 x,令 ω(t)=j=0∏n(t−xj),再取 C=[f(x)−pn(x)]/ω(x),定义 F(t)=f(t)−pn(t)−Cω(t)。此函数在 n+1 个节点及 x 处均为零。反复使用 Rolle 定理,在这些点的凸包内得到 F(n+1)(ξ)=0。由于 pn(n+1)=0,ω(n+1)=(n+1)!,便得余项公式。ξ 可以随目标点 x 改变,通常不能把所有目标点的 ξ 当作同一个数。
对于 Newton 形式,先由 Neville 递推式归纳:P0,k 的 xk 系数等于 P1,k 和 P0,k−1 的最高次系数之差除以 xk−x0,因此等于 f[x0,…,xk]。从 P0,k 减去前 k 个节点的插值式,所得次数至多为 k 的多项式在这 k 点为零,故等于该最高次系数乘以 j<k∏(x−xj)。归纳得到 Newton 形式,再由唯一性与 Lagrange 形式相同。
在 [u,v] 上,对通过两个端点的线性插值多项式积分得到梯形公式。插值余项与 ∣(x−u)(x−v)∣=(x−u)(v−x) 给出局部误差界 M2(v−u)3/12。对 N 个宽度为 h 的区间求和即得复合界,不需要假设局部误差相互抵消。
对于中点为 m 的单个 Simpson 区间 [u,v],二次插值积分得到 (v−u)[f(u)+4f(m)+f(v)]/6。为了证明四阶导数误差,改用三次 Hermite 多项式 H:它在 u,m,v 匹配函数值,在 m 还匹配 f′。由于三个取样值相同,f 与 H 的求积值相等;公式又能精确积分三次多项式 H,所以误差等于 ∫uv(f−H)。广义 Rolle 定理给出
f(x)−H(x)=4!f(4)(ξx)(x−u)(x−m)2(x−v).乘积在区间内非正,积分为 −(v−u)5/120。乘积符号固定且非正。连续函数 f(4) 的最大、最小值逐点控制商 (f−H)/[(x−u)(x−m)2(x−v)];以该乘积的负数作为非负权重积分,再用介值定理,便得到某个单独的 ξ 表示积分误差。这里不需要所选 ξx 连续或可测:
∫uvf(x)dx−6v−u[f(u)+4f(m)+f(v)]=−2880(v−u)5f(4)(ξ).共有 N/2 个宽为 2h 的区间,局部误差绝对值求和便得 (b−a)h4M4/180。这个估计需要四阶导数;较不光滑的函数仍可能可近似,但此公式无法为其提供误差证书。
证明透视
为什么中点要算两次
通过 u,m,v 的二次插值,其余项为 f′′′(ξ)(x−u)(x−m)(x−v)/6,核在 m 处变号,只能支持含三阶导数的估计。加上条件 H′(m)=f′(m) 后,核变为 (x−u)(x−m)2(x−v),在区间上符号固定。这样做之所以合理,有两个事实。新增的三次项是 (x−u)(x−m)(x−v) 的倍数,它关于 m 为奇函数、积分为零,所以公式对 f 和 H 给出同一个数。而符号固定的核,正是让 f(4) 的最大、最小值把积分误差夹成单一的 f(4)(ξ) 的关键。若没有这个二重根,变号就会堵住这一步,论证只能得到涉及 f′′′ 的较弱估计。
对于两点 Gaussian 公式,先采用对称形式:节点为 ±c,权重均为 w。奇次单项式的积分与求积值均为零。匹配常数和二次项得到 2w=2、2wc2=2/3,因而权重为一、节点为 ±1/3,所以至多三次均精确。误差证明使用在两节点同时匹配 f 和 f′ 的三次 Hermite 多项式 H。余项中的因子 (t2−1/3)2≥0;求积公式对 H 和 f 的值相同,又对 H 精确。该因子的积分为 8/45,用同样的最大最小值论证得到误差 f(4)(ξ)(8/45)/4!=f(4)(ξ)/135。对 t4,误差为 8/45=0,故代数精确度恰为三。允许调整节点及权重能提高每次求值的精确度,但不会消除近似或舍入误差。
例题
节点 0,1,2 的值分别为 1,2,5。差商为 f[0,1]=1、f[1,2]=3、f[0,1,2]=1。Newton 形式给出
p2(x)=1+x+x(x−1)=1+x2.在 x=1/2 时值为 5/4。Neville 表中此目标点的第一层为 P0,1=3/2、P1,2=1/2,再递推得 P0,2=5/4。由唯一性,Lagrange 公式给出同一多项式。虽然目标点位于全部节点范围内,计算 P1,2 时相对于节点 1,2 是外插。
例题 7.1.10
(有误差证书的 Simpson 计算)
令 f(x)=ex,积分区间为 [0,1],取 N=2、h=1/2。Simpson 公式给出
S2=61+4e1/2+e≈1.718861.因为 f(4)(x)=ex≤e,误差至多为 e/2880≈0.000944。精确积分为 e−1≈1.718282,实际误差约为 0.000579;界不是精确预测。此处 Simpson 值高于积分,与单区间公式中 ∫f−S2 为负一致。
例题 7.1.11
(将 Gauss 节点移到新区间)
对 [0,2] 上的 f(x)=x4,换元 x=1+t 得
G=(1−1/3)4+(1+1/3)4=956.精确积分为 32/5,所以 ∫02x4dx−G=8/45。对 (1+t)4 应用 [−1,1] 上的余项,其四阶导数为 24,也得到 24/135=8/45。此公式对三次多项式精确,但并非对所有四次多项式精确。
即使插值多项式唯一,节点之间的表现也可能很差。对 [−1,1] 上的 Runge 函数 f(x)=1/(1+25x2),等距节点的高次插值会在端点附近出现很大的振荡。改变节点或使用分段低次插值可能改善表现。余项界展示了因子 j∏∣x−xj∣ 的影响,但高阶导数界增长也会使估计失去信息;仅在节点处误差小不足以控制整个区间。
常见错误
无论节点之间的误差多大,插值多项式在数据节点处的残差都为零。应检查光滑性、节点位置和余项大小;对计算数据,还需考察结果对数据扰动的敏感性。若导数界未知或极大,形式上的误差界就不能提供有效的数值证书。
Simpson 公式对三次多项式精确,并在 C4 条件下满足四阶导数误差界。仅靠精确度不能推出一般函数的误差常数。同样,Gauss 公式的代数精确度是关于多项式的性质,不是所有光滑函数都被精确积分的保证。
总结
Lagrange、Newton 和 Neville 方法描述同一个唯一插值多项式。余项定理将逼近误差与导数及节点几何联系起来。积分局部插值多项式产生 Newton–Cotes 公式;Gaussian 求积通过选取节点提高多项式精确度。误差界需要相应正则性,且截断误差界与代数精确度均不能单独量化浮点误差。
练习
快速检查
(对数据 (0,1),(1,0),(2,3) 写出 Newton 插值形式,并计算 x=3 处的值。)
解答 · 答案
第一层差商为 −1 和 3,故 f[0,1,2]=2。于是 p(x)=1−x+2x(x−1)=2x2−3x+1,p(3)=10。
快速检查
(对 [0,π] 上的 f(x)=sinx,求 N=10 的复合梯形误差上界,并判断近似值位于积分之上还是之下。)
估计 ∣f′′∣,并利用凹性。
解答 · 答案
h=π/10,且 ∣f′′∣=∣sinx∣≤1,所以 ∣I−T10∣≤π3/1200。sin 在此区间为凹函数,弦位于图像之下,故 T10≤I=2。
快速检查
(在 [−1,1] 上用两点 Gauss 公式计算 f(t)=t4,并与精确积分比较。)
计算 t4 在 ±1/3 处的值。
解答 · 答案
求积值为 2(1/3)4=2/9,精确积分为 2/5。误差 2/5−2/9=8/45,与 24/135 一致。
快速检查
(在 [0,1] 上取 N=4 用 Simpson 公式,已知 ∣f(4)∣≤10。求绝对误差界;若 N 加倍又如何?)
在 Simpson 误差界中取 h=1/4。
解答 · 答案
h=1/4,误差界为 10/(180⋅44)=1/4608。N 加倍使 h 减半,界变为原来的十六分之一,即 1/73728;实际误差不一定恰好按此比例变化。
节点复用:梯形、中点与 Simpson 公式
在 N 个粗网格区间上的中点近似是 MN=hj=0∑N−1f(a+(j+21)h);TN 与 S2N 分别是上面定义的梯形和 Simpson 近似。
固定整数 N≥1、区间 [a,b](a<b)以及 h=(b−a)/N。把步长减半为 h/2,得到网格 a+kh/2,k=0,…,2N。偶数下标 k=2j 对应旧节点 a+jh;奇数下标 k=2j+1 对应中点 a+(j+21)h。在 T2N 的定义中把两类节点分开,得
T2N=2h[2f(a)+f(b)+j=1∑N−1f(a+jh)]+2hj=0∑N−1f(a+(j+21)h)=2TN+MN.
在宽度为 h/2 的 2N 个子区间上,复合 Simpson 公式给端点权重 1、奇数节点权重 4、内部偶数节点权重 2,再整体乘以 h/6:
S2N=6h[f(a)+f(b)+2j=1∑N−1f(a+jh)+4j=0∑N−1f(a+(j+21)h)]=3TN+2MN.
代入 MN=2T2N−TN,即得 S2N=(4T2N−TN)/3。
这些都是代数恒等式。凡是能在网格节点上求值的函数,它们都成立。它们不涉及收敛性或光滑性。
计算上的意义。 先保存 TN 已用过的 N+1 个函数值。加密时只需新算 N 个中点值来构成 MN,随后 T2N 与 S2N 便可直接得到,无需重复求值。在浮点运算中,这些恒等式只在舍入误差范围内成立;舍入是另一个独立的问题。
例。 取 [0,1] 上的 f(x)=x2,N=1。则 T1=21,M1=41,T2=83,S2=31。
快速检查
(取 [0,1] 上的 f(x)=x3,N=1。验证 T1=21,M1=81,T2=165,S2=41。)
先求 f 在 0、1/2、1 处的值。
解答 · 答案
节点值为 f(0)=0、f(1/2)=1/8、f(1)=1。代入得 T1=1/2、M1=1/8;再由恒等式得 T2=5/16、S2=1/4。
反例模式
估计值一致不能保证准确
两个估计值相等,并不能证明结果准确。设 [0,1] 上 f(x)=x2(1−x)2(x−21)2。它在 0,21,1 处为零,所以 T1=M1=T2=S2=0。但令 u=x−21 可算得 ∫01f=8401>0。取样值无法反映节点之间的行为。单个例子也不能证明收敛。若要说 (4T2N−TN)/3 能减小误差,必须对 f 另加正则性假设;恒等式本身并不提供这一点。
Newton–Cotes 公式:权重从哪里来
梯形和 Simpson 公式属于一个更大的族。Newton–Cotes 公式积分通过等距节点的插值多项式。闭型公式包含两个端点,开型公式的节点则严格位于区间内部。端点值无法取得时,后者可能有用;但仅凭这一点,不能保证它在端点奇异附近的精度。
设 a<b 且 n≥1 为整数。对闭型公式,令 h=(b−a)/n、xi=a+ih(i=0,…,n)。若 ℓi 是这些节点的 Lagrange 基函数,定义
wi=∫abℓi(x)dx,Qn(f)=i=0∑nwif(xi).
于是 Qn(f)=∫abpn(x)dx。次数不超过 n 的多项式等于自己的插值多项式,因此该公式对它们精确。开型公式的构造相同,但使用 n+1 个内部节点 xi=a+(i+1)(b−a)/(n+2),i=0,…,n。中点公式是开型的 n=0 情形;梯形公式和单区间 Simpson 公式分别是闭型的 n=1 和 n=2 情形。
为什么 Simpson 公式对三次多项式也精确?两类节点都关于 m=(a+b)/2 对称。反射会交换对应的 Lagrange 基函数,因此 wi=wn−i。当 n 为偶数时,中心化单项式 (x−m)n+1 是奇函数,其积分和求积和都为零。每个次数不超过 n+1 的多项式都可写成此单项式的倍数加上一个次数不超过 n 的多项式。所以两类公式在 n 为偶数时的精确度至少为 n+1。这个对称性论证使用精确算术,并不是任意函数的误差界。
取四个节点 0,1,2,3。积分它们的 Lagrange 基函数得到权重 3/8,9/8,9/8,3/8。例如,
ℓ0(t)=−6(t−1)(t−2)(t−3),∫03ℓ0(t)dt=83.反射后的另一端点具有相同权重。两个内部权重也由对称性相等;又因为所有权重之和为 3,它们各为 9/8。作变量代换 x=a+ht,其中 0≤t≤3、h=(b−a)/3,便得到
Q(f)=83h[f(a)+3f(a+h)+3f(a+2h)+f(b)].由插值可知,它对次数至多为三的多项式精确。但对 [0,3] 上的 f(x)=x4,公式给出 99/2,积分则为 243/5;带符号误差 ∫f−Q(f)=−9/10。因此它的精确度恰为三。这个例子也说明,对低次多项式精确并不等于对每个光滑函数精确。
快速检查
(在 [0,3] 上用两个节点 1,2 构造开型公式。将它用于 f(x)=x2,并与积分比较。)
在 [0,3] 上积分每个 Lagrange 基函数。
解答 · 答案
基函数是 ℓ0(x)=2−x、ℓ1(x)=x−1。两者的积分均为 3/2,故 Q(f)=23[f(1)+f(2)]=15/2。积分为 9,带符号误差为 3/2。该公式对常数和一次函数精确,但此例表明它并非对所有二次函数精确。