Как рассчитать среднеквадратичное отклонение, если среднее значение неизвестно?

Question

[Йцу Йцуевич]

Пусть есть некоторый очень, очень большой файл, где в каждой строке числа, для простоты - целые.
Рассчитать среднее значения через формулу сумма/кол-во нельзя, т.к. файл огромен, в оперативку сумма не поместится (просто смеритесь с этим!). Поэтому я придумал форму (наверняка не я первый):
((i-1) * avg + nextValue) / i где
i - это текущее кол-во рассчитанных чисел (текущий шаг начиная с 1);
avg - текущее среднее значение;
nextValue - следующее значение (из файла).

Например:
3
3
6
читаем построчно
для 3: (0 * 0 + 3) / 1 = 3
для 3: (1 * 3 + 3) / 2 = 3
для 6: (2 * 3 + 6) / 3 = 4

т.е. в любой момент можно остановиться и узнать текущее средн. арифм. значение.

Итого: Среднее значение меняется на каждом шаге, а в будущее заглянуть не дано.
Вопрос: как узнать среднеквадратичное отклонение, если для него нужно заранее узнать среднее значение?

Википедия: Среднеквадратическое отклонение

P.S. Пожалуйста, учтите, что файл очень большой. Представьте себе, самый мощный супер компьютер и SSD диском бесконечно большого объёма (но с ничтожной ОЗУ) будет считывать данные неделями. И остановится он по сигналу, после чего должен сразу же выдать ответ, а не начать считывание повторно (зная среднее значение).

Comments

[Василий]

а у вас есть тип данных под такой алгоритм? а то даже extended сломается об неделю расчётов, не говоря уже про double и что по проще.

[Йцу Йцуевич]

на самом деле, конечно расчёты не недельные, и настоящая задача немного другая, а это просто абстрактный пример.
А так, согласен, погрешность увеличивается на каждом шаге, замечание справедливое! Но, я это как-то решу...

[SeptiM]

Интересно, откуда появилась задача в такой формулировке. Я, наверное, повторю предыдущих авторов, но
- формула либо накапливает серьезную ошибку, либо восстанавливает в промежуточных вычислениях всю сумму;
- если поддерживать сумму чисел F_1, сумму квадратов F_2 и общее количество, то среднее квадратичное вычисляется по формуле F_2 / n - F_1^2 / n^2;
- откуда берутся ограничения? Даже если чисел 2^64, их размер 64 бита, можно обойтись длинкой на 256 бит. Кажется, это самая большая интрига в вопросе.

Answer 1

[Andy_U]

Если вы знаете количество чисел, их сумму и сумму их квадратов, то можете вычислить и среднее, и дисперсию. Любой учебник по мат.статистике и/или стат.обработке данных Вам поможет. Единственно, что надо следить за накоплением ошибок округления и возможным переполнением при суммировании.

Answer 2

[Rsa97]

Формула в таком виде смысла не имеет.
Причина: (i-1) * avg = SUM(Value₀...Value_i-1), что, по вашим же словам, в память не поместится.
Можно считать среднее блока (например, 100 чисел), затем суммировать эти средние и делить на количество блоков. Продолжая алгоритм, средние для каждых 100 блоков можно считать отдельно, как суперблок, затем суммировать их и т.д.

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

Answer 3

[evgeniy_lm]

Вы считаете среднеквадратическое отклонение, т.е. предполагается, что все ваши числа приближенно равны и в принципе не имеет значения сколько вы возьмете чисел из файла 10, 100, 1000 или
1 000 000. Количество значений выборки влияет исключительно на точность результата, само собой разумеется идеальную точность ни кто не требует, по этому выберите несколько случайный значений и не парьтесь

Answer 4

[Cheshire-Cat]

Можно рассчитать по алгоритму Велфорда https://ru.qwe.wiki/wiki/Standard_deviation#Rapid_... https://en.wikipedia.org/wiki/Algorithms_for_calcu...
Он позволяет рассчитывать последовательно среднее и среднеквадратичное отклонение.