§ 9.4. Метод Ньютона и другие методы минимизация гладких функций

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

1. Метод бисекции.

Пусть унимодальная непрерывно дифференцируемая на отрезке функция и на отрезке точка х является единственной стационарной точкой. Применительно к решению уравнения (9.14) одна итерация метода бисекции выглядит следующим образом.

Пусть отрезок локализации известен и найдено значение Тогда производят следующие действия.

1°. Вычисляют значение

2°. Если то полагают . В противном случае полагают

3°. Вычисляют

В рассматриваемом случае метод сходится с оценкой погрешности

И обладает всеми присущими методу бисекции решения нелинейных уравнений достоинствами и недостатками (см. § 4.3). Возникает лишь дополнительная проблема, связанная с необходимостью вычисления производной

2. Метод Ньютона.

Для решения уравнения (9.14) можно попытаться воспользоваться методом Ньютона (см. § 4.6), расчетная формула которого в данном случае принимает вид

Следствием теоремы 4.6 является следующее утверждение.

Теорема 9.1. Пусть в некоторой окрестности точки х функция трижды непрерывно дифференцируема и выполняется условие Тогда найдется такая малая -окрестность корня х, что при произвольном выборе начальною приближения из этой -окрестности метод Ньютона (9.16) сходится квадратично.

В силу сверхлинейной сходимости для метода Ньютона можно использовать следующий критерий окончания итераций:

Пример 9.11. Используя метод бисекции, найдем с точностью точку локального минимума функции локализованную на отрезке [0, 1].

Положим Заметим, что .

I итерация. 1. Вычислим

2. Так как

3. Вычислим

Результаты остальных итераций приведены в табл. 9.8.

Таблица 9.8

После выполнения шести итераций вычисления можно прекратить и положить Таким образом, Отметим, что для достижения точности потребовалось шесть вычислений значения производной

Пример 9.12. Используя метод Ньютона, найдем с точностью точку локального минимума функции локализованную на отрезке [0, 1].

Положим Результаты вычислений по формуле (9.16), имеющей в данном случае вид

приведены в табл. 9.9.

Таблица 9.9 (см. скан)

При итерации прерываются. Можно считать, что Заметим, что точность была достигнута уже после выполнения двух итераций.

3. Метод последовательной параболической интерполяции.

Этот метод предназначен для минимизации гладких функций, но в отличие от методов бисекции и Ньютона не требует вычисления производных.

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

За очередное приближение принимается та точка, в которой функция достигает минимума. Из уравнения

получается формула

Естественно, что для начала работы этого метода требуется выбор трех начальных приближений

Пусть функция трижды непрерывно дифференцируема в некоторой окрестности точки х и удовлетворяет в ней условию Можно показать, что в этом случае выбор начальных приближений из достаточно малой окрестности точки х гарантирует, что для всех к и метод последовательной параболической интерполяции сходится сверхлинейно, с порядком, приближенно равным 1.324. Поэтому в качестве критерия окончания итерационного процесса можно принять неравенство (9.17).

Отметим, что в описанном методе используются только значения функции вычисляемые в точках Поэтому (как и для методов прямого поиска) при его реализации на ЭВМ достижимая точность метода ограничена снизу величиной, равной радиусу интервала неопределенности. После того как очередное приближение попадет в интервал дальнейшие вычисления теряют смысл (см. § 9.2).

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

4. Гибридные алгоритмы.

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

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