Метод Ньютона з Параметром: Що Варто Знати Про Цей Підхід

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

Метод Ньютона з Параметром: Як Будують Напрям Переходу

Нехай задано функцію кількох змінних

\[
f(\bar{x})=f(x_1,x_2,\dots,x_n),
\]

де \( \bar{x} \) — вектор змінних. Потрібно знайти таку точку, у якій функція набуває локально найменшого значення. Але як визначити, у який бік треба рухатися від поточного наближення? Саме це питання і розв’язує перший крок методу.

Передусім поблизу точки \( \bar{x}_k \) функцію замінюють її квадратичним наближенням. Тобто замість аналізу всієї функції використовують локальну модель, яка точніше описує її поведінку біля поточної точки. Це важливо, адже в задачах мінімізації потрібно враховувати не лише напрям зміни функції, а й форму її поверхні.

Таке наближення записують так:

\[
f(\bar{x}) \approx f(\bar{x}_k)
+ \nabla f(\bar{x}_k)^T \cdot (\bar{x}-\bar{x}_k)
+ \frac{1}{2} \cdot (\bar{x}-\bar{x}_k)^T \cdot H(\bar{x}_k) \cdot (\bar{x}-\bar{x}_k).
\]

Тут використовують дві головні величини. Перша — це градієнт \( \nabla f(\bar{x}_k) \), який показує, як функція змінюється поблизу точки \( \bar{x}_k \). Друга — це матриця Гессе \( H(\bar{x}_k) \), яка описує локальну кривизну поверхні. Саме завдяки другим похідним метод Ньютона належить до методів другого порядку.

Далі з цієї квадратичної моделі визначають вектор \( \Delta \bar{x}_k \), який задає ньютонівський приріст, тобто напрям переходу від поточного наближення. Для цього розв’язують систему

\[
H(\bar{x}_k)\cdot \Delta \bar{x}_k=-\nabla f(\bar{x}_k).
\]

Якщо матриця \( H(\bar{x}_k) \) є оборотною, тоді

\[
\Delta \bar{x}_k=-H(\bar{x}_k)^{-1}\cdot \nabla f(\bar{x}_k).
\]

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

Демпфований Метод Ньютона: Як Отримують Нове Наближення

Після того як ньютонівський приріст \( \Delta \bar{x}_k \) уже знайдено, постає наступне запитання: чи завжди варто переходити до нової точки на весь цей крок? Саме тут і з’являється параметр.

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

Тоді нове наближення визначають за формулою

\[
\bar{x}_{k+1}=\bar{x}_k+\alpha_k\cdot \Delta \bar{x}_k.
\]

Підставляючи сюди вираз для \( \Delta \bar{x}_k \), одержуємо

\[
\bar{x}_{k+1}=\bar{x}_k-\alpha_k\cdot H(\bar{x}_k)^{-1}\cdot \nabla f(\bar{x}_k).
\]

Саме ця формула є основною для методу Ньютона з параметром у задачах мінімізації функції кількох змінних.

Тут важливо чітко розрізняти дві ролі. Вектор \( \Delta \bar{x}_k \) визначає напрям переходу, а параметр \( \alpha_k \) визначає, яку частину цього кроку виконують.

Якщо \( \alpha_k=1 \), то отримуємо класичний метод Ньютона. Якщо ж \( 0<\alpha_k<1 \), то крок зменшується, і метод набуває демпфованого характеру.

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

Метод Ньютона: Коли Завершують Процес і Що Вважають Результатом

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

\[
\bar{x}_0,\ \bar{x}_1,\ \bar{x}_2,\ \dots,\ \bar{x}_k,\ \dots
\]

обчислюється крок за кроком.

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

\[
\|\nabla f(\bar{x}_k)\| \le \varepsilon,
\]

де \( \varepsilon>0 \) — заздалегідь задана точність.

Що означає ця умова? Вона показує, що в точці \( \bar{x}_k \) функція вже практично не змінюється. Отже, поточне наближення можна вважати достатньо близьким до точки локального мінімуму.

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

\[
f(\bar{x}_{k+1})<f(\bar{x}_k).
\]

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

Після виконання умови зупинки останню знайдену точку \( \bar{x}_k \) приймають за наближене значення точки локального мінімуму, а значення \( f(\bar{x}_k) \) — за наближене мінімальне значення функції.

Отже, метод Ньютона з параметром, або демпфований метод Ньютона, поєднує три послідовні ідеї. Спочатку він будує ньютонівський приріст за допомогою градієнта і матриці Гессе. Далі формує нове наближення з урахуванням параметра кроку. Після цього перевіряє умову зупинки й визначає наближений результат. Саме така побудова робить цей метод важливим інструментом у чисельних методах мінімізації функції кількох змінних.

Метод Ньютона з Параметром: Практичний Приклад Для Функції Двох Змінних

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

Приклад 1. Знайти мінімальне значення функції \( f(x_1,x_2)=x_1^4-3\cdot x_1^2+x_2^2 \) з точністю \( \varepsilon=0.1 \), використовуючи метод Ньютона з параметром

Розглянемо функцію

\[
f(x_1,x_2)=x_1^4-3\cdot x_1^2+x_2^2.
\]

Для цієї функції застосуємо метод Ньютона з параметром. Візьмемо початкове наближення

\[
\bar{x}_0=
\begin{pmatrix}
0.8\\
0
\end{pmatrix},
\]

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

Спочатку знайдемо градієнт функції:

\[
\nabla f(x_1,x_2)=
\begin{pmatrix}
\frac{\partial f}{\partial x_1}\\
\frac{\partial f}{\partial x_2}
\end{pmatrix}
=
\begin{pmatrix}
4\cdot x_1^3-6\cdot x_1\\
2\cdot x_2
\end{pmatrix}.
\]

Далі знайдемо матрицю Гессе:

\[
H(x_1,x_2)=
\begin{pmatrix}
\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1\partial x_2}
\\[6pt]
\frac{\partial^2 f}{\partial x_2\partial x_1} & \frac{\partial^2 f}{\partial x_2^2}
\end{pmatrix}
=
\begin{pmatrix}
12\cdot x_1^2-6 & 0\\
0 & 2
\end{pmatrix}.
\]

Тепер обчислимо градієнт і матрицю Гессе в початковій точці \( \bar{x}_0=(0.8,0)^T \):

\[
\nabla f(0.8,0)=
\begin{pmatrix}
4\cdot 0.8^3-6\cdot 0.8\\
2\cdot 0
\end{pmatrix}
=
\begin{pmatrix}
-2.752\\
0
\end{pmatrix},
\\[6pt]
H(0.8,0)=
\begin{pmatrix}
12\cdot 0.8^2-6 & 0\\
0 & 2
\end{pmatrix}
=
\begin{pmatrix}
1.68 & 0\\
0 & 2
\end{pmatrix}.
\]

Для знаходження ньютонівського приросту використаємо систему

\[
H(\bar{x}_k)\cdot \Delta \bar{x}_k=-\nabla f(\bar{x}_k).
\]

Отже, для початкової точки маємо

\[
\Delta \bar{x}_0=-H(0.8,0)^{-1}\cdot \nabla f(0.8,0).
\]

Оскільки матриця \( H(0.8,0) \) є діагональною, її обернена матриця має вигляд

\[
H(0.8,0)^{-1}=
\begin{pmatrix}
\frac{1}{1.68} & 0\\
0 & \frac{1}{2}
\end{pmatrix}.
\]

Тоді

\[
\Delta \bar{x}_0=
–
\begin{pmatrix}
\frac{1}{1.68} & 0\\
0 & \frac{1}{2}
\end{pmatrix}
\cdot
\begin{pmatrix}
-2.752\\
0
\end{pmatrix}
=
\begin{pmatrix}
1.638095\\
0
\end{pmatrix}.
\]

Тепер важливо звернути увагу на один момент. Якщо тут використати класичний метод Ньютона, тобто взяти повний крок \( \alpha_0=1 \), то отримали б точку

\[
\tilde{\bar{x}}_1=
\bar{x}_0+\Delta \bar{x}_0=
\begin{pmatrix}
0.8\\
0
\end{pmatrix}
+
\begin{pmatrix}
1.638095\\
0
\end{pmatrix}
=
\begin{pmatrix}
2.438095\\
0
\end{pmatrix}.
\]

Обчислимо значення функції в початковій і цій новій точці:

\[
f(0.8,0)=0.8^4-3\cdot 0.8^2=-1.5104,
\\[6pt]
f(2.438095,0)\approx 2.438095^4-3\cdot 2.438095^2\approx 17.4889.
\]

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

\[
\alpha_k=\frac{1}{4}.
\]

Тоді ітераційна формула матиме вигляд

\[
\bar{x}_{k+1}=\bar{x}_k+\frac{1}{4}\cdot \Delta \bar{x}_k.
\]

Для першої ітерації одержуємо

\[
\bar{x}_1=
\bar{x}_0+\frac{1}{4}\cdot \Delta \bar{x}_0
=
\begin{pmatrix}
0.8\\
0
\end{pmatrix}
+
\frac{1}{4}
\cdot
\begin{pmatrix}
1.638095\\
0
\end{pmatrix}
=
\begin{pmatrix}
1.209524\\
0
\end{pmatrix}.
\]

Перевіримо значення функції:

\[
f(1.209524,0)\approx 1.209524^4-3\cdot 1.209524^2\approx -2.248627.
\]

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

Продовження ітераційного процесу

Переходимо до другої ітерації. Обчислюємо градієнт у точці \( \bar{x}_1 \):

\[
\nabla f(1.209524,0)=
\begin{pmatrix}
4\cdot 1.209524^3-6\cdot 1.209524\\
0
\end{pmatrix}
\approx
\begin{pmatrix}
-0.179262\\
0
\end{pmatrix}.
\]

Матриця Гессе в цій точці дорівнює

\[
H(1.209524,0)=
\begin{pmatrix}
12\cdot 1.209524^2-6 & 0\\
0 & 2
\end{pmatrix}
\approx
\begin{pmatrix}
11.555374 & 0\\
0 & 2
\end{pmatrix}.
\]

Тоді ньютонівський приріст буде таким:

\[
\Delta \bar{x}_1=
–
H(1.209524,0)^{-1}\cdot \nabla f(1.209524,0)
\approx
\begin{pmatrix}
0.015513\\
0
\end{pmatrix}.
\]

Отже,

\[
\bar{x}_2=
\bar{x}_1+\frac{1}{4}\cdot \Delta \bar{x}_1
=
\begin{pmatrix}
1.209524\\
0
\end{pmatrix}
+
\frac{1}{4}
\cdot
\begin{pmatrix}
0.015513\\
0
\end{pmatrix}
=
\begin{pmatrix}
1.213402\\
0
\end{pmatrix}.
\]

Переходимо до третьої ітерації. Для точки \( \bar{x}_2 \) маємо

\[
\nabla f(1.213402,0)\approx
\begin{pmatrix}
-0.134228\\
0
\end{pmatrix},
\\[6pt]
H(1.213402,0)\approx
\begin{pmatrix}
11.668137 & 0\\
0 & 2
\end{pmatrix}.
\]

Звідси

\[
\Delta \bar{x}_2=
–
H(1.213402,0)^{-1}\cdot \nabla f(1.213402,0)
\approx
\begin{pmatrix}
0.011504\\
0
\end{pmatrix}.
\]

Тоді

\[
\bar{x}_3=
\bar{x}_2+\frac{1}{4}\cdot \Delta \bar{x}_2
=
\begin{pmatrix}
1.213402\\
0
\end{pmatrix}
+
\frac{1}{4}
\cdot
\begin{pmatrix}
0.011504\\
0
\end{pmatrix}
=
\begin{pmatrix}
1.216278\\
0
\end{pmatrix}.
\]

Тепер знайдемо градієнт у точці \( \bar{x}_3 \):

\[
\nabla f(1.216278,0)\approx
\begin{pmatrix}
-0.100550\\
0
\end{pmatrix}.
\]

Матриця Гессе в цій точці дорівнює

\[
H(1.216278,0)\approx
\begin{pmatrix}
11.752030 & 0\\
0 & 2
\end{pmatrix}.
\]

Отже,

\[
\Delta \bar{x}_3=
–
H(1.216278,0)^{-1}\cdot \nabla f(1.216278,0)
\approx
\begin{pmatrix}
0.008556\\
0
\end{pmatrix}.
\]

Тоді одержуємо четверте наближення:

\[
\bar{x}_4=
\bar{x}_3+\frac{1}{4}\cdot \Delta \bar{x}_3
=
\begin{pmatrix}
1.216278\\
0
\end{pmatrix}
+
\frac{1}{4}
\cdot
\begin{pmatrix}
0.008556\\
0
\end{pmatrix}
=
\begin{pmatrix}
1.218417\\
0
\end{pmatrix}.
\]

Тепер перевіримо умову зупинки. Для точки \( \bar{x}_4 \) маємо

\[
\nabla f(1.218417,0)\approx
\begin{pmatrix}
-0.075189\\
0
\end{pmatrix}.
\]

Отже,

\[
\|\nabla f(\bar{x}_4)\|\approx 0.075189.
\]

Оскільки

\[
0.075189<0.1,
\]

ітераційний процес можна завершити.

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

\[
\bar{x}^*=
\begin{pmatrix}
1.218417\\
0
\end{pmatrix}.
\]

Обчислимо мінімальне значення функції в цій точці:

\[
f_{\min}\approx f(1.218417,0).
\]

Підставляємо знайдені значення:

\[
f(1.218417,0)=1.218417^4-3\cdot 1.218417^2+0^2\approx -2.249761.
\]

Отже, методом Ньютона з параметром отримуємо

\[
\bar{x}^*=
\begin{pmatrix}
1.218417\\
0
\end{pmatrix},
\qquad
f_{\min}\approx -2.249761.
\]

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

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

Що Варто Розглянути Далі: Корисні Напрями Для Продовження

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

1. Покоординатний спуск: Як працює покрокова мінімізація — У цій статті йтиметься про мінімізацію функції багатьох змінних шляхом послідовної зміни однієї координати за раз.
2. Градієнтний спуск: Як шукають мінімум за напрямом спаду — Тут буде показано, як для функції декількох змінних будують ітераційний процес на основі градієнта та вибору напряму зменшення.
3. Метод Ньютона для однієї змінної: Як працює класична схема — У цьому матеріалі розглядатиметься пошук мінімуму функції однієї змінної методом Ньютона та основні кроки цього процесу.

Метод Ньютона з Параметром у Коді: Ідея Для Власної Реалізації

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