Каков наилучший способ вычисления среднего

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

Спасибо.


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

Ответы

Ответ 1

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

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

Ответ 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)

(Я надеюсь, что формулы достаточно ясны)

Ответ 4

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

Ответ 5

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

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

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

У меня нет формальных доказательств его устойчивости, но вы можете видеть, что у нас не будет проблем с численным переполнением, если предположить, что значения данных хорошо себя ведут. Он упоминается в Knuth Art of Computer Programming