Я читаю стандартные (числовые рецепты и GSL версии C идентичны) ) реализация алгоритма поиска корня Брента и не может понять значение переменной "e" . Использование предполагает, что «e» должно быть предыдущим расстоянием между скобками. Но тогда почему для него установлено значение «xm» (половина расстояния), когда мы используем деление пополам?
Что такое переменная e в популярных реализациях алгоритма поиска корня Брента?
Ответы (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 ....
Я бы надеялся, что назначение переменных будет ясно описано в книге, но, видимо, нет :)
Хорошо, вот. Я нашел оригинальную реализацию (на алголе 60) здесь. В дополнение к красивому описанию алгоритма в нем говорится (начиная со страницы 50):
пусть
eбудет значениемp/qна шаге перед последним. Если|e|‹ или|p/q|1/2|e|, то делаем деление пополам, в противном случае делаем либо деление пополам, либо интерполяцию, как в алгоритме Деккера. Таким образом,|e|уменьшается как минимум в два раза на каждом втором шаге, а когда|e|‹ необходимо выполнить деление пополам. (После деления пополам мы беремe = mдля следующего шага.)
Таким образом, добавление e является «основной модификацией» Брента в алгоритме Деккера.
person
Seth
schedule
29.12.2009
Да, я вижу, что e связано с условным циклом, потому что оно читается в операторе if... Дело в том, что b и a в условном операторе Википедии являются текущим лучшим предположением и противоположной точкой (где функция имеет другой знак), в то время как в кодах GSL и Netlib b — это наилучшее предположение, a — предыдущее наилучшее предположение, c — противоположная точка.
- person quant_dev; 30.12.2009
Спасибо. Я мог подумать о поиске оригинальной статьи через Google Books...
- person quant_dev; 30.12.2009
Это был несчастный случай :P. Я хотел узнать немного больше об алгоритме. Оригинальная книга просто оказалась первым результатом при поиске нулевой процедуры алгола 60, приведенной в алгоритмах Ричарда Брента (из одного из комментариев в источнике Fortran).
- person Seth; 30.12.2009
E - это переменная "эпсилон", которая в основном является мерой того, насколько близко достаточно близко. Вашему конкретному приложению может не требоваться 20-значная точность, поэтому epsilon позволяет сбалансировать требуемое количество итераций (т. е. продолжительность выполнения) и требуемую точность.
С числами с плавающей запятой вы не сможете быть точными, поэтому эпсилон должен быть небольшим ненулевым числом. Фактическое значение зависит от вашего приложения... в основном это самая большая допустимая ошибка.
person
Chris Arguin
schedule
29.12.2009
Я так не думаю, потому что e — это а) переменная, которая меняется между итерациями, б) проверяется только при принятии решения о том, делать ли обратно-квадратичную интерполяцию или вернуться к бисекции, и в) уже есть переменная эластичного допуска tol, который отвечает за то, что, как вы утверждаете, e делает. Нет печенья.
- person quant_dev; 30.12.2009
Я думаю, что он в основном прав, он не говорит, что это константа, которая указывает желаемую точность, скорее он говорит, что это значение, которое вы сравниваете с константой, которая определяет желаемую точность. Хорошо сочетается с другим ответом. Его также можно использовать для определения того, какой алгоритм (обратный квадратичный или пополам) использовать на основе их характеристик сходимости?
- person Tim Lovell-Smith; 30.12.2009
e не является эпсилон-переменной, это переменная tol1.
- person Robotbugs; 11.03.2015
Во время шага деления пополам интервал уменьшается ровно вдвое. Таким образом, e, удерживающее текущую ширину интервала, также уменьшается вдвое.
person
Drew Hall
schedule
30.12.2009
