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

Разложим f(x) в ряд Тейлора до 2-го слагаемого включительно:

(*)

- вектор

- матрица Гессе, матрица вторых производных.

Будем рассматривать квадратичную аппроксимацию f(x) тогда получим (*) без то есть предполагаем, что f(x) квадратичная форма. Эта форма имеет единственную точку min, который является корнем уравнения f ’(x)=0.

В данном случае:

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

Пример:

Сделаем одну итерацию метода Ньютона для квадратичной функции

Этот пример показывает связь решения системы уравнений Ax-b = 0 и поиска минимума соответствующей функции f(x).

= A - матрица вторых производных.

Одна итерация метода Ньютона:

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

Точка х₁ гораздо ближе к х*, чем в градиентных методах, но надо вычислить матрицу Гессе и обратить ее. Градиентный метод медленнее, но без дополнительных вычислений.

Оценим скорость сходимости метода Ньютона:

Теорема (о скорости сходимости метода Ньютона):

Пусть f(x) дважды дифференцируема, матрица удовлетворяет условию

Липшица с константой L:

f(x) сильно выпукла: 0< l I £Ñ² f(x) и начальное приближение удовлетворяет условию:

Тогда метод Ньютона сходится х* с квадратичной скоростью

Доказательство:

Известно, что:

Если на g’(x) удовлетворяет условию Липшица , то

Применим это отношение к Ñ² f(x), тогда

Пусть x = x_k, тогда

Дано (см. условие) тогда:

Таким образом .

Пусть q₁= (обозначим). Рассмотрим полученное неравенство

.........................................................................

Для сильно выпуклых функций известно

Тогда

Теорема доказана.

Если начальные условия не удовлетворяют требованиям теоремы, то метод может не сходиться.

Пусть метод обеспечивает выполнение следующего неравенства

, где d- наибольшее из чисел, для которых выполняется это условие, тогда d- скорость сходимости метода.

Если обозначить D_k= , тогда скорость сходимости

d = , при D_k®0 (k® ¥).

Пусть D_k+1»q D_k, 0< q< 1. Для этого случая d =1- линейная скорость. Для метода Ньютона тогда D_k+1= const D_k² Þ d =2- поэтому скорость называется квадратичной.

Сравнительная таблица достоинств и недостатков градиентного метода и метода Ньютона:

Метод	Достоинства	Недостатки
градиентный метод	1. Глобальная сходимость, т.е. слабые требования на исходные данные, точка х₀ может быть далека от х*. 2. Слабые требования к f(x), только f’(x) нужна 3. Относительная простота вычислений	1. Медленная скорость сходимости (геометрическая сходимость, скорость сходимости d = 1).
метод Ньютона	1. Быстрая сходимость (квадратичная)	1. Локальная сходимость, т.е. начальное приближение должно быть достаточно близко к х*) 2. Жесткие требования на саму функцию (должна быть дважды непрерывнодифференц. 3. Большой объем вычислений, связанный с необходимостью вычисления матрицы вторых производных и ее обращения.