Какой численно лучший способ рассчитать среднее

Question

Как лучше всего рассчитать среднее?С помощью этого вопроса я хочу знать, какой алгоритм для вычисления среднего является лучшим в численном отношении.Он должен иметь наименьшее количество ошибок округления, не должен быть чувствительным к чрезмерному или недостаточному переполнению и т. Д.

Спасибо.

---

Дополнительная информация: предпочтительнее добавочные подходы, поскольку число значенийможет не помещаться в ОЗУ (несколько параллельных вычислений для файлов размером более 4 ГБ).

Answer 1

Если вам нужен алгоритм O (N), посмотрите на Суммирование Кахана .

Answer 2

Вы можете взглянуть на http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3535 (Ник Хайэм, «Точность суммирования с плавающей точкой», SIAM Journal of Scientific Computing, 1993).

Если я правильно помню, скомпенсированное суммирование (суммирование по Кахану) хорошо, если все числа положительны, и не менее, чем сортировка их и добавление их в порядке возрастания (если только не очень много чисел).История намного сложнее, если некоторые числа положительные, а некоторые отрицательные, так что вы получите отмену.В этом случае есть аргумент для добавления их в порядке убывания.

Answer 3

Просто добавьте один возможный ответ для дальнейшего обсуждения:

Постепенно рассчитайте среднее значение для каждого шага:

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 4

Сортировка чисел в порядке возрастания.Суммируйте их сначала по малой величине.Разделите на количество.

Answer 5

Я всегда использую следующий псевдокод:

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

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

У меня нет формальных доказательств его стабильности, но вы можете видеть, что у нас не будет проблем с числовым переполнением, если предположить, что значения данныххорошо себя ведетЭто упоминается в Кнуте Искусство компьютерного программирования