Что такое переменная "e" в популярных реализациях алгоритма поиска корня Brent?
Я читаю стандартную (числовые рецепты и версии C GSL идентичны) реализацию алгоритма поиска корня Brent, и не могу понять значение переменной "e". Использование предполагает, что "е" должно быть предыдущим расстоянием между скобками. Но тогда почему он установлен на "xm" (половину расстояния), когда мы используем бисекцию?
3 ответа
Я не знаком с алгоритмом. Тем не менее, я могу сравнить источник C и описание алгоритма в Википедии. Алгоритм кажется прямым (если вы знакомы с методами поиска корней), но реализация C выглядит как прямой порт фортрана, поэтому его довольно сложно прочитать.
Я думаю, что e связано с циклом условно.
Википедия говорит (строка 8 алгоритма): repeat until f(b or s) = 0 or |b − a| is small enough (convergence)
Источник C говорит: e = b - a, тогда позже if (fabs(e) <= tol ...,
Я надеюсь, что назначение переменных будет четко описано в книге, но, очевидно, нет:)
Хорошо, вот и все. Я нашел оригинальную реализацию (в algol 60) здесь. В дополнение к хорошему описанию алгоритма он говорит (начиная со страницы 50):
позволять
eбыть ценностьюp/qна шаге перед последним. Если|e|<δ или|p/q|≥1/2|e|затем делим пополам, иначе мы делим пополам или интерполяцию, как в алгоритме Деккера. таким образом|e|уменьшается как минимум в два раза на каждом втором шаге, и когда|e|<δ деление пополам. (После деления пополамe = mдля следующего шага.)
Таким образом, добавление e является "основной модификацией" алгоритма Брента в Деккере.
E - это переменная "эпсилон", которая в основном является мерой того, насколько близко находится достаточно близко. Вашему конкретному приложению может не потребоваться 20 цифр точности, поэтому epsilon позволяет вам сбалансировать, сколько требуется итераций (т. Е. Как долго он выполняется), и насколько вам это нужно.
С числами с плавающей запятой вы не сможете быть точными, поэтому эпсилон должен быть небольшим ненулевым числом. Фактическое значение зависит от вашего приложения... это в основном самая большая допустимая ошибка.
На этапе деления пополам интервал точно уменьшается вдвое. Таким образом, e, содержащая текущую ширину интервала, также уменьшается вдвое.