动机
积分涉及整个区间,计算机却通常只能取得有限个函数值。梯形法使用分段直线;更高精度的方法可以利用对称、对更大多项式空间的准确性,或自由选择节点。不过,准确性仍需函数假设。一个对所有三次多项式准确的公式,未必能看见恰好避开节点的狭窄峰值。
本节区分两种误差信息。已知导数上界可提供严格的先验保证;粗细网格之差则可在渐近模型下估计误差。自适应方法利用后一种信息分配计算量。小的差值是模型下的证据,严格认证则需要真正控制未知函数的假设。
定义
求积公式为 。代数精度是它对所有次数不超过该数的多项式都准确的最大整数。积分和求积都是线性的,因此只需检验单项式 。
在 上取 个等长小区间,。复合中点公式为
当 为偶数,复合 Simpson 公式为
Gaussian 构造使用内积 。令 是与所有低次多项式正交的首一 次多项式。它存在,因为可从 减去其在 上的正交投影。相应 Gram 矩阵正定:非零多项式的平方积分严格为正。
误差估计中设 ,并假设
其中固定 ,主系数 。Richardson 外推比较两个步长以估计或消除主项。非零条件与比值解释有关;若主系数为零,更高阶项可能主导。这是关于一整族计算的假设,并不是两个数值相近便能证明的事实。
定理/命题
定理 6.1.1
(中点与 Simpson 的光滑性误差界)
若 且 ,则
若 、 为偶数,且 ,则
中点公式的代数精度为一,Simpson 为三。凸函数满足 ;若四阶导数非负,则 。两个结论均可能取等号。
定理 6.1.2
(Gaussian 精度与正权重)
有 个相异根,全部在 。以这些根为节点, 表示第 个节点的 次 Lagrange 基底多项式。令 ,则公式对 准确。每个权重严格为正,权重和为二。任何只用 中 个实节点的公式,都不能对全部 准确。
若样本绝对误差各不超过 ,结果扰动不超过 。映到 后,界为 。
这些数据界针对扰动输入的精确加权和,不包括浮点求和或函数求值本身的算法误差。正权重在这个绝对数据模型中避免额外的抵消放大,但不能补救节点完全没有捕捉函数结构的问题。
实际还需决定是在一个区间上增加代数精度,还是把区间细分。前者改善当前区间的多项式准确性,后者把局部困难隔开,取得的是不同信息。函数求值可能很昂贵,所以成本常应按不同采样点的数目计算。复合公式必须按各子区间长度缩放权重,并按实际局部权重合并共享端点贡献,例如相邻梯形各自给公共端点一个半权重。这些不是附属记账,而是所实施的数学公式本身。
证明思路或证明
中点对称与 Simpson 核
证明
(Taylor 对称与正核)
在宽度为 、中心为 的小区间,Taylor 定理给出 ,其中 。奇函数的一次项在 上积分为零,余项上界积分为 。将 个界相加即得全局结论。凸性给出 ,再积分得到低估性质。
对 Simpson,先在 令 ,其中 。直接代入可见 消去 。从 展开的积分型 Taylor 定理将 函数写成三次多项式加上
作用 并交换有限和与积分,得 ,其中
当 ,采样的截断三次项只有端点一有贡献,故核为 ,化简即上式。负半轴可直接计算或利用 的对称。于是 。将区间映到 ,积分贡献一次缩放,四阶导数贡献四次,共为 。相加 个双小区间,得到 。核非负也证明误差符号。分别代入 和 ,说明两种公式的代数精度不能再提高。
正交如何加倍代数精度
证明
(数根与多项式除法)
设 在 中改变符号的根为 。若 ,取 ;没有这种根时取一。乘积 在区间中不再改变符号,并在某个小区间非零,所以其积分不可能为零。但 ,正交性要求积分为零,矛盾。因此至少有 个变号根。次数恰为 ,故所有根都是相异的内部单根。
对 做多项式除法,写成 ,其中 。正交性使第一项积分为零,节点处 又使其求积为零;插值权重准确积分 ,所以整个公式准确。再对次数为 的 使用准确性,得到
常数函数的准确性给出权重和。最后,节点乘积的平方是次数 的非负多项式,积分严格正,但所有节点值为零。因此任何这些节点上的公式都不可能准确积分它。最优代数精度并不等于对每个非多项式函数都最优。
证明透视
正内积的两次使用
证明的关键是一次除法。写成 ,就把 上的准确性化为 上的准确性;对任何 个相异节点,插值权重都能提供后者。剩下的 被处理两次:因 ,正交性使其积分为零;因节点是 的根,其求积也为零。节点的选取只在这里起作用。
内积的正性也用了两次。在数根时,符号不变的非零多项式 的积分必须非零。在 中,准确性被用于次数 的多项式,所以权重为正是额外精度的推论,而不是另外的计算。最优性一步以单一测试多项式 (次数 )结束论证;它对任何 个节点都成立,不论是否为 Gaussian 节点。
自适应估计究竟假设什么
在给定渐近模型下,
所以细网格的主误差估计及外推值为
的主项抵消后只有 ;要断言明确的更高阶,需要更强的展开及受控余项。Simpson 取 ,分母便是十五。自适应 Simpson 比较父区间与两个子区间,估计足够小时接受细结果或修正值,否则继续细分。把父容差分配给子区间,可以保证有效局部上界之和不超总预算,却不能把启发式估计变成严格上界。
实际停止还要处理最大深度、函数求值失败、浮点节点已无法区分,以及容差低于输入或算术误差下限。遇到这些情况应如实报告,不能把未达目标写成成功。重用共享端点和中点可以节省求值并保持一致。当积分接近零时,还需绝对容差;单纯相对容差可能没有可用意义。
例题详解
例题 6.1.3
(四次函数上的两种公式)
在 积分 ,真值为 。两个小区间的中点公式为 ,是低估。Simpson 为 ,高估 。由于 、,定理上界也是 ,恰好达到。
例题 6.1.4
(推导二节点 Gaussian 公式)
正交性给出 ,节点为 。对称及常数矩条件给出两个权重均为一,故 对三次多项式准确。但对 ,它给出 ,真积分为 。固定样本数的最优代数精度仍然有限,不能解释为对所有光滑函数准确。
节点是一个对称三对角矩阵的特征值,权则由其特征向量给出。
自然的下一个问题
m 很大时如何计算节点?
节点是一个对称三对角矩阵的特征值,权则由其特征向量给出。
首一多项式满足 ,其中 。因此 的根正是 对称三对角矩阵的特征值;该矩阵对角线为零,次对角元为 。若 是对应 的单位特征向量,则 。当 时,这给出 及两个等于一的权。
例题 6.1.5
(外推消去已知主项)
对于 的 ,复合 Simpson 的误差恰为 。于是 、,差的绝对值是 。细结果的估计为 ,恰等于真实误差;修正值 。这里恰好准确,是因为该多项式没有后续 Simpson 误差项。
常见错误
反例模式
粗细结果相同不代表没有误差
在 令 。它非负,在有限个零点之间严格为正,所以积分严格正。父 Simpson 区间采样 ,两个子区间另外采样 。函数在这五点全部为零。因此粗细结果及误差估计都为零。函数非常光滑也不能排除这种失败;认证仍需定量导数界或其他经过验证的函数类别约束。
误差阶描述一个极限过程,不能保证最初的粗网格已进入渐近区间。间断、端点奇异、快速振荡和不准确函数值都可能破坏模型。Gaussian 节点在内部,不会自动解决端点行为。细分增加成本,也不一定减少数据不确定性。报告必须说明目标是由证明上界、模型估计,还是仅由迭代上限结束。
概念视角结构
代数精度也是信息预算
选择 个 Gaussian 节点及权重,使矩条件可以满足到 次。节点乘积的平方证明下一次已经出现不可避免的盲点。自适应方法在比较提示困难之处取得新样本,但没有额外函数约束,有限确定性采样无法排除所有隐藏峰值。
常见错误
(只映射节点而忘记权重)
在 上,Gaussian 节点为 ,权重为 。只缩放节点是常见的疏忽。对 ,映射后的二节点公式节点为 , 在两点的值之和为 。用正确权重 ,公式恰好给出 ;用未缩放的权重 ,则给出 。
常见错误
(把 Simpson 的分母用于其他阶的公式)
分母 取决于被加密公式的阶 。梯形法的 。在 上取 ,有 、,细结果误差为 。正确估计 与之相符;除以十五则得 ,小了五倍。
总结
中点对称给出二阶全局界,Simpson 的正四阶导数核给出四阶及误差符号。正交多项式根产生正 Gaussian 权重与最优代数精度。Richardson 比较依赖可辩护的渐近模型;自适应能分配计算量及容差,但停止报告必须区分估计和保证。
练习
快速检查
(对 上的 ,求 和误差。在中点定理中代入 ,求保证误差不超过 的最小 。)
单一小区间的中点法只取样 。
解答 · 答案
,低估 。全局界为 ,这个二次函数恰达到该界。要求 ,所以最小整数为 。记号 表示导数上界,而不是两个小区间的中点近似。
快速检查
(把二节点 Gaussian 公式映到 ,列出节点及权重,积分 。若每个函数值误差至多 ,结果不确定性多大?)
仿射映射 的比例因子为一。
解答 · 答案
节点为 ,仿射比例为一,所以权重仍均为一。两个节点的立方和是 ,等于真实积分。绝对权重和为二,故数据界为 ,同号误差达到此界。
快速检查
(设精确模型 。取 ,求粗细结果误差、细结果的 Richardson 估计,以及修正误差。)
取 ,故分母为 。
解答 · 答案
粗误差为 ,细误差为 ,差的绝对值为 。除以 得 ,恰好是细误差。修正值 的误差为零,因为模型只有一个误差项。若有未指定的高阶项,一般仍会留下余项。
快速检查
(两个子区间的误差数字为 、,总绝对目标为 。若它们是已证明的上界,可作何结论?若只是 Simpson 差值除十五,结论如何改变?)
区分已证明的上界与模型估计。
解答 · 答案
若两个数字是有效局部上界,且两个区间覆盖积分域,三角不等式给出总求积误差不超过 ,另外排除的输入和算术误差仍需另计。若只是模型估计,只能作条件性的准确度说明;隐藏多项式反例表明它们未必控制实际误差,应报告估计收敛而非严格认证。