c++ - 计算平均值的最佳数值方法是什么

Question

计算平均值的最佳方法是什么？有了这个问题，我想知道哪种计算平均值的算法在数字意义上是最好的。它应该具有最小的舍入误差，不应该对上溢或下溢等敏感。

谢谢你。

---

附加信息：首选增量方法，因为值的数量可能不适合 RAM（对大于 4 GB 的文件进行多次并行计算）。

Answer 1

如果您想要 O(N) 算法，请查看Kahan summation。

Answer 2

您可以查看http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3535（Nick Higham，“浮点求和的准确性”，SIAM Journal of Scientific Computation，1993） .

如果我没记错的话，如果所有数字都是正数，补偿求和（Kahan 求和）就很好，至少与对它们进行排序并按升序添加它们一样好（除非有非常多的数字）。如果一些数字是正数而一些数字是负数，那么这个故事就会复杂得多，这样你就会被取消。在这种情况下，有一个参数可以按降序添加它们。

Answer 3

我总是使用以下伪代码：

float mean=0.0; // could use doulbe
int n=0;  // could use long

for each x in data:
    ++n;
    mean+=(x-mean)/n;

我没有其稳定性的正式证明，但您可以看到，假设数据值表现良好，我们不会遇到数值溢出问题。在 Knuth 的《计算机编程的艺术》中提到了它

Answer 4

按数量级升序对数字进行排序。将它们相加，首先是低震级。除以计数。

Answer 5

只是为了进一步讨论添加一个可能的答案：

逐步计算每个步骤的平均值：

AVG_n = AVG_(n-1) * (n-1)/n + VALUE_n / n

或成对组合

AVG_(n_a + n_b) = (n_a * AVG_a + n_b * AVG_b) / (n_a + n_b)

（我希望公式足够清楚）

Answer 6

一篇很晚的帖子，但由于我没有足够的声誉来发表评论，@Dave 的方法是Gnu 科学图书馆使用的方法（截至 2020 年 12 月） 。

这是从 mean_source.c 中提取的代码：

double FUNCTION (gsl_stats, mean) (const BASE data[], const size_t stride, const size_t size)
{
/* Compute the arithmetic mean of a dataset using the recurrence relation mean_(n) = mean(n-1) + (data[n] - mean(n-1))/(n+1)   */

long double mean = 0;
size_t i;

for (i = 0; i < size; i++)
{
  mean += (data[i * stride] - mean) / (i + 1);
}

return mean;
}

GSL 使用相同的算法来计算方差，毕竟这只是给定数字的平方差的平均值。