Лучшая стратегия для вычисления среднего с высокой точностью

Question

Я сравнивал два алгоритма, вычисляющих среднее число случайных чисел.

• Первый алгоритм суммирует все числа и делит на количество элементов в конце
• Второй алгоритм вычисляет среднее значение для каждой итерации и повторно использует результат при получении новых данных.

Я полагаю, что здесь нет ничего революционного, и я не математик, поэтому я не могу дать название этим двум алгоритмам.

Вот мой код:

#include <iostream>
#include <iomanip>
#include <cstdlib>

class Average1
{
public:
    Average1() : total( 0 ), count( 0 ) {}

    void add( double value )
    {
        total += value;
        count++;
    }

    double average()
    {
        return total/count;
    }

private:
    double total;
    size_t count;
};

class Average2
{
public:
    Average2() : av( 0 ), count( 0 ) {}

    void add( double value )
    {
        av = (av*count + value)/(count+1);
        count++;
    }

    double average()
    {
        return av;
    }

private:
    double av;
    size_t count;
};

void compare()
{
    Average1 av1;
    Average2 av2;
    double temp;
    for ( size_t i = 0; i != 100000000; ++i )
    {
        temp = static_cast<double>(std::rand()) / static_cast<double>(RAND_MAX);
        av1.add( temp );
        av2.add( temp );
    }

    std::cout << std::setprecision(20) << av1.average() << std::endl;
    std::cout << std::setprecision(20) << av2.average() << std::endl;
}

int main()
{
    compare();
    return 0;
}

Выход:

0.50001084285722707801
0.50001084285744978875

Разница, безусловно, связана с double Тип точности.

В конце концов, какой из них хороший метод? Какой из них дает реальное математическое среднее (или ближе всего к...)?

Answer 1

Если вы действительно хотите высокую точность:

• рассмотреть произвольную арифметику точности (например, с GMP)
• рассмотреть алгоритм суммирования Кахана (возможные проблемы с компилятором)
• рассмотрим алгоритм Шевчука (который доступен в Python как math.fsum)

Изменить: Python-документы в math.fsum также ссылки на этот обзор подходов

Answer 2

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

Answer 3

Джон Д. Кук дает отличный анализ, который он рекомендует:

av = av + (value - av)/count;

Его посты начинаются со сравнения трех методов вычисления стандартного отклонения.

Тогда теоретическое объяснение численных результатов

и последнее Точно вычисление бегущей дисперсии

Answer 4

Мое собственное мнение состоит в том, что оба вычисляют значение времени подсчета, которое является большим числом, прежде чем его разделить, что объясняет, почему ваш результат является приблизительным. Я бы сделал:

class Average3
{
public:
    Average3() : av( 0 ), count( 0 ) {}

    void add( double value )
    {
        count++;
        av +=  (value - av)/count;
    }
...

Но вы все равно теряете точность при добавлении последних чисел, потому что добавление значения / количества мало по сравнению со средним. Я был бы рад узнать, была ли моя интуиция правильной, хотя