метод Брента
В численном анализе метод Брента представляет собой гибридный алгоритм поиска корня, сочетающий метод деления пополам , метод секущих и обратную квадратичную интерполяцию . Он обладает надежностью деления пополам, но может быть таким же быстрым, как некоторые из менее надежных методов. Алгоритм пытается использовать потенциально быстро сходящийся метод секущих или обратную квадратичную интерполяцию, если это возможно, но при необходимости он возвращается к более надежному методу деления пополам. Метод Брента принадлежит Ричарду Бренту [1] и основан на более раннем алгоритме Теодора Деккера . [2] Следовательно, метод также известен какМетод Брента-Деккера .
Современные усовершенствования метода Брента включают метод Чандрупатлы , который проще и быстрее для функций, плоских вокруг своих корней; [3] [4] Метод Риддерса , который выполняет экспоненциальную интерполяцию вместо квадратичной, обеспечивая более простую замкнутую формулу для итераций; и метод ITP, который представляет собой гибрид между regula-falsi и bisection, который обеспечивает оптимальные гарантии наихудшего случая и асимптотические гарантии.
Предположим, что мы хотим решить уравнение f ( x ) = 0. Как и в случае с методом деления пополам, нам нужно инициализировать метод Деккера двумя точками, скажем, a 0 и b 0 , такими, что f ( a 0 ) и f ( b 0 ) имеют противоположные знаки. Если f непрерывно на [ a 0 , b 0 ], теорема о промежуточном значении гарантирует существование решения между a 0 и b 0 .
Вычисляются два предварительных значения для следующей итерации. Первый дается линейной интерполяцией, также известной как метод секущих:
Если результат метода секущих s лежит строго между b k и m , то он становится следующей итерацией ( b k +1 = s ), в противном случае используется средняя точка ( b k +1 = m ).
Затем значение новой контрапункта выбирается таким образом, чтобы f ( a k +1 ) и f ( b k +1 ) имели противоположные знаки. Если f ( a k ) и f ( b k +1 ) имеют противоположные знаки, то контрапункт остается прежним: a k +1 = a k . В противном случае f ( b k +1 ) и f ( b k ) имеют противоположные знаки, поэтому новая контрапункт становится a k+1 знак равно б к .
