数值积分要判断的是函数在两个端点之间的整体行为,但计算机只会在有限多个位置求值。求积法用一个较简单、可以直接积分的对象代替原函数。关键问题是:选择了什么对象、如何加权样本,以及用什么假设控制没有观察到的部分。
复合梯形法积分的是分段线性插值函数。Simpson 法则在每两个子区间上积分二次插值多项式,但连三次多项式也能精确积分。本节推导两条公式,证明带有正确符号与常数的误差界,再用一个可精确计算的例子,分清误差保证与细分后的误差估计。
先数清子区间,再写权重
设 a<b,目标积分为 I=∫abf(x)dx。把区间平均分成 n 个子区间,令
h=nb−a,xj=a+jh(0≤j≤n).
包含两个端点在内,一共有 n+1 个取样点。分清子区间数与点数,才能避免步长及权重的差一错误。梯形法允许任意整数 n≥1;下面的复合 Simpson 法要求 n≥2,而且 n 必须是偶数。
最初的推导假设函数值与算术都精确。求值误差的影响会在后面另行处理。
把取样点的个数当作 n 会得出错误的步长:五个取样点表示 n=4 个子区间,h=(b−a)/4。这个错误同样影响 Simpson 公式,因为它要求子区间数为偶数,所以五个取样点可用,六个则不可用。
积分直线,得到梯形公式
在 [xj,xj+1] 上,连接两个端点函数值的直线,其积分是 h(f(xj)+f(xj+1))/2。把所有子区间的结果相加:内部节点属于左右两段直线,整体端点则只属于一段。
定义 7.7.1
(复合梯形与 Simpson 公式)
复合梯形近似值为
Tn=h[2f(x0)+f(xn)+j=1∑n−1f(xj)].当 n 为偶数,复合 Simpson 近似值为
Sn=3hf(x0)+f(xn)+41≤j≤n−1j 为奇数∑f(xj)+22≤j≤n−2j 为偶数∑f(xj).空和取零。特别是 n=2 时,最后一个和是空的。
梯形权重全部为正,而且总和是 b−a,所以它能正确积分常数函数。它对一次函数也精确,因为线性插值就是原函数。不过,这两点都不表示它能精确积分一般曲线。
推导 Simpson 权重,并解释三次精确性
考虑三个节点 m−h,m,m+h。以 t=(x−m)/h 改变坐标后,节点变成 −1,0,1。二次 Lagrange 基函数为 t(t−1)/2、1−t2、t(t+1)/2;它们在 [−1,1] 上的积分分别是 1/3,4/3,1/3。再乘上坐标变换因子 h,得到单个子区间对(panel)的公式
3h[f(m−h)+4f(m)+f(m+h)].
因此这条公式对所有二次多项式精确。它对 (x−m)3 也精确:这个函数关于中点是奇函数,积分与加权端点和都等于零。任何三次多项式都可写成一个二次多项式,加上一个 (x−m)3 的倍数,所以三次情况也精确。
依次接上互不重叠的子区间对 [x0,x2]、[x2,x4] 等,就得到复合权重。奇数索引节点是子区间对中点,权重为 4;内部偶数索引节点是两个子区间对共用的端点,权重为 2。这正是此处规则要求偶数个子区间的原因。
对相同的嵌套网格,也有一条精确的代数恒等式:
Sn=34Tn−Tn/2(n 为偶数).
逐一比较端点、奇数节点及偶数节点的系数即可证明。这条加权和之间的恒等式是精确的;若要进一步把某种相消解读成未知积分误差的估计,仍须额外论证。
导数界提供真正的误差保证
若 f∈C2([a,b]),且整个区间上 ∣f′′(x)∣≤M2,则
∣I−Tn∣≤12b−ah2M2.此外,若 f′′≥0,则 I−Tn≤0。
在单个区间 [p,q] 上,令 g(x)=(x−p)(q−x)。它在端点为零,而且 g′′=−2。分部积分两次,得到
∫pqf(x)dx−2q−p[f(p)+f(q)]=−21∫pq(x−p)(q−x)f′′(x)dx.非负权重 (x−p)(q−x) 的积分是 (q−p)3/6,所以绝对误差不超过 M2(q−p)3/12。对 n 个宽度为 h 的子区间相加,就得到 nM2h3/12=(b−a)M2h2/12。
同一条恒等式还给出误差符号:若 f′′≥0,则 I−Tn≤0。因此,对二次连续可微的凸函数,梯形近似值不小于真实积分。
若 f∈C4([a,b]),整个区间上 ∣f(4)(x)∣≤M4,而且 n 为偶数,则
∣I−Sn∣≤180b−ah4M4.此外,若 f(4)≥0,则 I−Sn≤0。
证明
(单个 Simpson 子区间对的四阶导数核)
在参考区间 [−1,1],以 L(F) 表示真实积分减去 Simpson 加权和。以 −1 为展开点的 Taylor 积分余项公式,把 F 写成一个三次多项式,再加上
61∫−11(t−s)+3F(4)(s)ds,u+=max{u,0}.这里 t 是函数自变量;当 s>t 时,相应项为零。因为 L 对三次多项式为零,应用 L 并交换积分次序,可得 L(F)=∫−11K(s)F(4)(s)ds。直接积分截断三次函数,再代入三个取样值,得到
K(s)=24(1−s)4−184(−s)+3+(1−s)3=−72(1−∣s∣)3(1+3∣s∣).这个核在 [−1,1] 上非正,积分为 −1/90,因此 ∣L(F)∣≤∥F(4)∥∞/90。
对实际子区间对 [m−h,m+h],令 F(t)=f(m+ht)。其四阶导数为 h4f(4)(m+ht),积分变换再带来一个 h,所以单个子区间对的绝对误差至多是 h5M4/90。子区间对共有 n/2 个,合起来就是 (n/2)h5M4/90=(b−a)h4M4/180。
这个核也证明:若 f(4)≥0,则 I−Sn≤0。此处 Simpson 误差的符号由四阶导数控制,不能只看凸性。
证明透视
四阶导数、符号与常数从何而来
论证靠三步。第一,三次精确性让我们减去三次 Taylor 多项式,只剩下含 F(4) 的积分余项。第二,核 K 在 [−1,1] 上符号不变:这使 L(F)=∫KF(4) 化为界 ∥F(4)∥∞∫∣K∣=∥F(4)∥∞/90,并且只要 F(4) 符号不变,就决定了误差的符号。第三,缩放 F(t)=f(m+ht) 由导数带来 h4,由积分再带来一个 h,所以每个子区间对带有 h5;把 n/2 个子区间对相加损失一个 h 的幂次,剩下 h4。若没有三次精确性,第一步就不成立,论证只能得到三阶结果。
这些保证以所列的导数假设为依据,不能单靠已取样的函数值推出。
这个证明说明了为什么只估计二次插值余项、却不处理相消,就得不到四阶结果。三次精确性多消去了一项,而带符号的核找出了剩余的导数及常数。
常见错误
(凸性并不决定 Simpson 误差的符号)
对凸函数,梯形法会高估,因为 I−Tn 的符号由 f′′ 控制。Simpson 误差则由 f(4) 控制,所以 f(4)<0 的凸函数会被 Simpson 公式低估。应检查误差公式中真正出现的那个导数。
精确计算一个细分表
例题 7.7.4
(在 [0,1] 上积分四次方函数)
对 f(x)=x4,真实积分是 I=1/5。在 [0,1] 上,可以使用 M2=12、M4=24。
例如,S2=(0+4(1/2)4+1)/6=5/24。由于四阶导数恒为 24,复合 Simpson 误差恰好达到所列的界。步长减半时,这个误差恰好减至原来的 1/16。
梯形误差界虽然有效,却偏保守。两个观测误差之比接近 4,但不恰好等于 4,因为误差除了主要的二阶项,还可能有其他项。最坏情况的界不会对每个函数、每个网格都取等号。
例题 7.7.5
(n=2 时的三次函数)
取 [0,1] 上的 f(x)=x3,n=2,则 h=1/2,S2 中偶数下标的和是空的。精确值为 1/4。梯形值为 T2=21(21+81)=165,I−T2=−1/16:这是高估,与 f′′=6x≥0 的预测一致,并且在界 121⋅41⋅6=81 之内。Simpson 给出 S2=61(0+4⋅81+1)=41,精确,因为 f(4)=0,可取 M4=0。恒等式也吻合:T1=1/2,(4T2−T1)/3=(5/4−1/2)/3=1/4=S2。
若要在计算样本前,规划使绝对误差不超过 ε>0 的网格,可以重排误差界。梯形法要求 n2≥(b−a)3M2/(12ε);Simpson 法要求 n4≥(b−a)5M4/(180ε),并且 n 为偶数。只有在整个区间上的导数界已被证明时,这才是有保证的充分选择。
取 [0,1] 上的 f(x)=ex,ε=10−4。在 [0,1] 上 f′′=f(4)=ex≤e<3,所以 M2=M4=3 有效。梯形条件为 n2≥3/(12⋅10−4)=2500,故 n=50,需要 51 个取样点。Simpson 条件为 n4≥3/(180⋅10−4)≈166.7;由于 24=16、44=256,最小的偶数 n 是 4,需要 5 个取样点。验算:n=4 的界为 3/(180⋅256)≈6.5⋅10−5≤10−4,而 n=2 的界为 3/(180⋅16)≈1.04⋅10−3。
细分估计还有额外假设
对足够光滑的固定函数,假设这些均匀网格上的 Simpson 误差具有非零首项 I−Sn=Ch4+o(h4)。步长减半后,首项除以 16。两个近似值相减,得到估计
I−S2n≈15S2n−Sn,I≈S2n+15S2n−Sn.
当目前网格已处于渐近展开适用的范围,这很有用。但不能只因函数光滑,或两个答案接近,就把它当成严格上界。梯形法对应的首项估计用除数 3。如果首项系数为零,或网格太粗、首项还未主导误差,观测到的比例就可能不同。
对 x4,Simpson 误差只有该四阶项,因此 S4+(S4−S2)/15=1/5 恰好精确。但在一个多项式上的成功,不能为任意函数提供精度保证。
反例模式
两次细分答案一致,也可能都漏掉正积分
在 [0,1] 上,定义
f(x)=r∈{0,1/4,1/2,3/4,1}∏(x−r)2.这是光滑的非负多项式,在 S2、S4 所使用的每个节点都等于零。因此两个近似值及其差都是零,但函数在这些有限零点之间为正,积分严格大于零。再把函数乘上任意正常数,两个取样答案仍然是零,真实积分却会按比例放大。
这并不违反导数误差保证:放大函数时,导数界也跟着放大。错误在于把未证明的数值估计,当成了独立成立的导数界。
分开积分误差与求值误差
两条规则的权重都为正,总和是 b−a。如果每个输入函数值与精确的 f(xj) 相差不超过 η,则加权和与精确函数值规则的差不超过 (b−a)η。因此,在尚未计算求和舍入误差之前,三角不等式给出的总误差界是原求积界加上 (b−a)η。
细分时,这个区分尤其重要。增加节点可以减少插值误差,却可能不减少求值误差,并增加浮点运算量。精确算术下关于 I−Sn 的定理,本身不能保证浮点程序的输出。嵌套网格可以重用旧函数值来节省工作,但不会改变上述数学假设。
练习与解答
快速检查
(用 T2 和 S2 积分 [0,1] 上的 f(x)=x2。以 M2=2 验证梯形误差界,并在不估计四阶导数的情况下解释 Simpson 结果。)
解答 · 答案
真实积分是 1/3。梯形值为 (1/2)(0/2+1/4+1/2)=3/8,误差是 3/8−1/3=1/24;误差界为 (1)(1/2)2(2)/12=1/24,刚好取等号。Simpson 值为 (0+4(1/4)+1)/6=1/3,因为它对每个二次多项式都精确。
快速检查
(对 [0,1] 上的 x4,按本节导数界,要保证绝对误差至多 10−4,梯形法最小的 n 与 Simpson 法最小的偶数 n 各是多少?比较取样点数。)
解答 · 答案
梯形界是 1/n2,所以 n=100 足够,而且是此界允许的最小整数,需要 101 个函数值。
Simpson 界是 2/(15n4)。n=6 时为 1/9720>10−4,n=8 时则为 1/30720<10−4。此界随 n 递减,所以 8 是它能保证的最小偶数选择,需要 9 个函数值。这比较的是同一函数的充分导数保证,不是普遍固定的速度提升。
快速检查
(有人说 Simpson 公式对光滑凸函数一定高估。用 [0,1] 上的 f(x)=x2−x4/12 检查,并同时给出导数论证和精确误差。)
解答 · 答案
此时 f′′(x)=2−x2≥1,所以函数凸。但 f(4)=−2,Simpson 核恒等式给出 I−S2>0,即低估。直接计算也得 I=19/60、S2=91/288,所以 I−S2=1/1440。凸性控制梯形误差的符号;本定理中,Simpson 误差符号则由四阶导数控制。
快速检查
(在长度为 2 的区间上,已知 ∣I−Sn∣≤0.0003。每个输入函数值的绝对误差至多 0.0001。在尚未计入求和舍入前,总误差可保证多少?极小的细分差能消除求值误差项吗?)
解答 · 答案
正权重总和是 2,所以求值误差的贡献至多 2(0.0001)=0.0002。三角不等式给出求和舍入前的总误差至多 0.0005。极小的细分差不能消除这一项:误差可能同时保留在两个加权和中,而两者一致并不是对精确函数值的独立误差保证。
解答提示: 下方互动图会显示上面各练习的结果,包括四次幂练习的最小网格数。请先尝试练习,再展开互动图。
展开互动图(显示练习 1–3 的解答)