自适应求积

形式陈述 ​

自适应求积的输入包括 $f$、区间 $[a,b]$、绝对与相对容差、最大函数求值数或细分深度，以及处理非有限函数值的策略。输出应包含积分近似 $\hat{I}$、累计误差估计、函数求值数和状态；状态必须区分达到容差、预算耗尽、端点无法继续细分与函数评估失败。

在每个候选子区间 $J$ 上，算法用共享函数值计算低阶近似 $Q_L(J)$ 和更精细或更高阶的近似 $Q_H(J)$，再以

$$e(J)=\rho |Q_H(J)-Q_L(J)|$$

估计局部误差。系数 $\rho$ 来自所用规则的渐近误差模型，并非普适常数。若 $e(J)$ 超过分配给 $J$ 的容差，便把区间分裂，复用已有节点值并对子区间重复判断。

以自适应 Simpson 为例，令 $S_1$ 是整个 $J$ 上的单面板 Simpson 值，$S_2$ 是左右两个半区间 Simpson 值之和。在四阶渐近误差成立时，

$$I(J)-S_2\approx \frac{S_2-S_1}{15},$$

所以可采用 $|S_2-S_1|/15$ 作为局部估计，并用

$$S_2+\frac{S_2-S_1}{15}$$

作为校正值。若递归实现把父区间绝对容差分给两个子区间，叶区间的估计和便控制全局预算；相对容差则应根据当前全局积分尺度统一判断，避免每个近零局部积分各自使用不稳定的相对分母。

细分过程形成一棵递归树公理库递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。。若最终接受 $N$ 个叶区间，并正确复用共享节点，函数求值与组合成本通常为 $O(N)$，深度优先实现使用 $O(d)$ 栈空间，其中 $d$ 是最大深度；按误差最大区间优先细分的实现需要额外队列存储。实际 $N$ 由函数局部结构和容差决定，没有只依赖初始区间长度的固定公式。

停止时应检查全部已接受区间的误差估计和是否不超过

$$\mathrm{atol}+\mathrm{rtol}|\hat{I}|.$$

这仍是估计器意义下的达到容差，不是严格可验证上界。若达到最大深度、相邻浮点端点中点等于端点、函数返回 NaN/无穷，或误差估计随细分不下降，算法必须返回未达容差状态并保留当前结果与剩余误差。

直觉 ​

固定复合网格把相同数量的样本分给平坦区和困难区；自适应方法先用一对近似询问“这一小段是否已经解释得够好”，只在答案不一致处继续花函数求值。它优化的是信息分配，而不是让单个求积公式突然拥有更高代数精度。

局部规则差像两把分辨率不同的尺子。它们若给出接近结果，通常说明当前尺度下看不到更多结构；但若两把尺子的采样点恰好都绕过同一窄特征，一致只代表共同失察。

例子与边界 ​

考虑 $[0,1]$ 上的窄峰

$$f(x)=\exp (-1000(x-0.37{)}^2).$$

平坦区的粗、细 Simpson 值很快一致，靠近 $0.37$ 的区间则持续产生较大差值，递归树会在那里集中叶节点。与覆盖整个区间的同等最细均匀网格相比，自适应方法可用更少求值分辨局部峰形。

若峰窄到所有初始和子区间采样点都没有命中，$Q_L$ 与 $Q_H$ 可能同时接近零，误差估计也接近零。算法会错误接受区间；这说明两规则差是启发式后验估计，不是对任意函数的确定性证书。已知可能存在窄峰时，应提供断点、变量变换或额外探测，而不是只收紧容差。

端点奇性和不可积函数还会让递归不断追向端点。最大深度可以阻止死循环，却不能把发散积分变成收敛结果。可靠接口应报告“疑似奇性或未达容差”，而不是返回一个看似稳定的小数。

浮点细分也有几何下限。当中点舍入为端点时，新区间不再缩小；继续递归只会重复相同函数值。该状态必须在递归前检测，并作为分辨率耗尽退出。

推论与应用 ​

误差估计公理库残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。区分可计算指示量与真误差，本页的规则差正是这一原则在求积中的实例。Gauss–Kronrod 通过嵌套节点复用函数值，adaptive Simpson 通过面板加倍复用端点和中点；两者都需要各自的误差模型，不能只把“高阶减低阶”当作严格界。

结果报告应包含容差、累计估计、叶区间数、总求值数、最大深度和退出状态。若用户需要数学上可验证的包含区间，还须引入区间算术或带证明的误差界，普通自适应差值不足以承担该规格。

参考资料

• Robert Piessens, Elise de Doncker-Kapenga, Christoph W. Überhuber, and David K. Kahaner, QUADPACK: A Subroutine Package for Automatic Integration, Springer, 1983.
• NIST Digital Library of Mathematical Functions, §3.5: Quadrature.
• Philip J. Davis and Philip Rabinowitz, Methods of Numerical Integration, 2nd ed., Academic Press, 1984.