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

Перейдем к изложению метода второго порядка, использующе­го вторые частные производные минимизируемой функции /(ж). Этот метод является прямым обобщением метода Ньютона для отыскания решения системы уравнений <~р{х) = 0, где (р : Rn —> Rn. Возьмем линейную аппроксимацию функции <~р{х) в окрест­ности точки хк и перепишим уравнение в следующем виде:

<р(х) = ip(xk) + ip'(xk)(x - хк) + о(\\х - хк\\) = 0.

Отбрасывая последний член в этом разложении, получим линей­ную систему уравнений относительно нового приближения хк+1.

Таким образом, метод Ньютона отыскания решения системы урав­нений описывается следующей формулой:

xk+1 =хк - Фк)-

Рассмотрим теперь случай, когда функция <~р{х) является гра­диентом некоторой функции /(ж). Формула метода Ньютона для решения уравнения /'(ж) = 0 выглядит так:

хк+1 =хк _ (/"(ж^))-1

В этом случае метод Ньютона можно интерпретировать как по­иск точки минимума квадратичной аппроксимации функции /(ж) в окрестности точки хк.

Лемма 4.4 Пусть f — дважды непрерывно дифференцируемая функция. Если f — сильно выпуклая функция с константой I, то выполняется следующее неравенство:

\\[П*)}-1\\<1-1-

Доказательство. Пользуясь теоремой о среднем, получим сле­дующие формулы для конечных приращений функции /:

1

/(ж + у) - /(ж) = J (/'(ж + ty),y)dt = (/'(ж + пу), у) = о

= (f(x),y)+(f"(x + r2y)y,y)/2, где 0 < ti,t2 < 1. Воспользуемся условием сильной выпуклости

(f"{x + т2у)у, у)/2 = /(ж + у) - /(ж) - (/'(ж), у) > 1\\у\\2/2.

Заменяя у на ty, получим:

(f"(x + t2ty)ty,ty) > l\\ty\\2.

Следовательно,

г2(Г(х + т2гу)у,у)>г21\\у\\2.

Поделив на V2 и устремляя £ к нулю, будем иметь

(Г'(х)у,у)>1\\у\\2.

Положим у = (/"(х))~12 и, используя неравенство Коши-Буняковского, получим /||(/"(ж))_12:|| < \\г\\ для любого г. Это означает, что

Лемма доказана.

Пусть последовательность {хк} получена с помощью метода Ньютона и точка х* — глобальный минимум функции /. Ниже­следующая теорема устанавливает условия квадратичной скоро­сти сходимости метода.

Теорема 4.3 Пусть дважды непрерывно дифференцируемая функ­ция / сильно выпукла (с константой I > 0), вторая производная удовлетворяет условию Липшица

\\/"(х) — /"(у)\\ < Т \\х — у\\, для любых х, у 6 Ь5"",

и д = Ь\\/'(х°) ||/2/2 < 1. Тогда хк —> х* при к —> оо и метод Ньютона имеет квадратичную скорость сходимости

\\хк - х*\\ < {21/1)а2\

Доказательство. Воспользуемся следующей формулой конеч­ных приращений:

1

д(х + у) = д(х) + (д'(х),у) + I(д'(х + ту) - д'(х))а1т.

Подставим вместо д производную функции / и, применяя нера­венство Коши-Буняковского, получим

\\f>(x + y)-f>(x)-(f»(x),y)\\<L\\y\\2/2.

Тогда для х = хк и у = — [f"(xk)]~1f'(xk) имеем

II/V+1)II<(V2)||[/V)]_1II2II/V)II2-

Применяя лемму 4.4, получим

||/'(^+1)||<(L/2/2)||/V)H2-Итерируя это неравенство по к, приходим к неравенству

||/V+1)ll<(2/2/b) (L\\f(x°)\\/2l2f+\

q

Остается показать, что

\\f'(xk+1)\\ > l\\xk+1 - х*\\.

Из определения 4.1 сильной-выпуклости имеем

(f'(x)- f'(y),x-y)>l\\x-y\\2.

Тогда при подстановке у = ж*, ж = хк+1, учитывая равенство /'(ж*) = 0, получим

l\\xk+1 - ж*||2 < (f{xk+l),x* - xk+1) <

< ll/V+1)ll

откуда и следует требуемое неравенство. Теорема доказана.