即使每个输入都能精确表示,长串求和仍可能丢失小增量。前一单元区分了舍入误差和总和本身的敏感度;这里研究一种记住部分加法舍入影响、并在下一步加以补偿的算法。
带符号的修正
定义 1.4.1
(补偿求和(Kahan 求和))
对已表示的输入 ,令 、,每步按所示次序计算:
返回 。计算 时用的是旧的 。
精确算术下 ,修正项为零。有舍入时, 估计实际吸收的增量,因此 估计所吸收增量超出原定增量多少;下一步减去这个超额。上述每个运算都分别舍入,估计值一般并非精确误差。
常见错误
(把修正项化简为零)
若将表达式 按代数规则化简为零,就会破坏这个计算,因为这种代数式只在精确算术中成立。实现,以及会重排浮点运算的编译器,都必须保持指定的求值次序。
命题 1.4.2
(精确算术下修正项为零)
若每个运算都精确进行,则每步之后 ,并且第 步之后 。
证明
(对步数归纳)
设第 步之前 、。则 ,,,所以新的 是 ,且 。第一步之前 ,命题成立。
证明透视
修正的是什么?
仅为理解符号,设想 和 精确,而唯一的误差来自舍入后的加法 。若 ,则 ,下一个输入便用 修正。实际算法的两次减法也会舍入:这个推理解释了符号,但不能证明所有误差都被消除,也不是误差界。
小型十进制机器中的十个增量
例题 1.4.3
(在 1000 上加十个 1)
使用三位有效数字的十进制算术,每次运算舍入到最接近的数,平局取偶;假设指数范围足够。 的所有输入都可精确表示,精确和为 。处理 后,普通和与补偿和均为 ,且 。在这个量级上, 上方相邻的可表示数相距十。
| 已处理的 1 的个数 | 普通和 | 补偿和 | 修正项 |
|---|---|---|---|
| 1 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 10 |
第五个 1 时, 恰在正中间,平局取偶选 ;第六次 , 舍入为 ,修正项是 。其后四个输入使 减到零。普通和丢掉了每一个 1;这次补偿结果恰好精确。格式、舍入规则或次序改变,过程也可能不同。
例题 1.4.4
(两个 4 的增量)
在同一机器中处理 ,精确和为 。普通求和得 ,再加一次仍是 :结果为 ,与精确和相差 。补偿方法在处理 后 。第一个 给出 、、。第二个给出 、、,所以 ,与精确和只差 。在这两条运算记录的每一行中, 都等于精确的部分和(例如 ,)。这个恒等式只是对这些记录的观察,在 及 中的减法都精确时成立;下面的反例显示它在哪里失效。
例题 1.4.5
(没有任何舍入的情形)
在同一机器处理 。每个中间量都至多有三位有效数字:;然后 ;再然后 。返回的和是 ,修正项始终为零,方法与普通求和一致,正如关于精确算术的命题所预言的那样。
反例模式
补偿并非精确累加器
在同一十进制机器处理 。前两项之后 ;第三项有 ,故返回 ,但已表示输入的精确和是 。修正项与大得多的输入结合时,本身也可能被舍入掉。
方法的作用与局限
每个输入只需常数次算术运算和常数个存储单元,所以运算量为 ,工作空间为 ,不计输入的存储。此算法可大幅改善求和,但上面的例子并不是普遍的误差界。
常见错误
(以为补偿可以消除病态性)
相消可能使精确和对数据扰动敏感;补偿不能恢复已表示输入中不存在的数位。它改善的是算术,而不是问题本身的条件性。
溢出、下溢、非有限数以及编译器重组运算需要另行分析。若应用需要经过认证的误差,须选择适合该实现的算术模型和误差分析。
习题
快速检查
(十个增量例子中处理第三个 1 后 是什么?)
依照表中最初几行的规律。
解答 · 答案
:第三步有 、、。
快速检查
(第六次修正项为何是正的?)
比较被吸收的增量与原定增量。
解答 · 答案
舍入步骤吸收 ,而调整后原定增量是 ,多出 。
快速检查
(十个增量例子中处理第七个 1 后 是什么?)
从第六个之后的 开始。
解答 · 答案
,,。所以 。
快速检查
(最后的反例是否证明所有补偿和都会失败?)
数一数它用了多少个输入、什么算术。
解答 · 答案
否;它只显示指定算术与次序下的一次失败,并不是典型或普遍行为的证明。