Метод Ньютона та його модифікації

Метод Ньютона є методом другого порядку, тобто використовують розрахунки других похідних мінімізуємої на Е_n функції f.

,

де f – двічі диференційована на Е_n функція.

У його модифікації у «квазі – ньютонівських» алгоритмах, матриця других похідних за допомогою інформації про значення градієнтів функції f і ці модифікації є методами першого порядку.

Опис методу Ньютона:

Припустимо, що функція f – опукла та двічі диференційована на Е_n, при чому матриця других похідних від х не вироджена на Е_n.

У методі Ньютона послідовність генерується виходячи з наступного:

- з визначення двічі диференційованої функції для чергової точки х _k маємо:

Для визначення наступної точки х _k+1 мінімізуюча функція f_k(х) є квадратичною частиною прирощення f(х)- f (х_k), тобто вирішується задача

(1)

Зрозуміло, що .

Так як необхідною і достатньою умовою опуклості функції є додатна матриця її других похідних, а функція f опукла за умовою, тоді f_k також опукла, тому з необхідної і достатньої умови оптимально опуклої функції слідує:

(2)

Якщо матриця Гессе функції f (х_k) системи лінійних алгебраїчних рівнянь не вироджена, то отримуємо:

(3)

Дане співвідношення визначає метод Ньютона мінімізації функції f.

Цей метод співпадає з відомим з курсу математичного аналізу методом Ньютона, вирішуємо систему рівнянь f ^’(x)=0.