让新样本发挥作用
当函数求值昂贵,我们仍希望近似 ,其中 。将区间等分为 个小区间,步长为 ,复合梯形值为
将步长减半时,无须重新计算所有旧节点。新增的 个点恰在旧相邻节点的中间,所以在精确运算下,
检查权重:在 中,旧内部节点的权重是 ,旧端点的权重是 ,每个新中点的权重是 ,与右边完全一致。若求值成本高,应保存旧函数值。累加、节点构造和函数值的舍入误差,与下面的精确恒等式是不同问题。
逐列消去不同次幂
定义 6.5.1
(Romberg 表)
从 开始,令 ,其中 。一旦两个相邻网格的第 列已算出,就定义
由数 ()组成的三角形阵列称为 Romberg 表。
分母随列数改变:每一列都用 并不能实现同样的消项。第一列比较步长为 和 的值,消去 项;第二列比较剩余主导项与 成正比的估计,依此类推。
定理 6.5.2
(在明确展开条件下外推)
令 。固定整数 ,假设当 时,
其中系数与 无关。那么对每个固定的 ,
这是固定列在网格足够细时的渐近结论,并非单个表项的误差保证。
消项的证明
证明
(对列序号作归纳)
第零列具有假设中的展开。假设第 列展开到 后,首个可能非零项为 ,各系数均与 无关,余项为 。较粗网格满足 ,其对应项就是 。将细网格的值乘以 再减去粗网格的值,便消去这一项。分母 非零。其余偶次幂仍有与网格无关的系数;由于 固定,余项仍为 。由归纳法得证。
证明透视
展开式比单个误差界提供更多信息
证明中唯一的一步,是在两个网格之间消去 。这只因为系数 在两个网格上是同一个数才成立;“常数与 无关”的假设正是用在这里。只有 ,并不能说明相邻网格的带符号误差具有相同的首项系数。表格消去的是展开式中的共同项,而不是任何被 控制的误差。
另有两点使归纳得以完成。 的项 变为 ,系数仍与 无关,所以新的一列具有同样形式的展开。余项至多乘以 ;这只因 固定才是常数,定理对沿对角线 前进的情形没有给出任何一致结论。
对于足够光滑的函数,Euler–Maclaurin 公式给出这样的偶次幂展开。例如若 ,则
因此定理可取 。这些系数来自该公式,并非仅从表格推断出的误差界。若某个导数差为零,相应首项系数可能消失,特定问题的收敛因而更快。分段光滑、端点奇异或被采样网格漏掉的振荡,都需要另行分析;增加表格深度本身不能验证展开条件。
递推式还有另一种等价的读法,可以解释其中的权重。
概念视角代数
Romberg 即外推到零步长的多项式
令 、,则 。设 是关于 、次数至多为 的多项式,在 时于 取值 。插值多项式的 Neville 递推在 处为
这正是 Romberg 递推,所以 :每个表项用 的多项式穿过 个已算出的梯形值,再读出它在达不到的步长 处的值。展开假设等于说:把 看成 的函数时,它能被这类多项式很好地近似。
第一外推列另有一个熟悉的名字。
命题 6.5.3
(第一列就是复合 Simpson 法则)
对每个 , 等于宽度为 的 个小区间上的复合 Simpson 法则,其中 。特别地, 是 个小区间上的复合 Simpson 值。
证明
(逐个节点比较权重)
用 ()标记细网格节点,并记 。在 中,每个端点的权重为 ,其他细节点的权重为 。在 中,端点权重为 ,偶数号内部节点权重为 ,奇数号节点不出现。相减后,端点得 ,奇数号节点得 ,偶数号内部节点得 。除以 得
即步长为 的复合 Simpson 法则。
四次函数的完整算表
例题 6.5.4
( 的精确算表)
取 上的 ,则 。梯形值为 、、。例如,加密公式给出
由上面的命题,第一外推列等于细网格上的复合 Simpson 值。现在把这些值放进完整表格:
| 0 | — | — | |
| 1 | — | ||
| 2 |
例如,,而 。最后恰好等于积分,是本多项式和精确运算的特殊情况。一般而言,有限次消项后仍有其余误差项。
更多算例
例题 6.5.5
( 的观察收敛率)
在 上取 ,。精确地,
于是 、、。精确到六位小数:
| 误差 | 误差 | 误差 | ||||
|---|---|---|---|---|---|---|
| 0 | — | — | — | — | ||
| 1 | — | — | ||||
| 2 |
梯形误差依次缩小约 倍和 倍,趋近 项的因子 。第一列在一次减半中改善约 倍,正趋向 项的因子 。这里 在 上光滑,且 ,首项系数确实存在,定理描述了这个趋势;但它仍然没有给任何单个表项提供误差界。
例题 6.5.6
(边界情形:周期被积函数与过粗的首个网格)
在 上取 ,则 。 的各阶导数在 与 处相等,所以 Euler–Maclaurin 的每个系数都是零。取样得 (两端点的值都是 ),而 与 已是精确值。外推则给出
追溯到 的表项,比它们所用的最细梯形值(已经精确)还差。单一小区间太粗,无法分辨一个周期:它的误差是混叠,而不是展开式的首项。这与定理一致,因为定理是 的渐近结论;它也说明由未进入渐近区间的网格构成的表项可能误导。
数值一致不等于证明精度
反例模式
所有采样点都可能漏掉积分
令 ,定义域为 。它连续、非负,在有限个零点之间为正,因此积分为正。然而,前面一、二、四个小区间的三层网格上,所有采样值均为零。整个三角表都是零,相邻表项完全一致。仅凭这个表,无法区分该函数和零函数。因此,若没有额外信息,例如有根据的导数界,表格不能保证误差达到指定容限。
当误差展开有根据且首项占主导时,相邻表项之差可作为实用指标。首项接近消失、网格尚未进入渐近区间、求值误差或舍入都可能使指标误导。可靠实现还要检测浮点节点重复、非有限值和资源限制;除非另有误差界,停止报告应将估计称为估计。
常见错误
(每一列都用因子 )
权重 只适用于第 列。对四次函数的表使用 ,得 ,误差仍约为 ;正确的 则给出 。第 列要消去的项与 成正比, 加倍时它乘以 。
常见错误
(跨越端点奇点作外推)
对 上的 ,导数在 处无界,梯形误差并非偶次幂展开:它含有与 成正比的项。数值上,相邻梯形误差缩小的因子接近 ,第一列误差 、、 也是如此,而不是表格所针对的因子 。应先消除奇点,例如作代换 ,然后才使用 Romberg 权重。
练习与解答
快速检查
(在 上由 加密至 ,需要哪些新点?)
新点位于相邻旧节点的正中。
解答 · 答案
旧节点为 ;新中点是 。所以 。
快速检查
(若 、、,计算 、 和 。)
第 列用分母 ,第 列用分母 。
解答 · 答案
依次为 、、。这些数相等本身并不能证明 。
快速检查
(若第 列首个未消去误差项为 ,为什么用因子 ?)
比较该项在步长 与 的网格上的值。
解答 · 答案
步长加倍使该项乘以 。将细网格估计也乘以此因子后,其首项与粗网格对应项相等,相减便消去。
快速检查
(仅凭 ,能否证明 ?)
试考虑符号随 交替的误差。
解答 · 答案
不能。若某序列的误差为 ,它满足该界,但相邻网格的带符号系数不同:。外推后的误差仍是 的非零倍数。系数相同的偶次幂展开提供了缺失的条件。