动机
均匀求积在函数平缓和变化迅速的地方投入相同的取样密度。自适应方法则反复检查子区间,把工作集中到看起来需要更多精度的部分。这个想法虽然直观,实际算法却必须处理共享样本、局部容差和未能完成的情况;更重要的是,它必须说清楚“成功”究竟证明了什么。
本节给出两种使用同一分割策略的算法。第一种通过粗、细 Simpson 值的差来估计误差;第二种假设已知四阶导数界,从而在精确算术下得到真正的绝对误差保证。
定义
对 ,令 ,单区间 Simpson 值为
定义 、、。两种公式共使用五个点 。细规则的误差估计量为 ;带符号的修正值为 。此指标在模型下估计未修正值 的误差,而非 的误差;与 一起返回时仍然只是启发式指标。符号不能随便改变:在平滑的主导项模型中, 估计的是 ,不是其相反数。
绝对容差 是积分误差预算,其单位与积分相同。每次二分,将容差各分一半给两个子区间。这只是分配预算,不自动证明真实误差满足预算。积分接近零或发生抵消时,相对容差需要另外处理。
定理/命题
定理 6.6.1
(差值究竟估计什么)
令 为固定紧致区间, 且 。对面板 ,当 时,下列展开一致成立:
因此 ,且 。大 中的常数可以依赖 的界。以上结论不能推出 。
定理 6.6.2
(由导数界得到的保证)
设 ,已知 。将区间分成有限个长度为 的面板 ,每个面板计算两子区间 Simpson 值之和 。在精确算术下,
若已知各面板上的界 ,可在相应项中替换全局界 。若返回修正值 ,则另一个有效上界是各项 之和。
导数界必须对整个面板成立,不能仅由五个取样点上的数值断言。可以用已证明的解析不等式或合适的区间算术求界。函数值近似、求和舍入、溢出以及端点舍入都需要额外控制;上述精确算术保证本身不涵盖这些误差。
证明思路或证明
证明
(在面板中点作 Taylor 展开)
在 处将函数 Taylor 展开至五次。积分及两种规则都关于 对称,并且精确积分所有三次以下多项式,因此五次奇项也消失。对 ,直接计算得 、,故 。乘上 Taylor 系数 ,得到粗规则主项 。在每个子面板中心重新展开该四次式,其余项次数至多为三,规则对它们精确;两子面板宽度减半,故其四次误差之和变为原来的 。当六阶导数有界时,Taylor 余项逐点为 ,积分与加权和各增加一个长度因子,故余项均为 。
两式相减得 ,于是得到定理中的修正关系。特别是当 时,主项消失,估计量的相对解释更不可靠。
证明
(把单面板 Simpson 误差界相加)
单个宽度为 的 Simpson 面板误差界为 。对宽度均为 的两个子面板分别应用并相加,得到 。再对所有面板求和并用三角不等式,即得整体结论。由于 ,对修正值再用一次三角不等式便得到第二个界;这并不声称修正一定改善认证误差界。
证明透视
为什么一个证明给出估计,另一个给出上界
第一个证明只有一个关键步骤:两种规则都关于 对称,且对三次式精确,所以除余项外,各自的误差都只是 的倍数;面板减半时,四次误差乘以 。 中的 完全来自这个缩放。假设 只用于余项:使它逐点为 ,再对总质量为 的权重积分后成为 。其常数没有算出,所以证明只以“相差未知的 项的等式”收尾,从不给出不等式。这就是即使 非常光滑, 仍然只是估计的原因。
第二个证明完全不看 。它只用 及一个在整个面板上都有效的数 ,对每个子面板套用已知的单面板不等式,再把绝对值相加。若去掉关于 的假设,取样值中没有任何数据能代替它,下面的反例正说明这一点。
例题详解
例题 6.6.3
(四次函数的完整自适应计算)
取 ,区间为 ,绝对容差为 。根面板上 、、,故 ,需要二分,并给每一半分配 的容差。
在 ,粗、细值分别为 和 ;在 ,分别为 和 。两个差值都是 ,故两个估计量都是 ,两叶均通过。修正值分别为 和 ,总和是 。
根面板用了五个不同的取样点;检查两个子面板只需再计算四个点,即 的奇数倍位置。共享端点和中点都被重复利用。此四次函数碰巧被修正公式精确积分,但停止条件并不保证一般函数也如此。
例题 6.6.4
(同一棵树上的严格保证)
对 可取 。每个半区间细规则的误差界是 ,两者之和 。返回两项细规则之和 ,便在精确算术下得到不超过 的严格误差界。事实上此例恰好达到这个界:。修正结果恰为真值,是四次函数的特殊计算结果,而不是由估计量保证的。
例题 6.6.5
(边界情形:平方根奇点)
在 上取 ,其积分为 。这里 在 附近无界,所以对接触原点的面板,两条定理都不适用。精确到六位小数,根面板的值为
细值的实际误差为 ,约为 的八倍。若 ,启发式测试在根面板就接受,返回 ,其误差 超出容差四倍以上。修正的符号正确,但由 缩放预测的大小是错的,因为该缩放假设四阶导数有界。必须在 附近进一步细分,或作 之类的变量代换,估计量才可信。
可以实现的递归
下面用精确实数描述数学算法。simpson(u,v,fu,fm,fv) 使用上面的公式;eval(x) 要么返回函数值,要么报告失败。depth 是非负整数;浮点实现还必须检查新节点严格有序。
integrate(f, a, b, tolerance, maxDepth):
require a < b, tolerance > 0, maxDepth >= 0
m = (a+b)/2
evaluate fa=f(a), fm=f(m), fb=f(b), or return failure
A = simpson(a,b,fa,fm,fb)
return visit(a,b,fa,fm,fb,A,tolerance,maxDepth)
visit(u,v,fu,fm,fv,A,tau,depth):
m = (u+v)/2; l = (u+m)/2; r = (m+v)/2
if nodes are not strictly ordered: return failure
evaluate fl=f(l), fr=f(r), or return failure
left = simpson(u,m,fu,fl,fm)
right = simpson(m,v,fm,fr,fv)
B = left + right; D = B-A
if abs(D)/15 <= tau: return success(B+D/15, abs(D)/15)
if depth == 0: return failure
leftResult = visit(u,m,fu,fl,fm,left,tau/2,depth-1)
rightResult = visit(m,v,fm,fr,fv,right,tau/2,depth-1)
if either child failed: return failure
return success(leftResult.value+rightResult.value,
leftResult.estimate+rightResult.estimate)
返回的估计量是接受的叶节点指标之和,不是经过证明的误差上界。程序可以在失败时附上部分结果,但不能声称它满足容差保证。实现时还应处理非有限函数值或中间结果。浮点代码需依据允许的数值范围选择避免溢出的中点公式,并检测节点重合与容差下溢;仅限制递归深度并不能认证精度。
若要严格保证,把接受条件改成 ,返回 及此界,其他分割和失败规则不变。若已知全局 有限且算术精确,均匀二分至深度 时,每个叶节点的界与所分配容差之比为 。故足够大的有限 保证接受,叶预算求和又证明整体误差不超过 。此论证在所有节点使用同一个全局 ;更精细的局部界也可认证叶节点,但各自需要有效界和终止论证。如果最大深度 maxDepth 过小仍会失败。这个终止论证不适用于有任意不光滑或不准确函数值的启发式测试。
常见错误
反例模式
五个样本不能认证所有光滑函数
在 上令 。它是非负多项式,仅在有限个点为零,所以积分严格为正。两种根面板规则只看到零,因而 ,无论正容差多小,启发式测试都会接受。将 乘以常数可使漏掉的积分任意大。这不违反导数界定理:放大函数时,导数界也改变。
各叶估计量的和低于预算只是一项记账结果,并不证明真实误差受这些估计量约束。反过来,严格界可能远大于实际误差;不能认证也不代表答案必然错误。即使最后的树不均匀,每个子面板分得父面板一半预算仍是有效分配,因为所有叶预算之和等于根预算。
概念视角结构
三个不同的断言
差值衡量两个有限取样公式的一致程度;渐近模型将差值联系到误差主项;严格保证则在定量假设下控制整个误差。三者不能不经论证地互相替代。
常见错误
(修正方向弄反)
由于 ,而模型给出 ,修正值是 。若写成 ,或改用 ,答案就离积分更远。对 上的 ,正确公式恰好给出 ;符号反转则得 ,其误差 是未修正值 误差的两倍。
常见错误
(把整个容差传给每个子面板)
若每个子面板分得 而非 ,有 个叶的树可接受总和接近 的局部估计。正是减半规则使叶预算之和等于根容差;没有它,连记账上的总数也会超出要求的预算。
快速检查
快速检查
(若 ,加到 上的修正是什么符号?)
回想 与 的定义。
解答 · 答案
答案是正号:。这只回答模型中的符号问题,并不证明 低估积分。
练习
快速检查
(在 上取 和 。求根面板细规则的严格误差界;它能否认证 ?)
对长度 的单一面板使用保证公式。
解答 · 答案
界为 ,大于 ,所以此测试不能认证该容差。对于本四次函数,这也是细规则的实际误差:。
快速检查
(证明任意有限二叉分割树的所有叶预算之和等于根预算。)
追踪一次分割对总和的影响。
解答 · 答案
最初唯一叶节点拥有全部预算。每次分割把预算 的一个叶换成两个预算 的叶,不改变总和。对有限次分割归纳即可。
快速检查
(若每个函数样本的绝对误差至多为 ,求精确加权运算下分区细 Simpson 值之和的扰动界。)
Simpson 权重均为正。
解答 · 答案
每个子 Simpson 规则的权重为正,总和等于子区间长度;故面板 上的扰动不超过 ,整体至多 。这里不假设重复利用的样本相互独立。舍入以及假设界之外的求值偏差仍需另行处理。
快速检查
(将 写成五个等距根节点上的加权公式,并说明它为何精确积分所有至多五次多项式。)
写 ,再收集每个样本的系数。
解答 · 答案
设 、,则 ,合并权重得 。两原规则均精确积分三次以下多项式,修正恰好消除四次误差;对称性使以中点为中心的五次幂在规则和积分中均为零。线性组合说明至多五次均精确,并不说明六次也精确。