Сравнение алгоритмов поиска функций (функции) в Python

Question

Я хотел бы сравнить различные методы поиска корней функций в python (например, методы Ньютона или другие простые методы, основанные на calc). Я не думаю, что у меня будет слишком много проблем при написании алгоритмов. Что было бы хорошим способом сделать фактическое сравнение? Я прочитал немного о Big-O. Будет ли это путь?

(любые идеи или повороты проекта также приветствуются)

Спасибо.

Answer 1

Ответ @sarnold верен - проводить анализ Big-Oh бессмысленно.

Принципиальные различия между алгоритмами поиска корня:

• скорость сходимости (количество итераций)
• вычислительное усилие за итерацию
• что требуется в качестве входных данных (т. Е. Нужно ли знать первую производную, нужно ли устанавливать ограничения lo / hi для деления пополам и т. Д.)
• с какими функциями он работает хорошо (т. Е. Отлично работает с полиномами, но не работает с функциями с полюсами)
• какие допущения она делает в отношении функции (то есть непрерывной первой производной или аналитической и т. Д.)
• как просто реализовать этот метод

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

Answer 2

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

Что это говорит об алгоритме?Хорошо или плохо?

Answer 3

Система обозначений Big-O предназначена для описания поведения алгоритма в пределе при переходе n к бесконечности. Это гораздо проще для теоретического исследования, чем для практического эксперимента. Я бы выбрал для изучения вещи, которые вы можете легко измерить и которые волнуют людей, такие как точность и использованные ресурсы компьютера (время / память).

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

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

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

Answer 4

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

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

Хотя вы можете охарактеризовать число итераций, требуемых для разных алгоритмов, с помощью соотношений между ними (один алгоритм может занять примерно в десять раз больше итераций для достижения той же точности, что и другой), часто это не так. «рост» в итерациях при изменении входных данных.

Конечно, если ваши алгоритмы выполняют больше итераций с «большими» входами, тогда имеет смысл обозначение Big O.

Answer 5

Хотя это очень старый пост, мои 2 цента:)

Как только вы решили, какой алгоритмический метод использовать для их сравнения (так сказать, ваш «протокол оценки»), вас могут заинтересовать способы запуска ваших претендентов на реальных наборах данных.

В этом учебнике объясняется, как это сделать, на примере (сравнение алгоритмов подбора полиномов для нескольких наборов данных).

(я автор, не стесняйтесь оставлять отзывы на странице github!)

Answer 6

Я только что закончил проект, в котором сравнивал методы деления пополам, Ньютона и корневого секвента.Поскольку это практический случай, я не думаю, что вам нужно использовать обозначение Big-O.Система обозначений Big-O больше подходит для асимптотики.Что вы можете сделать, это сравнить их с точки зрения:

Скорость - например, здесь ньютон является самым быстрым, если собраны хорошие условия

Количество итераций - например, здесь деление пополам занимает большую часть итерации

Точность - как часто он сходится к правому корню, если существует более одного корня, или, возможно, он даже не сходится вообще.

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

Другое - ошибки округления

Ради визуализации выможет хранить значения каждой итерации в массивах и выводить их на график.Используйте функцию, которую вы уже знаете, корни.

Answer 7

Зачем беспокоиться?Там может быть только один:

    public class BrentsMethodResult
    {
        public bool TerminatedSuccessfully;
        public double Result;
        public double UpperResult;
        public double LowerResult;
    }

    public static BrentsMethodResult BrentsMethodSolve(Func<double, double> function, double lowerLimit, double upperLimit, double errorTol)
    {
        BrentsMethodResult result = new BrentsMethodResult();

        double a = lowerLimit;
        double b = upperLimit;
        double c = 0;
        double d = double.MaxValue;

        double fa = function(a);
        double fb = function(b);
        result.LowerResult = fa;
        result.UpperResult = fb;

        if (Double.IsNaN(fa) || Double.IsNaN(fb))
        {
            result.TerminatedSuccessfully = false;
            result.Result = Double.NaN;
            return result;
        }

        double fc = 0;
        double s = 0;
        double fs = 0;

        // if f(a) f(b) >= 0 then error-exit
        if (fa * fb >= 0)
        {
            result.TerminatedSuccessfully = false;
            if (Math.Abs(fa) < Math.Abs(fb))
            {
                result.Result = a;
                return result;
            }
            else
            {
                result.Result = b;
                return result;
            }
        }

        // if |f(a)| < |f(b)| then swap (a,b) end if
        if (Math.Abs(fa) < Math.Abs(fb))
        { double tmp = a; a = b; b = tmp; tmp = fa; fa = fb; fb = tmp; }

        c = a;
        fc = fa;
        bool mflag = true;
        int i = 0;

        while (Math.Abs(fb) > errorTol && Math.Abs(a - b) > errorTol)
        {
            //tol1 = 2.0 * double_Accuracy * Math.Abs(b) + 0.5 * errorTol;

            if ((fa != fc) && (fb != fc))
                // Inverse quadratic interpolation
                s = a * fb * fc / (fa - fb) / (fa - fc) + b * fa * fc / (fb - fa) / (fb - fc) + c * fa * fb / (fc - fa) / (fc - fb);
            else
                // Secant Rule
                s = b - fb * (b - a) / (fb - fa);

            double tmp2 = (3 * a + b) / 4;
            if ((!(((s > tmp2) && (s < b)) || ((s < tmp2) && (s > b)))) || (mflag && (Math.Abs(s - b) >= (Math.Abs(b - c) / 2))) || (!mflag && (Math.Abs(s - b) >= (Math.Abs(c - d) / 2))))
            {
                s = (a + b) / 2;
                mflag = true;
            }
            else
            {
                if ((mflag && (Math.Abs(b - c) < errorTol)) || (!mflag && (Math.Abs(c - d) < errorTol)))
                {
                    s = (a + b) / 2;
                    mflag = true;
                }
                else
                    mflag = false;
            }
            fs = function(s);

            if (Double.IsNaN(fs))
            {
                result.TerminatedSuccessfully = false;
                result.Result = Double.NaN;
                return result;
            }

            d = c;
            c = b;
            fc = fb;
            if (fa * fs < 0) { b = s; fb = fs; }
            else { a = s; fa = fs; }

            // if |f(a)| < |f(b)| then swap (a,b) end if
            if (Math.Abs(fa) < Math.Abs(fb))
            { double tmp = a; a = b; b = tmp; tmp = fa; fa = fb; fb = tmp; }
            i++;
            if (i > 100)
            {
                throw new Exception(String.Format("100 iterations exceeded and error is {0}", fb));
            }
        }
        result.TerminatedSuccessfully = true;
        result.Result = b;
        return result;
    }

Answer 8

Я бы посоветовал вам взглянуть на следующую демонстрацию поиска корня Python.Это простой код, с некоторыми различными методами и сравнениями между ними (с точки зрения скорости сходимости).

http://www.math -cs.gordon.edu / courses / mat342 / python / findroot.py