消去有规律的误差
数值近似的误差有时具有可利用的结构。假设目标量 的近似满足
其中 ,而且两个步长对应相同常数 。那么 的主导误差为 。取 与 的适当线性组合,就能消去该项。
定义 7.11.1
(Richardson 外推)
设 的近似 的主导误差为 ,且在每个步长上的 都相同。外推值定义为
权重 与 之和为一,因而保留 ;加权后的主导误差之和为零。这个推导依赖真正的渐近展开,不能仅因为两个近似值接近就套用结论。
定理 7.11.2
(主导误差的消去)
设 ,其中 ,且对 有 。则对 ,
证明
(把展开式代入组合)
由于 ,展开式在两个步长上都适用:
括号内为 。除以 得 ,而
证明透视
消去误差需要相同的系数
证明中唯一用到误差结构的一步,是括号变为零;它变为零,是因为 在 和 上乘的是同一个 。其余只是三角不等式。反之,若只知道 ,同样的计算只得到 ,阶数并不比原来的界好:两个步长上互不相关的误差未必抵消。权重之和为一只用了一次,使 在组合中的系数为 。
例题 7.11.3
(对中心差分作外推)
对足够光滑的 ,
故 ,且 。取 及 ,则 ,与 及 一致。取 和 ,得 、,所以
结果在这里精确,是因为三次函数的展开在 项之后就终止;对一般的 ,只有 项被消去,仍余下 的误差。
以上结论描述的是精确算术中的截断误差。相近数相减以及近似值的组合可能放大浮点误差,因此不断将 减半未必改善计算结果。
梯形公式构成的表
设 是在均匀网格上计算 的复合梯形近似,网格间距 。对固定的足够光滑的 ,Euler–Maclaurin 展开只含偶次幂:
使用的项数越多,需要的光滑性也越高;这里把展开作为假设,而不是说连续性就能保证它成立。令 ;步长不断减半,提示我们逐列作外推。
定义 7.11.4
(Romberg 表)
令 (),并对 定义
由数 排成的三角形数组称为 Romberg 表;第 列是梯形值的第 次外推。
为什么每一列的因子不同?因子 就是 (),即第 列所消去的那一项的阶。下面的结果把这一点说清楚。
定理 7.11.5
(Romberg 各列的精度)
假设上述 的展开对每个 都成立,系数 不依赖于 ,且余项以 为界。则对 及 ,
其中 ,。特别地,。
证明
(对列数作归纳)
时即为假设,。设结论对第 列成立,其中 。因 ,故 ,而系数 在 与 中相同。所以在 中, 的系数是 ,而 的总权重为 。除以 便得到所列的系数。当 时因子 为零,所以求和从 开始。余项满足
仍是 的常数倍。若 ,首个保留的项为 阶;若 ,求和为空,误差为 。
第一次外推正好是两个子区间上的 Simpson 公式:
例题 7.11.6
(二次函数的一次外推)
在 上积分 。单区间梯形值为 ,两个区间给出 。外推得到
恰好等于精确积分。这是因为这个二次函数的梯形误差恰好与 成比例(这里 );一个例子不能证明第一次外推对所有函数都精确。
例题 7.11.7
( 的三行 Romberg 表)
在 上积分 ,。梯形值为 、,并由 得
第 1 列使用因子 :
第 2 列使用因子 :
| 0 | 1 | 1/2 | ||
| 1 | 1/2 | 9/32 | 5/24 | |
| 2 | 1/4 | 113/512 | 77/384 | 1/5 |
与 分别是两个和四个子区间的 Simpson 公式。最后一项精确,是因为多项式的 Euler–Maclaurin 级数会终止:这里 ,只有第 2 列所消去的两项。对非多项式的被积函数,这一项仍带有 的误差。
网格可能漏掉函数的结构
反例模式
两次近似相等仍可能有非零误差
在 上取 。它在 、、 处都为零,因此单区间与双区间梯形值及其外推值都为零;然而真实积分为 。所以两个近似值相等本身不能给出普遍误差界。下一级网格能分辨这一振荡:。这个函数十分光滑;问题是前两级网格太粗,无法显示它的结构。
基于表中相邻数值的停止准则只是指标,除非另有假设能控制余项。尖峰、尚未分辨的振荡以及端点奇异性都可能破坏所假设的展开,或者把信息隐藏在取样点之间。即使展开成立,舍入误差最终也会与截断误差竞争。应检查被积函数和表的稳定性,并在把指标当作保证之前使用适用于该问题的误差定理。
常见错误
常见错误
(权重中用错幂次)
若 ,正确的组合取 。若改用 的公式 ,则得 :误差仍是 阶,只是符号反了。权重必须对应误差中真正出现的幂次。
常见错误
(每一列都用同一个因子)
在 的表中,第二列需要因子 。若再用第 1 列的因子 ,得 ,而不是 。此时权重之和虽为一,却没有消去 项。
练习与解答
快速检查
(假设严格有 ,求 。)
代入 ,再按 的幂次合并。
解答 · 答案
代入得 : 项消失,四阶项仍在。
快速检查
(为什么外推权重之和必须为一?)
想想目标 在组合中如何出现。
解答 · 答案
权重之和为一能保留共同目标 ,而不是改变它的倍数: 的系数是 。
快速检查
(对 上的 ,求单区间梯形值及第一个 Romberg 外推值。)
两个梯形值都来自同一条直线。
解答 · 答案
、,故 。梯形公式对仿射函数精确。
快速检查
(如果表中两个数在机器精度内相等,精确积分一定与它们相等吗?)
回想 上的被积函数 。
解答 · 答案
不一定。上面的 给出相等的零近似,但真实积分为 。