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

Пусть функция f(x) дважды дифференцируема в E _n. Тогда для нее можно записать разложение по формуле Тейлора в окрестности точки x ^k:

f(x) = f (х ^k) + < f '(х ^k), x-x ^k > + < f ¢¢(х ^k)(x-x ^k), x-x ^k > + o (|| x-x ^k ||²)

Отсюда видно, что поведение функции f(x) с точностью до величины порядка o (|| x-x ^k ||²) может быть описано квадратичной функцией

Ф _k (x) = < f ¢¢(х ^k)(x-x ^k), x-x ^k > + < f '(х ^k), x-x ^k > + f (х ^k). (3.68)

Минимизируем функцию Ф _k (x) вместо f(x). Найдем ее точку минимума x ^{k +1} из условия Ф¢ _k (x) = 0:

Ф¢ _k (x) = f ¢¢(х ^k)(x-x ^k) + f ¢(х ^k) = 0. (3.69)

Пусть матрица Гессе f ¢¢(х ^k) положительно определена при всех xÎ E _n и, следовательно, невырождена (det f ¢¢(х ^k) > 0). Тогда существует обратная матрица [ f ¢¢(х ^k)]^-1. Отметим, что квадратичная функция (3.68) с положительно определенной матрицей f ¢¢(х ^k) сильно выпукла и уравнение (3.69) определяет единственную точку глобального минимума функции Ф _k (x). Умножим слева обе части равенства (3.69) на матрицу [ f ¢¢(х ^k)]^-1 и найдем точку минимума x ^{k +1} квадратичной функции (3.68), аппроксимирующей f(x) в окрестности точки

x=x ^k:

x ^{k +1} = x ^k - [ f ¢¢(х ^k)]^-1× f ¢(х ^k), k = 0, 1, … (3.70)

Итерационный процесс --, начатый из произвольной точки x⁰Î E _n, называется методом Ньютона минимизации функции многих переменных и является обобщением метода Ньютона в одномерном случае (см. разд. 2.3.3).

Очевидно, для квадратичной функции с положительно определенной матрицей A применение метода Ньютона обеспечивает получение точки глобального минимума ровно за один шаг из любой точки x⁰Î E _n.

Для выпуклой функции, отличной от квадратичной, применение этого метода обеспечивает, как правило, быструю сходимость. Дело в том, что на каждом шаге итерационного процесса (3.70) используется информация о поведении функции f(x) в окрестности точки x ^k, содержащаяся не только в значениях первых, но и вторых ее частных производных. Поэтому при прочих равных условиях следует ожидать более быструю сходимость метода Ньютона по сравнению с градиентными методами.

При выборе достаточно хорошего начального приближения x⁰Î E _n минимизирующая последовательность {x ^k } для сильно выпуклой дважды дифференцируемой функции f(x) сходится к точке минимума с квадратичной скоростью r(x ^k, x^*)£ , q Î(0, 1). Если же точка x⁰ выбрана недостаточно близкой к точке х^*, то последовательность (3.70) может расходиться (см. разд. 2.3.3).

Отметим, что даже сходящаяся последовательность {x ^k } метода Ньютона не всегда обеспечивает монотонное убывание f(x), т.е. нера­венство f(x ^{k +1}) < f(x ^k) для некоторых k= 0,1,.. может нарушаться Этот недостаток устранен в обобщенном методе Ньютонa:

x ^{k +1} = x ^k - a _k [f ¢¢(x ^k)]^-1×f¢(x ^k),

где величина a _k > 0 находится на каждом шаге из условия исчерпыва­ющего спуска по направлению р ^k = -[f ¢¢(x ^k)]^-1×f ¢(x ^k).

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

Пример 3.13. Найти точку минимума функции f(x)=4x²₁ + 3x²₂ – 4 x₁x₂ + x₁,методом Ньютона из начальной точки х⁰ = (0,0).

Градиент f¢ (x⁰)=(-1,0), матрица Гессе f "(х⁰)=А= . Найдем обратную матрицу [f¢¢(х⁰)]^-1 = . С помощью формулы (3.70) получаем x¹=x⁰-a _k [f¢¢(х⁰)]^-1× f ¢(x⁰)=(-3/16, -1/8). Так как f '(x¹)=(0,0), то задача решена: х^* = х¹. Целевая функция квадратична, поэтому решение задачи по­лучено за одну итерацию.