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

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

Нехай функція де U задана множина в , зокрема, може бути . Опишемо метод Ньютона для розв'язування задачі мінімізації на U полягає у наступному. Нехай маємо деяке початкове наближення . Якщо вже відоме m - те наближення , то приріст функції у точці можна подати у вигляді:

Візьмемо квадратичну частину цього приросту:

і визначимо допоміжне наближення з умов

Наступне наближення шукатимемо у вигляді

В залежності від способу вибору величини в отримаємо різні варіанти методу Ньютона. Зокрема можна взяти , m =0, 1, 2…Тоді з випливає .

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

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

Приклад 1. Розв’яжемо методом Ньютона задачу мінімізації з прикладу 4.1.

Розв’язування. У цьому випадку

.

На першому кроці

, .

За формулою визначаємо точку :

.

Отже, .

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

Після четвертого кроку отримаємо

.

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

Отже

.