Выгодно ли для точности вычислять инкрементное среднее / среднее значение?

Question

В вопросе «Какой численно лучший способ рассчитать среднее?» было предложено , что вычисление скользящего среднего, т.е.

mean =  a[n]/n + (n-1)/n * mean

может быть численно более стабильным, чем вычисление суммы с последующим делением на общее количество элементов. Это было задано под сомнение комментатором. Я не могу сказать, какая из них правда - может кто-то другой? Преимущество скользящего среднего состоит в том, что вы сохраняете среднее значение маленьким (т.е. примерно того же размера, что и все векторные записи). Интуитивно это должно уменьшить ошибку. Но комментатор утверждает:

Частично проблема заключается в том, что 1 / n вносит ошибки в наименее значимые биты, поэтому n / n! = 1, по крайней мере, когда это выполняется как трехэтапная операция. (делить-хранить-умножать). Это сводится к минимуму, если деление выполняется только один раз, но вы делаете это для ГБ данных.

Итак, у меня несколько вопросов:

1. Является ли скользящее среднее более точным, чем суммирование и последующее деление?
   • Зависит ли это от вопроса, вычисляется ли сначала 1 / n, а затем умножается?
   • Если да, то реализуют ли компьютеры одностадийное деление? (Я так и думал, но сейчас не уверен)
2. Если да, то это более точно, чем суммирование Кахана с последующим делением?
3. Если можно сравнить - какой из них быстрее ? В обоих случаях у нас есть дополнительные вычисления.
4. Если точнее, можете ли вы использовать это для точного суммирования?

Answer 1

1. Во многих случаях да. Рассмотрим последовательность всех положительных членов одного порядка величины. Их сложение дает большую промежуточную сумму, к которой мы добавляем небольшие члены, которые могут округляться точно до промежуточной суммы. Используя скользящую сумму, вы получаете условия того же порядка, и, кроме того, эту сумму намного сложнее переполнить. Однако это не является открытым и закрытым: добавление терминов и последующее деление позволяет нам использовать инструкции AVX, которые значительно быстрее, чем инструкции вычитания / деления / сложения скользящего l oop. Кроме того, существуют распределения, которые делают то или иное более точным. Это было исследовано в:

Robert F Ling. Сравнение нескольких алгоритмов вычисления выборочных средних и дисперсий. Журнал Американской статистической ассоциации, 69 (348): 859–866, 1974

Суммирование Кахана - ортогональная проблема. Вы можете применить суммирование Кахана к последовательности x[n] = (x[n-1]-mu)/n; это очень точно.