Методы с использованием информации о производной функции

В методах прямого поиска при вычислении значений минимизируемой функции f (x) неизбежно возникают погрешности, к которым чувствительны алгоритмы прямого поиска, основанные на сравнении значений функции в отдельных точках. Если унимодальная функция f (x) непрерывно дифференцируема на отрезке минимизации, то точку х * наименьшего значения функции можно вычислять как корень уравнения:

f   (x) = 0

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

4.1. Метод Ньютона (метод касательных). Если строго унимодальная на отрезке [ a, b ] функция f (x) дважды непрерывно дифференцируема на этом отрезке, то точку x * минимума этой функции можно найти путем решения уравнения f  (x) = 0 методом Ньютона, иногда называемым методом касательных. Выбираем x ₀  начальное приближение, называемое обычно начальной точкой. Линеаризуем функцию f (x) в окрестности начальной точки, приближенно заменив дугу графика этой функции касательной в точке (x ₀, f  (x ₀)). Выберем в качестве следующего приближения к х * точку x ₁ пересечения касательной с осью абсцисс.

В общем случае сходимость метода Ньютона существенно зависит от выбора начальной точки x ₀. Поэтому говорят, что метод Ньютона обладает локальной сходимостью в том смысле, что надо выбрать хорошее начальное приближение, попадающее в такую окрестность точки х *, где f '' (x) > 0. Однако проверка выполнения этого условия не всегда возможна. Достаточным условием монотонной сходимости метода Ньютона будут постоянство в интервале между точками x ₀ и х * знака производной f ''' (x) и совпадение его со знаком f ' (x). Оказывается, что в этом случае метод Ньютона обладает квадратичной скоростью сходимости в некоторой окрестности точки х *.

4.2. Метод секущих. Метод секущих похож на метод Ньютона, но строится не касательная к графику производной, а секущая. Геометрическая интерпретация этого метода состоит в том, что в качестве очередного приближения x_{k +1} выбирают точку пересечения с осью абсцисс секущей к графику функции f ' (x).

Этот метод имеет сверхлинейную скорость сходимости. Модификации метода Ньютона обладают только локальной сходимостью, т.е. сходятся, если начальная точка выбрана в некоторой окрестности точки минимума функции. Если же начальная точка расположена слишком далеко от точки минимума, то подобный метод может расходиться или «зацикливаться». В отличие от метода средней точки метод секущих использует информацию не только о знаке производной, но и о значениях в пробных точках.