直观上为什么成对求和比朴素求和误差更小

Question

在 numpy sum 文档中 https://numpy.org/doc/stable/reference/ generated/numpy.sum.html

它提到，它使用成对求和来代替朴素求和以获得更好的错误率

我很困惑为什么成对求和更能减少误差

天真的总结

在朴素求和中，数字按顺序相加，平均误差为 O(sqrt(N))，最坏情况为 O(N)

sum=(((x1+x2)+x3)+…+xn)

成对求和的平均误差为 O(log(sqrt(N)))，最坏情况为 O(logN)

来自谷歌，pairwise 通过将数字列表分成对，对每对求和，然后递归地对结果求和，改进了朴素求和。流程如下：

1. 初始配对：从原始号码列表开始。

   {x1,x2,x3,x4,…,xn}

   {x1,x2,x3,x4,…,xn}

2. 对求和：对数字进行求和。

   {(x1+x2),(x3+x4),…} {(x1+x2),(x3+x4),…}

3. 递归求和：对上一步的和重复该过程，直到剩下一个和。 {((x1+x2)+(x3+x4)),…} {((x1+x2)+(x3+x4)),…}

有人可以解释一下改进在哪里的直觉吗？

例如

让我们使用下面的数字，假设尾数是3

1.01x10^10 + 1.01x10-10 + 1.01x10^10 + 1.01x10-10

天真的加法

(((1.01x10^10 + 1.01x10-10) + 1.01x10^10) + 1.01x10-10)
(((1.01x10^10 + 1.01x10^10) + 1.01x10-10)
(((2.02x10^10 + 1.01x10-10)
2.02x10^10

两两求和

(1.01x10^10 + 1.01x10-10) + (1.01x10^10 + 1.01x10-10)
1.01x10^10  + 1.01x10^10 
2.02x10^10

两者都会导致

2.02x10^10

Answer 1

成对求和并不比“朴素”求和更准确，这取决于级数。令 T_i 为第 i 次加法的结果，u 为机器精度。那么误差范围是

u (|T_1| + ... + |T_(n - 1)|)

。

所以对于幼稚的总结，

T_1 = x_1 + x_2
T_2 = T_1 + x_3
T_3 = T_2 + x_4

对于两两求和

T_1 = x_1 + x_2
T_2 = x_3 + x_4
T_3 = T_1 + T_2

背景

让我们首先看看应该如何量化错误。 假设一个苹果重 250 克，但我们测量为 249 克。如果我们取差值，我们会得到 1 的误差。这称为 绝对误差 如果我们进行相同的测量，但以千克为单位写下结果，则误差为 0.001。

解决此问题的方法是除以结果：(250 - 249) / 250 = 0.004，(0.25 - 0.249) / 0.25 = 0.004。这称为“相对误差”。等价地，249 = 250 * (1 - 0.004)，因此如果近似值 x' 等于 x(1 + delta)，我们称 |delta|是相对误差。 我们将 fl(x + y) 写为真实和 x + y 的浮点近似值。对于 32 位实数，我们有 fl(x + y) = (x + y)(1 + delta) 来表示 delta

直觉< 2^(-24) and for 64-bit reals the delta is at most 2^(-53).

浮点加法相对于结果来说是准确的。因此，我们累积的误差与部分总和成正比。部分和越小，误差越小。