Метод сполучених градієнтів онлайн. Метод сполучених градієнтів – математичний апарат

Метод сполучених градієнтів знаходження максимуму квадратичної форми має кілька модифікацій.

1. Одна з них виходить безпосередньо з розглянутого вище процесу, якщо замінити максимізацію функції на гіперпросторі знаходженням максимуму на прямий вид (16.15). Як було показано в попередньому пункті, результат від цього не зміниться, оскільки ці максимуми збігаються.

Алгоритм виходить таким (модифікація I):

А. Початковий крок.

1) Знаходиться градієнт функції у довільній точці;

2) належить ;

3) знаходиться точка , що доставляє максимум функції на прямий ( – параметр).

Б. Загальний крок. Нехай вже знайдено крапки .

1) знаходиться градієнт функції в точці.

2) належить

В. Зупинення алгоритму. Процес обривається в той момент, коли градієнт обернеться в нуль, тобто досягається максимум на всьому просторі.

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

У реальних умовах, при обмеженій точності обчислень, процес пошуку максимуму слід зупинити не при точному зверненні на нуль градієнта, а в той момент, коли градієнт стане досить малим. При цьому насправді може знадобитися більше кроків. Докладніше ці питання будуть розглянуті нижче.

Щоб надати алгоритму «конструктивнішу» форму, знайдемо формулу, що визначає точку максимуму квадратичної форми на прямій .

Підставляючи рівняння прямої у вираз функції, отримаємо

де - градієнт у точці. Максимізуючи по , отримаємо

і відповідно

. (16.16)

Таким чином, обчислення у пункті 3) алгоритму може бути здійснено за формулою

.

2. Більш відома модифікація методу, коли для обчислення чергового напрями використовуються вектори і замість і .

Розглянемо систему векторів, колінеарних відповідно до векторів (тобто при деяких дійсних). Для векторів і зберігається умова ортогональності

При . (16.17)

Крім того, з (16.11) випливає, що

При . (16.18)

Зрештою, залишається в силі співвідношення типу (16.9)

. (16.19)

Помножуючи праву та ліву частини (16.19) на та враховуючи (16.17) та (16.18), отримаємо при

звідки при . При отримаємо

. (16.20)

Співвідношення (16.20) визначає з точністю до довільного множника через ц. При виведенні (16.20) використовувалися лише співвідношення (16.17), (16.18), (16.19). Тому процес побудови векторів може розглядатися як процес ортогоналізації векторів.

Вважаючи (16.20) і , отримаємо конкретну систему векторів , колінеарних . Кожен вектор задає напрям прямий, що виходить з , на якій лежить . Алгоритм, таким чином, прийме наступний вигляд(Модифікація II).

А. Початковий крок, такий самий як і модифікації I.

Б. Нехай вже знайдено точку та напрямок.

1) Знаходиться градієнт функції у точці;

2) належить

,

; (16.21)

3) знаходиться точка , що доставляє умовний максимум на прямий

за формулою

. (16.22)

Формули (16.21) та (16.22) можуть бути перетворені. Так, вважаючи

маємо з (16.22)

,

звідки отримуємо, застосовуючи (16.12),

. (16.23)

З іншого боку, оскільки

з (16.21) маємо

і таким чином,

Нарешті, з (16.21), (16.23) та (16.24) отримуємо

.

Таким чином, формули (16.21) та (16.22) можуть бути записані у вигляді

,

. (16.26)

Збіг результатів дії за формулами (16.21) і (16.22), з одного боку, і (16.25), (16.26), з іншого, може бути критерієм правильності обчислень.

3. Метод сполучених градієнтів може бути застосований і для максимізації функцій, що не є квадратичними. Відомо, однак, що поблизу максимуму досить гладкі функції, як правило, добре апроксимуються квадратичною функцією, наприклад, за допомогою розкладання в ряд Тейлора. При цьому зазвичай передбачається, що коефіцієнти апроксимуючої квадратичні функціїневідомі, але для будь-якої точки можна знайти градієнт функції .

При цьому пункт 1) алгоритму може бути виконаний без змін, пункт 2) повинен виконуватися за формулою (16.25), оскільки до цієї формули не входить явно матриця , а пункт 3), знаходження умовного максимуму на прямій, може бути виконаний одним з відомих способівнаприклад, методом Фібоначчі. Застосування методу сполучених градієнтів дає зазвичай значно швидшу збіжність до максимуму проти методами якнайшвидшого спуску, Гаусса – Зайделя та інших.

4. Що буде, якщо застосувати метод сполучених градієнтів для максимізації квадратичної форми з позитивно напіввизначеною формою?

Якщо квадратична формапозитивно напіввизначена, то, як відомо з лінійної алгебри, у відповідній системі координат функція набуде вигляду

,

де всі та деякі з . У цьому функція має максимум, якщо виконано умова: коли , те й . Легко бачити, що максимум у цьому випадку досягається в цілому гіперпросторі. А саме, нехай, наприклад, при , що змінюється від 1 до , , а при , що змінюється від до , і . Тоді максимум досягається в точках з координатами при і довільними значеннями при . Вони утворюють гіперпростір розмірності.

Якщо ж за деяких , a , то функція немає максимуму і зростає необмежено. Справді, нехай, наприклад, і ; тоді, якщо покласти при і спрямувати до , то, очевидно, і зростатиме до нескінченності.

Виявляється, що метод сполучених градієнтів (при точному рахунку) дозволяє в першому випадку досягти максимуму не більше ніж за кроків, де число не рівних нулю, а другий випадок лише через кроків виводить на напрям, яким функція зростає необмежено.

У вихідній системі координат функція має вигляд

,

причому матриця вироджена і має ранг. При цьому, як і раніше, обіг градієнта в нуль є критерій досягнення максимуму, а ортогональність градієнта гіперпростору - критерій умовного екстремуму на гіперпросторі.

Розглянемо застосування методу сполучених градієнтів у формі ІІ у цьому випадку. Тут доводиться змінити умову зупинки, тобто тепер можливо, що при обчисленні довжини кроку

знаменник може звернутися в нуль (при обчисленні значення величина також входить у знаменник, але якщо вона дорівнює нулю, то вже попередній крокнеможливий).. Насправді нехай при ортогональному гіперпросторі

і оскільки , то квадратична частина позитивно визначено. Але, як відомо з лінійної алгебри, це можливо тільки в тому випадку, коли розмірність простору менша або дорівнює рангу матриці.

Отже, зупинка обов'язково відбудеться при .

Градієнтні методи, що базуються лише на обчисленні градієнта R(x), є методами першого порядку, тому що на інтервалі кроку вони замінюють нелінійну функцію R(x) лінійної.

Більш ефективними можуть бути методи другого порядку, які використовують при обчисленні не тільки перші, а й другі похідні від R(x) у поточній точці. Однак у цих методів є свої проблеми, які важко вирішити – обчислення других похідних у точці, до того ж далеко від оптимуму матриця других похідних може бути погано обумовлена.

Метод сполучених градієнтів є спробою поєднати переваги методів першого та другого порядку з виключенням їх недоліків. на початкових етапах(далеко від оптимуму) метод веде себе як метод першого порядку, а в околицях оптимуму наближається до методів другого порядку.

Перший крок аналогічний першому кроці методу якнайшвидшого спуску, другий і наступний кроки вибираються щоразу у напрямі, утвореному вигляді лінійної комбінації векторів градієнта у цій точці і попереднього напрями.

Алгоритм методу можна записати так (у векторній формі):

x 1 = x 0 - h grad R (x 0),

x i +1 = x i - h.

Розмір α може бути наближено знайдена з виразу

Алгоритм працює в такий спосіб. З початкової точки х 0 шукають min R(x) у напрямку градієнта (методом якнайшвидшого спуску), потім, починаючи зі знайденої точки і далі, напрямок пошуку min визначається за другим виразом. Пошук мінімуму за напрямом може здійснюватися у будь-який спосіб: можна використовувати метод послідовного сканування без корекції кроку сканування при переході мінімуму, тому точність досягнення мінімуму за напрямом залежить від величини кроку h.

Для квадратичної функції R(x) рішення може бути знайдено за пкроків (п- Розмірність завдання). Для інших функцій пошук буде повільнішим, а в ряді випадків може взагалі не досягти оптимуму внаслідок сильного впливуобчислювальних помилок.

Одна з можливих траєкторій пошуку мінімуму двовимірної функції методом сполучених градієнтів наведена на рис. 1.

Алгоритм методу сполучених градієнтів для пошуку мінімуму.

Початковий етап.Виконання градієнтного способу.

Задаємо початкове наближення x 1 0 ,х 2 0 . Визначаємо значення критерію R(x 1 0 ,х 2 0). Покласти до = 0 і перейти до кроку 1 початкового етапу.

Крок 1. і
.

Крок 2Якщо модуль градієнта

Крок 3

x k+1 = x k – h grad R(x k)).

Крок 4. R(x 1 k +1 , х 2 k +1). Якщо R(x 1 k +1 , х 2 k +1)< R(x 1 k , х 2 k), то покласти k = k+1 і перейти до кроку 3. Якщо R(x 1 k +1 , х 2 k +1) ≥ R(x 1 k , х 2 k), то перейти до основного етапу.

Основний етап.

Крок 1.Обчислити R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k , x 2 k + g), R(x 1 k , x 2 k) . Відповідно до алгоритму з центральної або парної проби обчислити значення приватних похідних і . Обчислити значення модуля градієнта
.

Крок 2Якщо модуль градієнта
, Розрахунок зупинити, а точкою оптимуму вважати точку (x 1 k , x 2 k). В іншому випадку перейти до кроку 3.

Крок 3Обчислити коефіцієнт α відповідно до формули:

Крок 4.Виконати робочий крок, розрахувавши за формулою

x k +1 = x k - h.

Крок 5.Визначити значення критерію R(x 1 k +1 , х 2 k +1). Покласти k = k+1 та перейти до кроку 1.

приклад.

Для порівняння розглянемо рішення попереднього прикладу. Перший крок робимо методом якнайшвидшого спуску (табл. 5).

Таблиця 5

Знайдено найкращу точку. Обчислюємо похідні у цій точці: dR/ dx 1 = –2.908; dR/ dx 2 =1.600; обчислюємо коефіцієнт α, що враховує вплив градієнта у попередній точці: α = 3,31920 ∙ 3,3192/8,3104 2 =0,160. Робимо робочий крок відповідно до алгоритму методу, отримуємо х 1 = 0,502, х 2 = 1,368. Далі все повторюється аналогічно. Нижче, у табл. 6 наведено поточні координати пошуку наступних кроків.

Таблиця 6

Метод призначений на вирішення завдання (5.1) і належить класу методів першого порядку. Метод є модифікацією методу якнайшвидшого спуску (підйому) і автоматично враховує особливості цільової функції, прискорюючи збіжність.

Опис алгоритму

Крок 0. Вибирається точка початкового наближення , параметр довжини кроку , точність рішенняі обчислюється початковий напрямок пошуку.

Крок k. на k-м кроці знаходиться мінімум (максимум) цільової функції на прямій, проведеній з точки за напрямом . Знайдена точка мінімуму (максимуму) визначає чергове k-е наближення, після чого визначається напрямок пошуку

Формула (5.4) може бути переписана в еквівалентному вигляді

.

Алгоритм завершує свою роботу, як тільки виконається умова; як рішення приймається значення останнього отриманого наближення.

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

Метод призначений на вирішення завдання (5.1) і належить класу методів другого порядку. У основі методу лежить розкладання Тейлора цільової функції і те, що у точці екстремуму градієнт функції дорівнює нулю, тобто .

Дійсно, нехай деяка точка лежить досить близько до точки шуканого екстремуму. Розглянемо i-ю компоненту градієнта цільової функції і розкладемо її в точці за формулою Тейлора з точністю до похідних першого порядку:

. (5.5)

Формулу (5.5) перепишемо у матричній формі, враховуючи при цьому, що :

де матриця Гессе цільової функції у точці.

Припустимо, що матриця Гессе невироджена. Тоді вона має зворотну матрицю. Помножуючи обидві частини рівняння (5.6) на ліворуч, отримаємо , звідки

. (5.7)

Формула (5.7) визначає алгоритм методу Ньютона: перерахунок наближень на k

Алгоритм закінчує свою роботу, як тільки виконається умова

,

де задана точність розв'язання; як рішення приймається значення останнього отриманого наближення.

Метод Ньютона-Рафсона

Метод є методом першого порядку та призначений для вирішення систем nне лінійних рівнянь c nневідомими:

Зокрема, цей метод може бути застосований при пошуку стаціонарних точок цільової функції задачі (5.1), коли необхідно вирішити систему рівнянь із умови .

Нехай точка є рішенням системи (5.9), а точка розташована поблизу . Розкладаючи функцію у точці за формулою Тейлора, маємо

звідки (за умовою) випливає

, (5.11)

де матриця Якобі вектор-функції. Припустимо, що матриця Якобі невироджена. Тоді вона має зворотну матрицю. Помножуючи обидві частини рівняння (5.11) на ліворуч, отримаємо , звідки

. (5.12)

Формула (5.12) визначає алгоритм методу Ньютона-Рафсона: перерахунок наближень на k-ї ітерації виконується відповідно до формули

У разі однієї змінної, коли система (5.9) вироджується в єдине рівняння , формула (5.13) набуває вигляду

, (5.14)

де значення похідної функції у точці.

На рис. 5.2 показана схема реалізації методу Ньютона-Рафсон при пошуку рішення рівняння .

Зауваження 5.1.Схожість чисельних методів, зазвичай, сильно залежить від початкового наближення.

Зауваження 5.2.Методи Ньютона та Ньютона-Рафсона вимагають великого обсягу обчислень (треба на кожному кроці обчислювати та звертати матриці Гессе та Якобі).

Зауваження 5.3.При використанні методів обов'язково слід враховувати можливість наявності багатьох екстремумів у цільової функції. мультимодальності).

ЛІТЕРАТУРА

1. Афанасьєв М.Ю., Суворов Б.П.Дослідження операцій на економіці: Навчальний посібник. - М.: Економічний факультетМДУ, ТЕІС, 2003 - 312 с.

2. Базара М, Шетті До.Нелінійне програмування. Теорія та алгоритми: Пер. з англ. - М.: Світ, 1982 - 583 с.

3. Берман Г.Н. Збірник завдань з курсу математичного аналізу: Навчальний посібник для вузів - СПб: « Спеціальна Література», 1998. - 446 с.

4. Вагнер Г.Основи дослідження операцій: У трьох томах. Пров. з англ. - М.: Світ, 1972. - 336 с.

5. Вентцель О.С. Дослідження операцій. Завдання, принципи, методологія - М.: Наука, 1988. - 208 с.

6. Демидович Б.П.Збірник завдань та вправ з математичного аналізу . - М.: Наука, 1977. - 528 с.

7. Дегтярьов Ю.І.Дослідження операцій. - М.: Вищ. шк., 1986. - 320 с.

8. Нурєєв Р.М.Збірник завдань з мікроекономіки. - М.: НОРМА, 2006. - 432 с.

9. Солодовников А.С., Бабайцев В.А., Браїлов А.В.Математика економіки: Підручник: У 2-х год. – М.:Фінанси і статистика, 1999. – 224 з.

10. Таха Х.Введення у дослідження операцій, 6-те вид.: Пер. з англ. - М.: Видавничий дім "Вільямс", 2001. - 912 с.

11. Хіммельблау Д.Прикладне нелінійне програмування: Пров. з англ. - М.: Світ, 1975 - 534 с.

12. Шикін Є.Ст, Шікіна Г.Є.Дослідження операцій: Підручник - М.: ТК Велбі, Вид-во Проспект, 2006. - 280 с.

13. Дослідження операцій на економіці: Навч. посібник для вузів/Н.Ш.Кремер, Б.А.Путко, І.М.Трішин, М.М.Фрідман; За ред. проф. Н.Ш. Кремера. - М.: Банки та біржі, ЮНИТИ, 1997. - 407 с.

14. Матриці та вектори: Навч. посібник/Рюмкін В.І. - Томськ: ТГУ, 1999. - 40 с.

15. Системи лінійних рівнянь: Навч. посібник / Рюмкін В.І. - Томськ: ТГУ, 2000. - 45 с.

Визначення лінійної та нелінійних функційдив. у розділі 1.2

Розглянуті вище градієнтні способи шукають точку мінімуму функції в загальному випадкулише за біс кінцеве числоітерацій. Метод сполучених градієнтів формує напрями пошуку, більшою мірою відповідні геометрії функції, що мінімізується. Це суттєво збільшує швидкість їх збіжності та дозволяє, наприклад, мінімізувати квадратичну функцію.

f(x) = (х, Нх) + (b, х) + а

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

За визначенням, два n-мірних векторх і у називають сполученими по відношенню до матриці H (або H-сполученими), якщо скалярний добуток(x, Ну) = 0. Тут Н – симетрична позитивно визначена матриця розміром пхп.

Однією з найістотніших проблем у методах сполучених градієнтів є проблема ефективної побудови напрямків. Метод Флетчера-Рівса вирішує цю проблему шляхом перетворення кожному кроці антиградієнта -f(x[k]) у напрям p[k], H-пов'язане з раніше знайденими напрямками р, р, ..., р. Розглянемо спочатку цей метод стосовно задачі мінімізації квадратичної функції.

Напрямки р[k] обчислюють за формулами:

p[k] = -f'(x[k])+k-1p, k >= 1; p = -f '(x).

Величини k-1 вибираються так, щоб напрямки p[k], р були H-сполученими:

(p [k], Hp) = 0.

В результаті для квадратичної функції

ітераційний процес мінімізації має вигляд

x = x [k] + akp [k],

де р [k] - напрямок спуску на k-му кроці; аk – величина кроку. Остання вибирається з умови мінімуму функції f(х) по напрямку руху, тобто в результаті розв'язання задачі одномірної мінімізації:

f(х[k] + аkр[k]) = f(x[k] + ар[k]).

Для квадратичної функції

Алгоритм методу сполучених градієнтів Флетчера-Рівса полягає у наступному.

1. У точці х обчислюється p = -f '(x).

2. На k-му кроці за наведеними вище формулами визначаються крок аk. та точка х.

3. Обчислюються величини f(x) та f'(x).

4. Якщо f'(x) = 0, то точка х є точкою мінімуму функції f(х). В іншому випадку визначається новий напрямок p із співвідношення

та здійснюється перехід до наступної ітерації. Ця процедура знайде мінімум квадратичної функції не більше ніж за п кроків. При мінімізації неквадратичних функцій метод Флетчера-Рівса з кінцевого стає ітеративним. У такому разі після (п+1)-ї ітерації процедури 1-4 циклічно повторюються із заміною х на х[п+1] , а обчислення закінчуються при де - задане число. При цьому застосовують таку модифікацію методу:

x = x [k] + akp [k],

p[k] = -f'(x[k])+k-1p, k >= 1;

f(х[k] + akp[k]) = f(x[k] + ap[k];

Тут I-множина індексів: I = (0, n, 2п, Зп, ...), тобто оновлення методу відбувається через кожні п кроків.

Геометричний змістметоду сполучених градієнтів полягає у наступному (Рис. 1.19). Із заданої початкової точки х здійснюється спуск у напрямку р = -f"(x). У точці х визначається вектор-градієнт f"(x). Оскільки х є точкою мінімуму функції в напрямку р, то f'(х) ортогональний вектор р. Потім знаходиться вектор р , H-пов'язаний до р . Далі знаходиться мінімум функції вздовж напрямку р і т. д.

Мал. 1.19. Траєкторія спуску у методі сполучених градієнтів

Методи сполучених напрямів є одними з найефективніших для вирішення задач мінімізації. Проте слід зазначити, що вони чутливі до помилок, що виникають у процесі рахунку. При великому числізмінних похибка може настільки зрости, що процес доведеться повторювати навіть для квадратичної функції, тобто процес для неї не завжди вкладається в п кроків.

Чисельні методибезумовної оптимізації другого порядку, варіанти алгоритмів методу Ньютона

Особливості методів другого порядку. Методи безумовної оптимізації другого порядку використовують другі приватні похідні функції f(х), що мінімізується. Суть цих методів ось у чому.

Необхідною умовоюекстремуму функції багатьох змінних f(x) у точці х* є рівність нулю її градієнта у цій точці:

Розкладання f'(х) в околиці точки х[k] у ряд Тейлора з точністю до членів першого порядку дозволяє переписати попереднє рівняння у вигляді

f"(x) f'(x[k]) + f"(x[k]) (х - х[k]) 0.

Тут f"(x[k]) Н(х[k]) - матриця других похідних (матриця Гессе) мінімізованої функції. Отже, ітераційний процес для побудови послідовних наближень до вирішення задачі мінімізації функції f(x) описується виразом

x x[k] - H-1(x[k]) f'(x[k]) ,

де H-1(x[k]) - зворотна матрицядля матриці Гессе, а H-1(x[k])f'(x[k]) р[k] - напрямок спуску.

Отриманий метод мінімізації називають методом Ньютона. Очевидно, що в даному методівеличина кроку вздовж напрямку р [k] належить рівної одиниці. Послідовність точок (х[k]), одержувана в результаті застосування ітераційного процесу, при певних припущеннях сходить до деякої стаціонарної точки x функції f(x). Якщо матриця Гесс Н(х*) позитивно визначена, точка х* буде точкою суворого локального мінімуму функції f(x). Послідовність x[k] сходить до точки х* тільки в тому випадку, коли матриця Гессе цільової функції позитивно визначена на кожній ітерації.

Якщо функція f(x) є квадратичною, незалежно від початкового наближення х і ступеня яружності, за допомогою методу Ньютона її мінімум знаходиться за один крок. Це тим, що напрям спуску р[k] H-1(x[k])f'(x[k]) у будь-яких точках х завжди збігається з напрямом у точку мінімуму х*. Якщо ж функція f(x) не квадратична, але опукла, метод Ньютона гарантує її монотонне зменшення від ітерації до ітерації. При мінімізації яружних функцій швидкість збіжності методу Ньютона вищу проти градієнтними методами. В такому випадку вектор р[k] не вказує напрямок у точку мінімуму функції f(x), проте має велику складову вздовж осі яру і значно ближче до напрямку мінімум, ніж антиградієнт.

Істотним недоліком методу Ньютона є залежність збіжності для невипуклих функцій від початкового наближення x. Якщо х знаходиться досить далеко від точки мінімуму, то метод може розходитися, тобто при проведенні ітерації кожна наступна точка буде віддаленішою від точки мінімуму, ніж попередня. Збіжність методу, незалежно від початкового наближення, забезпечується вибором як напрями спуску р[k] H-1(x[k])f’(x[k]), а й величини кроку а вздовж цього напряму. Відповідний алгоритм називають методом Ньютона з регулюванням кроку. Ітераційний процес у такому разі визначається виразом

x x[k] - akH-1(x[k])f'(x[k]).

Величина кроку аk вибирається з умови мінімуму функції f(х) а в напрямку руху, тобто в результаті вирішення задачі одномірної мінімізації:

f(x[k] – ak H-1(x[k])f'(x[k]) (f(x[k] - aH-1(x[k])f'(x[k])) ).

Такий варіант алгоритму називають методом Ньютона-Рафсона. Графічна інтерпретація цього варіанта методу Ньютона представлена ​​на рис. 1.20. На виносних елементах малюнка наведено графіки одновимірних функцій, що підлягають оптимізації для визначення кроку.

Мал. 1.20. Геометрична інтерпретаціяметоду Ньютона-Рафсона

Алгоритм методу Ньютона-Рафсона ось у чому. Частина дій виконується на початок ітераційного процесу. А саме необхідно отримати вектор формул, що становлять градієнт f'([x]) (тобто вектор перших приватних похідних) та матрицю формул, що становлять матрицю Гессе H(x) (тобто матрицю других приватних похідних). Далі в ітераційному циклі ці формули підставляються значення компонент вектора x і ці масиви стають масивами чисел.

1. У початковій точціх обчислюється вектор, що визначає напрямок спуску p - H-1(x)f'(). Тим самим багатомірна задача зводиться до завдання одномірної оптимізації.

2. На k-й ітерації визначається крок аk (за схемою, зображеною на рис. 1.20, для цього вирішується задача одновимірної оптимізації) та точка х.

3. Обчислюється величина f(x).

4. Перевіряються умови виходу із підпрограми, що реалізує даний алгоритм. Ці умови аналогічні умов виходу з підпрограми при методі якнайшвидшого спуску. Якщо ці умови виконуються, здійснюється припинення обчислень. В іншому випадку обчислюється новий напрямок

р –H-1(x[k])f'([k])

і здійснюється перехід до наступної ітерації, тобто крок 2.

Кількість обчислень на ітерації методом Ньютона, зазвичай, значно більше, ніж у градієнтних методах. Це пояснюється необхідністю обчислення та обігу матриці других похідних цільової функції (або розв'язання системи рівнянь, що потребує менше трудовитрат). Однак на отримання рішення досить високим ступенемточності за допомогою методу Ньютона зазвичай потрібно набагато менше ітерацій, ніж під час використання градієнтних методів. Через це метод Ньютона значно ефективніший. Він має надлінійну або квадратичну швидкість збіжності в залежності від вимог, яким задовольняє функція f(x), що мінімізується. Проте в деяких завданнях трудомісткість ітерації методом Ньютона може виявитися дуже великою за рахунок необхідності обчислення матриці других похідних функції, що мінімізується, що вимагатиме витрат значної кількості машинного часу.

У ряді випадків доцільно комбіноване використання градієнтних методів та методу Ньютона. На початку процесу мінімізації, коли точка х знаходиться далеко від точки екстремуму х*, можна застосовувати будь-який варіант градієнтних методів. Далі при зменшенні швидкості збіжності градієнтного методу можна перейти до методу Ньютона. Або внаслідок накопичення помилок у процесі рахунку матриця Гессе на деякій ітерації може бути негативно визначеною або її не можна буде звернути. У разі в підпрограмах оптимізації належить H-1(x[k]) Е, де Е - одинична матриця. Ітерація у своїй здійснюється методом якнайшвидшого спуску.

В іншій модифікації методу Ньютона, що отримала назву метод Левенберга - Маркардта (метод Ньютона з регулюванням матриці) для забезпечення позитивної визначеності матриці Гессе в точках послідовності використовується регулювання цієї матриці. У методі Левенберга - Маркардта точки будуються за законом: , де - Послідовність позитивних чиселщо забезпечують позитивну визначеність матриці. Зазвичай як береться значення значно більше найбільшого елементаматриці. Так у ряді стандартних програм належить. Якщо, то, в іншому випадку Очевидно, що якщо, то метод Левенберга - Маркардта являє собою метод Ньютона, а якщо велике, то оскільки при великих методЛевенберг - Маркардт близький до градієнтного методу. Тому, підбираючи значення параметра, можна домогтися, щоб метод Левенберга - Маркардта сходився