Root Finding With Derivatives: Newton-Raphson, Halley & Schröder . Boost , Math Toolkit 2.5.0 , Root finding

Root Finding With Derivatives: Newton-Raphson, Halley & Schröder

Synopsis

#include <boost/math/tools/roots.hpp>

namespace boost { namespace math {
namespace tools { // Note namespace boost::math::tools.
// Newton-Raphson
template <class F, class T>
T newton_raphson_iterate(F f, T guess, T min, T max, int digits);
template <class F, class T>
T newton_raphson_iterate(F f, T guess, T min, T max, int digits, boost::uintmax_t& max_iter);
// Halley
template <class F, class T>
T halley_iterate(F f, T guess, T min, T max, int digits);
template <class F, class T>
T halley_iterate(F f, T guess, T min, T max, int digits, boost::uintmax_t& max_iter);
// Schr'''&#xf6;'''der
template <class F, class T>
T schroder_iterate(F f, T guess, T min, T max, int digits);
template <class F, class T>
T schroder_iterate(F f, T guess, T min, T max, int digits, boost::uintmax_t& max_iter);
}}} // namespaces boost::math::tools.

Description

Все эти функции выполняют итеративный корневой поискс использованием производных:

<newton_raphson_iterate>выполняет второй заказИтерация Ньютона-Рафсона.
<halley_iterate>и<schroder_iterate>исполняют третий порядокГаллейиШрöдеритерация.

Все функции имеют одинаковые параметры:

Parameters of the root finding functions

F f

Тип F должен быть объектом вызывающей функции, который принимает один параметр и возвращаетstd::pair, std::tuple, boost::tuple или boost::fusion::tuple:

Для итеративного метода второго порядкаНьютон Рафсон<tuple>должен иметьдваэлемента, содержащих оценку функции и ее первую производную.

Для методов третьего порядкаГаллейи Шрöдер]<tuple>должны иметьтриэлемента, содержащих оценку функции и ее первого и второго производных.

T guess

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

T min

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

T max

Максимально возможное значение для результата используется в качестве начальной верхней скобки.

int digits

Желаемое количество двоичных цифр точности.

uintmax_t& max_iter

Дополнительное максимальное количество итераций для выполнения. На выходе это обновляется до фактического количества выполненных итераций.

При использовании этих функций следует отметить, что:

Дефолт<max_iter= (std::numeric_limits<boost::uintmax_t>::max)()>фактически является «итеративным навсегда».
Они могут быть очень чувствительны к исходному предположению, обычно они очень быстро сходятся, если исходное предположение имеет две или три десятичных цифры. Однако конвергенция не может быть лучше, чембисект, или в некоторых редких случаях даже хуже, чембисект, если исходное предположение далеко от правильного значения и производные близки к нулю.
Эти функции включают в себя специальные чехлы для обработки нулевых первых (и вторых, где это уместно) производных и в этом случае возвращаются кбиссекту. Однако полезно, если функтор F определен для возврата произвольно малого значенияправильного знака, а не нуля.
Если производная при текущем наилучшем предположении для результата бесконечна (или очень близка к бесконечности), то эти функции могут закончиться преждевременно. Большая первая производная приводит к очень маленькому следующему шагу, вызывая условие терминации. Производная итерация может быть неуместной в таких случаях.
Если функция «действительно хорошо себя ведет» (монотонна и имеет только один корень), границы скобокминимакстакже могут быть установлены в самых широких пределах, таких как ноль и<numeric_limits<T>::max()>.
Но если функция более сложна и может иметь более одного корня или полюса, выбор границ — это защита от выпрыгивания, чтобы искать «неправильный» корень.
Эти функции возвращаются кбиссекту, если следующий вычисленный шаг выводит следующее значение из пределов. Границы обновляются после каждого шага, чтобы обеспечить конвергенцию. Тем не менее, хорошая первоначальная догадка, подкрепленная асимптотически жесткими границами, улучшит производительность без конца - вместо того, чтобы полагаться набисекция.
Значениецифримеет решающее значение для хорошего выполнения этих функций, если оно установлено слишком высоко, то в лучшем случае вы получите одну дополнительную (ненужную) итерацию, а в худшем случае последние несколько шагов будут протекать поразделу. Помните, что возвращенное значение никогда не может быть более точным, чемf(x)может быть оценено, и что еслиf(x)страдает от ошибок отмены, поскольку она стремится к нулю, тогда вычисленные шаги будут фактически случайными. Значениецифрдолжно быть установлено таким образом, чтобы итерация завершалась до этой точки: помните, что для методов второго и третьего порядка число правильных цифр в результате значительно увеличивается с каждой итерацией,цифрдолжно быть установлено экспериментом, чтобы конечная итерация просто принимала следующее значение в зону, гдеf(x)становится неточным. Хорошей отправной точкой дляцифрбудет 0,6*D для Ньютона и 0,4*D для Галлея или Shröдер итерации, где D<std::numeric_limits<T>::digits>.
Если вам нужен какой-то диагностический вывод, чтобы увидеть, что происходит, вы можете<#defineBOOST_MATH_INSTRUMENT>до<#include<boost/math/tools/roots.hpp>>, а также обеспечить отображение всех значимых цифр с<cout.precision(std::numeric_limits<double>::digits10)>: Или, может быть, даже значительные цифры с<cout.precision(std::numeric_limits<double>::max_digits10)>: но будьте осторожны, это может привести к обильному выходу!
Наконец, вы можете быть в состоянии сделать лучше, чем эти функции, вручную кодируя эвристику, используемую, чтобы они были адаптированы к конкретной функции. Вы также можете вычислить соотношение производных, используемых этими методами, более эффективно, чем вычисление самих производных. Как всегда, алгебраическое упрощение может стать большой победой.

Newton Raphson Method

При исходной догадкеx0последующие значения вычисляются с использованием:

Вне пределов шаги возвращаются кбисекциитекущих границ.

В идеальных условиях количество правильных цифр удваивается с каждой итерацией.

Halley's Method

При исходной догадкеx0последующие значения вычисляются с использованием:

Чрезмерная компенсация второй производной (той, которая идет в неправильном направлении) заставляет метод вернуться к шагу Ньютона-Рафсона.

Вне пределов шаги возвращаются к разделу текущих границ.

В идеальных условиях количество правильных цифр утроится с каждой итерацией.

Schröder's Method

При исходной догадке x0 вычисляются последующие значения с использованием:

Чрезмерная компенсация второй производной (той, которая идет в неправильном направлении) заставляет метод вернуться к шагу Ньютона-Рафсона. Аналогично, шаг Ньютона используется всякий раз, когда этот шаг Ньютона изменит следующее значение более чем на 10%.

Вне пределов ступени возвращаются кбисекциитекущих границ.

В идеальных условиях количество правильных цифр утроится с каждой итерацией.

Это общий результат Schröder (уравнение 18 отСтюарта, Г. У. «О бесконечно многих алгоритмах решения уравнений». Английский перевод оригинальной статьи Schröder. College Park, MD: University of Maryland, Institute for Advanced Computer Studies, Department of Computer Science, 1993.

Этот метод гарантирует, по крайней мере, квадратическую конвергенцию (та же, что и метод Ньютона), и, как известно, хорошо работает в присутствии нескольких корней: то, что не могут сделать ни Ньютон, ни Галлей.

Examples

См.примеры поиска корней.

Статья Root Finding With Derivatives: Newton-Raphson, Halley & Schröder раздела Math Toolkit 2.5.0 Root finding может быть полезна для разработчиков на c++ и boost.