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

Обсуждение градиентного метода

Метод наискорейшего спуска

Антипод метода с дроблением шага. Количество итераций минимально.

определяется решением задачи минимизации. Для этого рассматривается функция .

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

Недостаток: на каждом шаге надо решить задачу минимизации функции одной переменной.

Отличие: точки отрезков будут касаться линий уровня, а не пересекать их.

В силу ортогональности за минимальное число шагов достигаем минимума

Алгоритм определения минимума методом наискорейшего спуска.

1)Задаются . Вычисляются .

Полагается k=1.

2)Определяется .

3)Вычисляются ,,,

4)Проверяется условие окончания вычислений

Если условие выполняется, то вычисления завершаются. Если нет, то полагается и переход к пункту 2.

Ответ: ,

Достоинство: простота метода среди методов поиска оптимума безусловных задач.

Недостатки:

1)плохо работают для функций «овражного типа» (большое число итераций).

Функциями «овражного типа» называют функции, у которых линии уровня сильно вытянуты, то есть имеют овражную структуру.

2)в окрестности точки (точки минимума) точность градиентных методов падает, так как норма градиента мала, компоненты градиента тоже малы и следовательно точность вычисления малых величин падает.

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

Рассматриваемый метод Ньютона является обобщением метода нахождения корня квадратичного уравнения.

, (3.5)

где – скалярная функция скалярного аргумента.

В окрестности точки функция раскладывается в ряд Тейлора и учитывается только линейная часть этого разложения.

Подставим это выражение в ряд Тейлора (3.5):

(3.6)

позволяет определить новое приближение корня .

Аналогичным способом осуществляется разложение в точке и т.д.

Рекуррентная формула, являющаяся формулой Ньютона:

(3.7)

Соотношение (3.7) является методом касательных.

– искомый корень уравнения (3.5)

Рассмотрим – n-мерная векторная функция n-мерного векторного аргумента.

Решим систему уравнений:

(3.8)

Для решения системы будем использовать соотношение (3.7) и подход, который к нему применен. Подставим в (3.8) только линейные части и в результате получим следующую систему:

(3.9)

n – линейных уравнений и n – неизвестных и решение этой системы имеет следующий вид:

(3.10)

Вычисляем скалярную функцию векторного аргумента

Находим градиент функции:

Корни этого уравнения и есть стационарные точки.

(3.11)