我的Java教科书指出,在处理浮点数时,从最大到最小相加不如从最小到最大相加准确。但是,他没有继续清楚地解释为什么会这样。
浮点数的精度有限(6 表示float
,15 表示double
)。 计算
1.0e20d + 1
给出结果1.0e20
因为没有足够的精度来表示数字
100,000,000,000,000,000,001
如果从最大数字开始,则任何小于n
数量级以上的数字(其中n
根据类型为 6 或 15)将根本不计入总和。 从最小的数字开始,您可以将几个较小的数字相加为一个,这将影响最终的总数。
例如,它会有所作为的地方
1.0e20 + 1.0e4 + 6.0e4 + 3.0e4
假设它的精度正好是 15 位十进制数字(事实并非如此,请参阅下面的链接文章,但 15 对于示例来说已经足够了),如果您从较大的数字开始,其他数字都不会产生影响,因为它们太小了。 如果从较小的开始,它们加起来为 1.0e5,这足以影响最终的总数。
请阅读每个计算机科学家都应该知道的关于浮点运算的知识
Nick Higham的"数值算法的准确性和稳定性"的第4.2节中有一个很好的解释。以下是我对此的随意解释:
浮点的关键属性是,当单个运算的结果无法精确表示时,将其舍入到最接近的值。这会产生许多后果,即加法(和乘法)不再是关联的。
另一个需要注意的主要事项是误差(真实值和舍入值之间的差异)是相对的。如果我们使用方括号 ([]
) 来表示此舍入运算,那么我们x
任何数字都有属性:
|[x] - x| <= ϵ |[x]| / 2
ε是机器epsilon。
所以假设我们想总结[x1, x2, x3, x4]
.显而易见的方法是通过
s2 = x1 + x2
s3 = s2 + x3 = x1 + x2 + x3
s4 = s3 + x4 = x1 + x2 + x3 + x4
如上所述,我们无法完全做到这一点,所以我们实际上正在做:
t2 = [x1 + x2]
t3 = [t2 + x3] = [[x1 + x2] + x3]
t4 = [t3 + x4] = [[[x1 + x2] + x3] +x4]
那么由此产生的误差有多大|t4 - s4|
?我们知道
|t2 - s2| = |[x1+x2] - (x1+x2)| <= ϵ/2 |t2|
现在通过三角形不等式我们可以写
|t3 - s3| = |[t2+x3] - (t2+x3) + (t2+x3) - (s2+x3)|
<= |[t2+x3] - (t2+x3)| + |t2 - s2|
<= ϵ/2 (|t3| + |t2|)
再说一遍:
|t4 - s4| = |[t3+x4] - (t3+x4) + (t3+x4) - (s3+x4)|
<= |[t3+x4] - (t3+x4)| + |t3 - s3|
<= ϵ/2 (|t4| + |t3| + |t2|)
这导致了Higham的一般建议:
在设计或选择求和方法以实现高精度时,目标应该是最小化中间和
ti
的绝对值。
因此,如果你正在做顺序求和(就像我们上面所做的那样),那么你想要从最小的元素开始,因为这会给你最小的中间和。
但这不是唯一的选择!还有成对求和,您将对以树的形式相加(例如[[x1 + x2] + [x3 + x4]]
),尽管这需要分配工作数组。您还可以利用 SIMD 矢量化,通过将中间和存储在矢量中,这可以提高速度和准确性。