定义明确的和也可能难以精确计算
对一长串数求和看起来比解方程组简单,但每一次加法都会产生舍入。此外,抵消现象可能使结果对输入的扰动高度敏感。这是两个不同的问题:一个涉及数学上的和,另一个涉及用于计算它的算法。
对于实数 ,记 。
定义 1.2.1
(和的条件数)
当 时,对分量相对扰动 , 的相对条件数定义为
若 ,则非零的绝对扰动相对于 没有有限的相对误差,因此 没有定义。
命题 1.2.2
(和对分量扰动的敏感性)
若对每个 都有 ,且 ,则
对于实数输入,这个界是紧的。
证明
(三角不等式与同向扰动)
由 及三角不等式,得 ;再除以 即得相对形式。取 ,所有扰动便沿同一方向叠加,,等号成立。
标准模型下的顺序加法
定义 1.2.3
(舍入模型与常数 )
假设计算中每一次浮点加法都满足
其中 是单位舍入误差的上界。该相对模型要求运算保持在其有效范围内;上溢、下溢和异常值需要另行处理。对 ,定义
设 是对已表示的输入依次相加所得的结果,即 、,并假设 。
定理 1.2.4
(顺序求和的误差界)
对于 ,
该模型适用于已表示的输入;表示原始数据时引入的误差必须另行计入。
证明
(展开递推式)
对 ,写 ,其中 。逐步展开得
每个乘积有 个因子。由于 ,每个乘积与 之差至多为 。对指数 使用 Bernoulli 不等式,得 ;故当 时 ,从而 。又 随 递增,所以每个乘积与 之差至多为 。因此
证明透视
每个假设用在哪里
假设 只用一次,用来保证 Bernoulli 步骤中的 为正。范围假设则每次加法都要用,因为每次加法都有各自的因子 。关键一步,是把舍入因子的乘积换成与各 符号无关的单一上界 。由于这个界分别附在每个 上,证明最后得到的是 ,而不是 。
若 ,两边除以 得
因此,当求和问题病态时,即使很小的后向扰动也可能产生很大的相对前向误差。反之,较大的条件数只是最坏情形下的警告,并不意味着每一种顺序或每一次舍入实现都会产生很大的误差。因子 来自算术模型以及舍入步骤的数目;因子 来自输入值及其抵消。改进求和算法可以减小前一个因子;但它无法改变底层求和对不确定数据的敏感性。
快速检查
(计算 的 。)
解答 · 答案
和为 ,各项绝对值之和为 ,所以 。
快速检查
(对于和非零的正输入, 是多少?)
解答 · 答案
为 ,因为所有 都为正时 。
顺序与示例
例题 1.2.5
(抵消与加法顺序)
的精确和为 。在 的算术中,从左到右求和返回零;而先将 与 相加、再加上 ,则返回一,这里假设这些运算都可精确表示。具体的顺序依赖行为取决于浮点格式和舍入模式。此处 ,这正是顺序可能有影响的警告。
例题 1.2.6
(达到敏感性界的扰动)
取 ,则 、、。取 及 ,扰动后的和为 ,故 ,且 。等号成立,所以对这组输入,比 更小的常数都不可行。
例题 1.2.7
(无抵消的情形,以及精确和为零)
若所有输入均非负且至少有一个为正,则 。对 ,相对误差界即为 ,不过实际舍入后的结果仍可能依赖于顺序。成对求和构成一棵平衡树,常常能把一条路径上的加法次数从 减少到约 ;相应的证明必须考虑实际的树结构和舍入模型。
边界情形是 :此时 , 没有定义。然而 恰好成立,所以绝对误差界 绰绰有余。绝对误差界仍然有意义,失去的只是相对误差的陈述。
反例模式
很小的相对输入扰动可能导致答案中的很大误差
命题:若输入的相对精度为 ,则其和的相对精度也接近 。考虑 与 。它们的和为 ,而各项绝对值之和约为 。因此 约为 。只把 扰动相对量 :,则和变为 ,相对改变为 。对不确定的输入数据进行精确算术,也无法恢复这些数据本身所不能确定的数位。只有在 不大时,上述命题才成立。
常见错误
(补偿求和不能修复不确定的数据)
补偿求和会追踪先前步骤中损失的部分舍入误差,可以提高精度,但上面证明的界针对的是普通顺序加法。它不能证明某个特定补偿算法的误差界,也不会消去因子 :若输入本身不确定,任何累加顺序都无法补回缺失的数位。
练习与解答
快速检查
(在所述模型下,给出对四个已表示的值求和的绝对误差界。)
解答 · 答案
该界为 ,假设 。
快速检查
(为什么当精确和为零时,相对条件数没有定义?)
解答 · 答案
其分母为 ;绝对误差界仍然有意义,但除以零无法定义相对误差。