为什么从最大到最小浮点数相加不如从最小到最大相加准确?

  • 本文关键字:浮点数 java floating-point rounding-error
  • 更新时间 :
  • 英文 :


我的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 矢量化,通过将中间和存储在矢量中,这可以提高速度和准确性。

最新更新