成对求和

在数值分析中，成对求和也叫级联求和，是一种对有限精度浮点数序列进行求和的技术，与天真地依次累加求和相比，可以大 大减少累积的舍弃误差。

虽然还有其他技术，如Kahan求和，通常有更小的舍入误差，但成对求和几乎同样好（只相差一个对数因子），同时计算成本更低–可以实现与天真求和几乎相同的成本（以及完全相同的算术操作数）。

特别是，n个数字序列xn的成对求和是通过递归地将序列分成两半，对每一半求和，然后将两个和相加来实现的：一个除法和征服算法。其最坏情况下的舍入误差最多渐进式增长为O(εlogn)，其中ε是机器精度（假设有固定的条件数，如下文所述）。

相比之下，依次累加总和的天真技术（在i=1,…,n的情况下一次加入每个xi）的舍入误差最多增长到O(εn)。Kahan求和的最坏情况下的误差大约为O(ε)，与n无关，但需要多几倍的算术运算。

如果舍入误差是随机的，特别是有随机符号，那么它们就会形成随机漫步，误差增长就会减少到平均为在许多快速傅里叶变换（FFT）算法中发现了非常类似的递归求和结构，并对这些FFT的缓慢舍入累积负责。

在伪代码中，长度为n≥0的数组x的成对求和算法可以这样写。s=pairwise(x[1…n])ifn≤N基本情况：对一个足够小的数组进行天真的求和s=0fori=1tons=s+x[i]else分割和征服：递归求和数组的两半m=floor(n/2)s=pairwise(x[1…m])+pairwise(x[m+1…n])endif对于一些足够小的N，这个算法切换到一个天真的基于循环的求和，作为一个基础案例，其误差边界为O(Nε)。

在给定的条件数下，整个求和的最坏情况下的误差在大的n下渐进式增长为O(εlogn)。在这种算法中（就像一般的除法和征服算法一样），最 好使用较大的基数，以便摊销递归的开销。

如果N=1，那么每一个输入都有一个递归子程序调用，但更普遍的是，如果递归正好在n=N时停止，那么每N/2个输入就有一个递归调用。不管N是多少，总共要进行n-1次加法，与天真求和相同，所以如果递归开销可以忽略不计，那么成对求和的计算成本与天真求和基本相同。

这个想法的一个变种是在每个递归阶段将求和分成b个块，对每个块进行递归求和，然后再对结果进行求和，这被其提出者称为超级块算法。上述成对算法对应于每个阶段的b=2，除了最后阶段是b=N。

假设人们要对n个值xi进行求和，i=1，…，n。其中ε是所采用的算术的机器精度（例如，ε≈10-16为标准双精度浮点）。通常情况下，感兴趣的数量是相对误差在相对误差边界的表达中，分数(Σ|xi|/|Σxi|)是求和问题的条件数。

从本质上讲，条件数代表了求和问题对错误的内在敏感性，无论它是如何计算的。每个（反向稳定的）求和方法的相对误差边界由一个固定的算法来决定。