为什么要有选择地细分?
均匀的求积网格在光滑区域与变化剧烈的区域投入相同的计算量。自适应方法则比较某一子区间及其两半上的近似值,并在两者分歧最大之处进一步细分。只有理解这种比较究竟度量了什么,它才是有用的:两个近似值之差本身并不是任一近似误差的保证界。
定义 7.3.1
(子区间上的 Simpson 比较)
对于宽度为 的区间 ,令 。Simpson 公式为
记 ,。给定 、 和容差 ,自适应问题是:求 的近似值,并决定哪些子区间需要细分。量 称为该子区间的误差指示量。
第二个近似使用五个节点;端点与中点处的函数值是共用的。当某个子区间再次被分割时,之前已计算的函数值可以重复使用。
为什么会出现因子十五
定理 7.3.2
(单个子区间上的 Simpson 误差)
若 ,则存在 ,使
这是标准的 Simpson 余项;其推导(包括符号与常数)见关于复合梯形与 Simpson 公式的那一节。两个半区间上的误差分别具有相同的形式,宽度为 ,但中间点可能不同。若 在该区间上近似为常数,则主导误差近似满足 ,因为两个半区间的贡献为 。将两式相减得
对一般函数而言,即使 光滑,该比值也不一定恰为 。对于次数不超过五的多项式,它则是精确的。
定理 7.3.3
(对次数不超过五的多项式,修正是精确的)
设 是次数不超过五的多项式。则在每个子区间 上,
因此 。
证明
(关于中点的对称性)
把 写成 。Simpson 公式对 精确:对 ,在 上的积分为 ,公式给出 ;奇次幂 的积分与公式值因对称性均为零。对 ,积分为 ,公式给出 ,所以误差为 。因此 ;由 ,这等于 。
对两个半区间(宽度 、中点 )应用同一公式。由于 是次数不超过一的多项式,。于是
两式相减,,所以 。
证明透视
只有在额外信息下,两个误差才共享同一个主导项
因子十五来自对比值为十六比一的两个误差作差。在上面的证明中,“次数不超过五”这个假设恰好用了一次:它使 成为一次函数,所以 在两个半区间中点处的平均值等于它在 处的值。对一般的 ,四阶导数定理在两个半区间上给出不同的未知中间点,并不能说明它们处的导数值相等。要做出可靠的停止判断,要么需要额外的界,要么需要接受该差值只是一种启发式的判据。因此,绝对量 是一个误差指示量,而不是无条件的误差保证。
一个简单的细分规则
给定局部容差 ,在某个区间上计算 。若 ,则接受修正值 ;否则将区间二分并递归,给每个子区间分配容差 。
命题 7.3.4
(各容差之和等于原来的容差)
设递归停止时,被接受的子区间为 ,其中 位于深度 ,容差为 。若每个被接受的值,其真实误差都不超过所分配的容差,则总绝对误差至多为 。
证明
(二分保持容差之和不变)
起初只有一个容差为 的区间。每次二分把容差为 的区间换成两个容差为 的区间,所分配容差之和保持不变。因此最终的容差之和为 ,由三角不等式,总误差至多为这个和。
其前提,即每个被接受的值的真实误差都在容差之内,正是仅凭差值检验不能证明的。实际实现还需要最大递归深度或最小区间宽度、指示量不再减小时的处理策略,以及对函数求值误差与算术误差的考虑。若中点在舍入后等于某个端点,则二分不再产生更小的浮点区间。这样的停止意味着未能达到所要求的精度,而不是容差已被满足的证据。
常见错误
(让每个子区间都得到完整容差)
若两个子区间都继承 而不是 ,一次分割后所分配的容差之和就是 ,继续分割后更大。即使每个子区间都通过了自己的检验,上述命题的保证也不再成立。
命题 7.3.5
(递归的函数求值次数)
若递归所考察的是一棵完整二分树,其被接受的子区间共有 个,则 的不同求值总数为 。
证明
(计算新增的四分点)
有 个叶子的完整二叉树共有 个节点,每个节点(无论被接受还是被分割)都要计算 与 。根节点需要 三个值。对其他节点,其端点与中点都已被求值:端点是父节点的端点或中点,而它的中点是父节点的一个四分点。因此每个节点只需新增自己的两个四分点。深度为 的节点宽度为 ,其四分点是离 为 的奇数倍,所以不同深度节点的四分点互不相同,同一深度的节点对应的子区间互不相交。总数为 。
例题 7.3.6
( 上 的单个子区间)
在 上取 ,则 ,且
于是 ,修正量为 。确实有 。符号很重要:指示量使用绝对值,而修正后的近似使用带符号的差值。
例题 7.3.7
(容差为 的细分过程)
继续考虑 上的 ,取 。顶层区间的指示量为 ,所以要二分,每个子区间得到容差 。对 和宽度为 的区间,,所以两个子区间(宽度 )的 ,指示量为 ,两者都被接受。对左子区间,、,修正值为 。右子区间修正为 ,总和为 。整个过程共用 次求值:根区间的五次,加上四个新增的四分点。
例题 7.3.8
(三次函数被立即接受)
对 上的 ,,,。指示量为零,所以该区间不经任何分割就被接受;在这里这个判断是正确的,因为 Simpson 公式对三次多项式精确。这是指示量为零的边界情形;一般而言,指示量为零并不表示误差为零,下一个例子说明了这一点。
反例模式
取样值相等并不能控制样本点之间的情形
设 上 。它是非负多项式,在 与 所用的全部五个节点处为零,并且在这些节点之外为正。两个近似及其差值都为零,但 。将 乘以任意正常数会按比例放大被遗漏的积分,而五个取样值仍全为零。因此,没有进一步的假设,任何仅使用这些样本的公式都无法给出普适的误差保证。要得到保证,需要额外的假设,例如在该区间上经过验证的某个导数界。
常见错误
(把指示量当作误差界)
因为 就接受区间,并报告“误差至多为 ”,所声称的比已证明的更多。指示量只是一个估计,依赖 在区间上近似为常数。除非另有导数界补上缺少的前提,否则只能把它当作估计来报告。
练习与解答
快速检查
(若 且 ,求指示量与修正值。)
解答 · 答案
指示量为 ,修正值为 。
快速检查
(为什么 中五个值里有三个已能由 得到?)
解答 · 答案
共用的点为 ;只有两个四分点是新增的。
快速检查
(设两个被接受的子区间的误差都经严格证明至多为 ,求总绝对误差的界。)
解答 · 答案
将误差相加并应用三角不等式,得总误差至多为 。
快速检查
(仅凭 能否证明对任意光滑函数积分是精确的?)
解答 · 答案
不能。反例中的非负多项式使两个近似都为零,但其积分为正。
快速检查
(某次运行接受了 个子区间。它共用了多少次不同的 求值?)
解答 · 答案
由求值次数公式,为 。二分树的 个节点各贡献两个四分点,再加根节点的 个值。