动机
数值方法经常包含两种竞争机制。减小步长可改善数学近似,却可能放大输入误差;增加运算可消去截断主项,却同时引入更多舍入。因此,准确性陈述需要一个统一的误差预算,各项都针对同一个最终量,并明确说明各自假设。
本节先从中心差分构造四阶公式,证明其误差常数,再研究组合样本时的算术。求和说明一个关键现象:算法可以后向稳定,但若真实和接近抵消,其相对前向误差仍可能很大。成对求和与补偿求和改善问题的不同部分。
定义
定义 8.1.1
(Richardson 外推的中心差分)
假设所需位置都可采样,定义
展开即得五点公式
中心点系数为零,所以只需四次偏离中心的函数求值。“五点”指包括中心的等距模板。Richardson 外推利用已知的步长幂消去主误差项,不是简单平均两个答案。
定义 8.1.2
(浮点舍入模型)
算术部分假设采用最近舍入,单位舍入误差为 ,并且讨论中的每次运算满足
定理排除溢出及不适用正常相对误差模型的运算。若 ,记 。
定义 8.1.3
(求和条件数)
对精确输入 ,令 。当 ,分量相对扰动下的求和条件数为
即使每次加法舍入很小,这个数仍可能很大。真实和为零时,除以 的相对误差没有定义;绝对误差依然有意义。
定理/命题
定理 8.1.4
(四阶微分及独立的数据界)
设 、,且该区间 。则
若四个函数输入值各有绝对误差至多 ,对这些输入精确计算公式,则
当 ,这个上界在所有正步长中于 取最小值,前提是该步长下的采样域及导数假设有效。
定理 8.1.5
(舍入模型下求和的后向稳定性)
顺序求和 个数,共使用 次舍入加法。若 ,结果可写为
因此 ;当 ,相对前向误差至多 。若使用最大深度 的平衡成对树,在相同模型及 下,绝对界改为 。
后向陈述表示答案是轻微扰动输入的精确和,不表示原问题的相对误差一定小。条件数正是连接两个陈述所缺的信息。
概念视角结构
统一分配误差预算
外推消去近似主项;成对求和缩短舍入因子链;补偿把丢失的低位传给后续计算;条件性描述输入中已有的误差如何影响目标。这些机制发生在不同阶段,合理组合需要把各自贡献写入同一个最终绝对或相对误差陈述。
证明思路或证明
消去微分误差主项
连续五阶导数的 Taylor 展开给出
换成 可见 消去二阶项,因此 。这识别了渐近主系数,但尚未证明定理中对整个余项的上界。
证明
(五点公式的 Peano 核误差界)
先缩放到 ,令 。直接代入发现它消去所有次数不超过四的多项式。以 为基点的积分 Taylor 公式,把 函数写成四次多项式加上 的积分。作用 后得到
核为偶函数,其非负半轴表达式是
对非负 ,截断幂在零点的导数贡献为零,代入两个正采样点便得上式;负半轴直接代入给出相同数值。在 ,,故分子非正;另一段显然非正。积分为
于是 。令 ,则 ,五阶导数提供 因子,除以 即得界。样本误差的绝对权重和为 ,故再加独立数据项。对合并上界关于 求导,得到所述极小点。它优化的是这个模型的上界,不是所有机器计算的普遍最佳步长。
证明透视
单一符号的核为何给出最佳常数
证明靠两个想法。公式对次数不超过四的多项式精确,使 Peano 表示可以丢掉整个 Taylor 多项式,于是 只取决于 。其次,核从不改变符号,这把粗略估计 变成 ,而这个数可用任何一个五次式算出:对 ,,同时 。由于 ,只要 为常数便取到等号,所以 不能再改进,而正的五阶导数必然给出负误差。假设 的用处在于核支撑于 ;偶性只是把计算减半。缩放时 带来 , 带走一个 ,剩下 。
展开舍入因子
证明
(展开舍入因子)
记 、。逐次代入后,每个输入都乘上至多 个 因子。包含 个因子的乘积偏离一至多 :其最大值不超过 ,最小值不少于 ,并且
第一个不等式可在 下归纳,第二个是 Bernoulli 不等式。因此每个输入都对应一个有界乘法扰动,取绝对值给出前向界,再除真实和的绝对值便出现条件数。成对树中的每个叶子最多通过 次加法,相同论证把 换成 。整个证明不需要随机舍入假设。
成对界改善的是最坏深度依赖,不能保证每组数据都比所有顺序次序严格准确。全正输入的条件数为一,接近抵消的和在两种算法下都可能敏感。输入本身也必须已按预期表示;外部十进制数据转换造成的扰动需另计。
补偿究竟记录什么
一种常用补偿方法保存和 与修正量 ,初始均为零。对每个输入 ,依顺序执行
修正量估计最近加法丢失的低位,并从下一输入减去它。运算顺序和每次舍入很关键;若把 的代数式简化成零,便破坏了算法。补偿经常显著改善累加,但这里的解释不是“总能返回精确和的正确舍入”的证明。更强误差界需要针对具体实现及舍入假设的独立分析,不能把顺序求和的定理直接附到不同递推上。
误差预算还说明更多测量能做到什么。仪器固定的绝对不确定性,不会因为采样距离缩短便自动减小。重复测量在合理统计模型下可能改善估计,但确定性绝对界不能仅凭样本数量增加而缩小。上面的优化把两个常数视为固定;若它们随步长改变,必须重新分析。
显示很多小数位也不证明每一位准确。接近零的导数或抵消的和,经过验证的绝对区间通常比相对误差更清楚。相对误差适合尺度差异大的非零结果。报告应同时说明量、范数、假设和界,读者才能判断哪些数字及后续决定有依据。
例题详解
例题 8.1.6
(达到微分常数的五次函数)
在零点取 ,五点分子为 ,故 ,真导数为零。由于五阶导数为 ,误差恰为 。外推 等于间距 的同一模板,所以误差为 。更小截断误差伴随更近采样及更大的数据不确定性权重。
例题 8.1.7
(小型二进制系统中的补偿)
使用三位有效二进制数字、最近舍入且中点取偶。求一加四个 。在一附近间距为 ,普通顺序加法每次遇到中点又回到一,因此返回一,真值却为 。补偿递推在各个小输入后依次得到 、、、。修正保留了足够的低位,在本例恢复精确和。
例题 8.1.8
(后向稳定遇上敏感的和)
输入 的真和为一,条件数为 。顺序定理给出相对误差界 。若模型中 ,该界约为四,尽管每次加法的相对舍入都很小。这不是某具体十进制或二进制格式的输出断言,而是说明抵消问题中的后向稳定只能提供较弱的相对保证。
常见错误
反例模式
补偿不是普遍精确求和算法
在标准 binary64 最近舍入、中点取偶下,上述补偿递推处理 会返回零,实数精确和却为一。加入一后修正量为 ,但形成下一个修正输入时, 又舍入回 ,保存的一在此丢失。因此成功的小例子不能支持无条件准确性声明。
常见错误
(对高阶公式取尽量小的步长)
四阶不表示步长越小越好。截断项按 减小,数据项却按 增长,而且浮点坐标 最终可能等于 。微分定理及其数据项没有包含形成坐标、求函数值、加权求和和相除的完整硬件分析。
常见错误
(把后向稳定理解为相对误差小)
后向误差小也不能克服病态问题:对接近抵消的和,相对前向界是 ,而 可以极大。误差报告应明确模型、最终量,以及哪些误差已被计入。
总结
Richardson 消去二阶项产生四阶模板,其单符号核给出具有可达常数的导数界。样本误差另加反比步长项。正常舍入模型下顺序求和分量后向稳定,但抵消可放大相对前向误差。成对树改善深度依赖,补偿保留低位,却需独立分析,不能普遍保证精确和。
练习
快速检查
(在零点将 应用于 和 ,解释前者准确及后者的误差符号。)
利用分子 。
解答 · 答案
三次函数的分子为 ,与真导数一致;公式重现所有四次以内多项式的导数。五次函数的结果为 。五阶导数正、核非正,故有符号误差为负。
快速检查
(设 ,每个函数样本的绝对不确定性为 。写合并上界,求最优正步长,并说明实际中该步长可能不适用的两个原因。)
把定理中的 与 相加。
解答 · 答案
上界为 。极小点满足 ,约 。采样点可能超出定义域,或者导数及数据界未覆盖整个采样区间。坐标舍入与求值误差也需独立预算。这个步长优化所写的界,而非未指定的全部硬件计算。
快速检查
(若 、,比较顺序及平衡树的 常数。若输入都非负且和为正,条件数是多少?)
有 个叶子的平衡树深度为 。
解答 · 答案
顺序深度为 ,常数为 。平衡深度为十,常数为 。非负输入且正和给出 。比较的是最坏界的常数,不是每个数据集的严格误差排名。
快速检查
(三个数的精确和为零,为什么相对前向误差没有定义?给出顺序求和的适当绝对界,并说明它是否要求计算结果为零。)
用后向稳定定理的绝对误差形式,取 。
解答 · 答案
绝对误差除以真实零和没有定义。若 ,定理给出 。这个区间可以包含非零计算答案。后向稳定允许各输入受到轻微分量扰动,而这些扰动不必保持原有的精确抵消关系。