Алгоритм BRE

Алгоритм BRE, или алгоритм Брента (Brent) [3], – это алгоритм одномерного поиска, который является комбинацией метода золотого сечения и квадратичной интерполяции. Методы последовательного перебора, подобные методу золотого сечения, имеют скорость сходимости первого порядка, в то время как полиномиальные методы интерполяции имеют асимптотическую скорость сходимости более высокую, чем линейная. С другой стороны, сходимость метода золотого сечения носит глобальный характер, т. е. обеспечивается на любом шаге работы алгоритма, в то время как сходимость метода полино­миаль­ной интерполяции является лишь локальной (асимптотической) и может потребовать выполнения большого числа итераций. Метод Брента направлен на то, чтобы объединить лучшие свойства обоих методов.

Одномерный поиск по методу Брента начинается с использования алгоритма золотого сечения, но при этом вычисляются некоторые дополнительные точки. По этим точкам рассчитывается аппроксимирующая квадратичная функция и вычисляется ее минимум. Если этот минимум находится в пределах исследуемого интервала, то он используется для уточнения квадратичной аппроксимации в пределах этого же интервала. Если минимум находится за пределами интервала, то продолжается поиск методом золотого сечения.

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

В рамках ППП Neural Network Toolbox этот алгоритм реализован в виде М-функции scrchbre.