Мінімізація функції кількох змінних — одна з важливих тем чисельних методів, адже в багатьох задачах потрібно знайти точку, у якій функція набуває найменшого значення одразу за кількома параметрами. Саме для таких задач часто застосовують метод Ньютона. Чому цей підхід такий важливий? Річ у тім, що він використовує не лише значення функції, а й її похідні першого та другого порядку. Завдяки цьому вдається побудувати точніше локальне наближення до точки мінімуму. У цій статті послідовно розглянемо основну ідею методу, роль градієнта та матриці Гессе, а також виведемо головну ітераційну формулу.
Метод Ньютона: Яка Основна Ідея Цього Методу
Нехай задано функцію кількох змінних
\[
f(\bar{x})=f(x_1,x_2,\dots,x_n),
\]
де \( \bar{x} \) — вектор змінних. Потрібно знайти таку точку, у якій функція набуває локально найменшого значення. Але як наближатися до цієї точки на практиці? Саме для цього і використовують метод Ньютона.
Його основна ідея полягає в тому, щоб поблизу поточної точки \( \bar{x}_k \) замінити вихідну функцію простішою локальною моделлю. Зокрема, використовують квадратичне наближення, яке отримують із розкладу функції в ряд Тейлора до другого порядку. Отже, на кожному кроці метод фактично працює не з усією функцією в цілому, а з її квадратичною моделлю поблизу поточної точки.
Тоді поблизу точки \( \bar{x}_k \) функцію \( f(\bar{x}) \) наближено подають так:
\[
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) \) — матриця Гессе в точці \( \bar{x}_k \), яка описує кривизну функції поблизу цієї точки.
Отже, лінійний доданок у формулі враховує напрям зміни функції, а квадратичний — те, як змінюється поверхня функції поблизу \( \bar{x}_k \). Саме тому квадратична модель дає значно більше інформації, ніж звичайне лінійне наближення.
Градієнт і Матриця Гессе: Які Величини Використовує Метод
Перш за все, для побудови методу потрібно знати градієнт функції. Градієнт — це вектор, який складається з перших частинних похідних:
\[
\nabla f(\bar{x})=
\begin{pmatrix}
\frac{\partial f}{\partial x_1} \\
\frac{\partial f}{\partial x_2} \\
\vdots \\
\frac{\partial f}{\partial x_n}
\end{pmatrix}.
\]
Він показує, як функція змінюється за кожною змінною. Однак для методу Ньютона цього ще недостатньо. Потрібно також врахувати, як змінюється сама форма поверхні функції. Саме тому тут використовують похідні другого порядку.
Матриця других частинних похідних називається матрицею Гессе:
\[
H(\bar{x})=
\begin{pmatrix}
\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\
\frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\
\vdots & \vdots & \ddots & \vdots \\
\frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2}
\end{pmatrix}.
\]
Отже, матриця Гессе описує кривизну функції. А це дуже важливо, бо для пошуку мінімуму недостатньо знати лише напрям зменшення функції. Потрібно ще враховувати, як поводиться поверхня функції поблизу поточної точки. Саме тому метод Ньютона, на відміну від методів першого порядку, використовує не тільки градієнт, а й похідні другого порядку.
Однак тут важливо враховувати ще одну обставину. Якщо матриця Гессе в поточній точці є додатно визначеною, тоді квадратична модель має локальний мінімум, і крок методу Ньютона буде спрямований у бік зменшення функції. Якщо ж матриця Гессе не є додатно визначеною, то отриманий напрям може не привести до мінімуму. Отже, властивості матриці Гессе істотно впливають на роботу методу.
Якщо другі похідні важко знайти аналітично, елементи матриці Гессе можна обчислювати наближено за допомогою різницевих формул. Наприклад, для діагональних елементів використовують таке наближення:
\[
H_{ii}(\bar{x}) \approx
\frac{f(x_1,\dots,x_i+h,\dots,x_n)-2\cdot f(x_1,\dots,x_i,\dots,x_n)+f(x_1,\dots,x_i-h,\dots,x_n)}{h^2}.
\]
А для змішаних похідних, тобто при \( i \ne j \), можна застосувати таке наближення:
\[
H_{ij}(\bar{x}) \approx
\frac{1}{4\cdot h\cdot k}
\Bigl(
f(x_1,\dots,x_i+h,\dots,x_j+k,\dots,x_n)-f(x_1,\dots,x_i+h,\dots,x_j-k,\dots,x_n)
\\[6pt]
-f(x_1,\dots,x_i-h,\dots,x_j+k,\dots,x_n)+f(x_1,\dots,x_i-h,\dots,x_j-k,\dots,x_n)
\Bigr).
\]
Отже, навіть без точного аналітичного обчислення других похідних матрицю Гессе часто можна побудувати чисельно. А далі вже виникає природне запитання: як саме за допомогою цих величин отримують формулу переходу до нової точки?
Метод Ньютона: Як Виводять Основну Ітераційну Формулу
Тепер перейдемо до головного кроку. Позначимо приріст аргументу через
\[
\Delta \bar{x}_k=\bar{x}_{k+1}-\bar{x}_k.
\]
Тоді квадратичну модель функції поблизу точки \( \bar{x}_k \) можна переписати у вигляді
\[
f(\bar{x}_{k+1}) \approx f(\bar{x}_k)
+ \nabla f(\bar{x}_k)^T \cdot \Delta \bar{x}_k
+ \frac{1}{2}\cdot \Delta \bar{x}_k^T \cdot H(\bar{x}_k)\cdot \Delta \bar{x}_k.
\]
Далі потрібно знайти такий приріст \( \Delta \bar{x}_k \), при якому мінімального значення досягає саме ця квадратична модель. Інакше кажучи, на поточному кроці ми шукаємо мінімум не вихідної функції в цілому, а її локального наближення поблизу точки \( \bar{x}_k \).
Для цього знайдемо градієнт квадратичної моделі за вектором \( \Delta \bar{x}_k \) і прирівняємо його до нуля:
\[
\nabla f(\bar{x}_k)+H(\bar{x}_k)\cdot \Delta \bar{x}_k=0.
\]
Звідси отримуємо:
\[
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).
\]
Тепер підставимо цей вираз у формулу переходу
\[
\bar{x}_{k+1}=\bar{x}_k+\Delta \bar{x}_k.
\]
У результаті одержуємо основну ітераційну формулу:
\[
\bar{x}_{k+1}=\bar{x}_k-H(\bar{x}_k)^{-1}\cdot \nabla f(\bar{x}_k).
\]
Саме ця формула є основою методу Ньютона для мінімізації функції кількох змінних. Вона показує, як із поточного наближення перейти до наступного, використовуючи одночасно і градієнт, і матрицю Гессе. З одного боку, градієнт задає напрям локальної зміни функції. З іншого боку, матриця Гессе враховує кривизну поверхні. Отже, перехід до нової точки стає більш точним, ніж у методах, які спираються лише на похідні першого порядку.
Якщо функція є квадратичною, то за відповідних умов метод може привести до розв’язку дуже швидко. Але в загальному випадку процес виконується послідовно:
\[
\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 \) норма градієнта вже досить мала. Отже, поблизу цієї точки функція змінюється незначно, і процес обчислень можна зупинити. Після цього останню знайдену точку \( \bar{x}_k \) приймають за наближене значення точки локального мінімуму, а значення \( f(\bar{x}_k) \) — за наближене мінімальне значення функції.
Отже, метод Ньютона у задачах багатовимірної мінімізації ґрунтується на послідовній схемі: спочатку будують квадратичну модель функції поблизу поточної точки, далі знаходять мінімум цієї моделі, а потім переходять до нового наближення. Саме така побудова і робить цей метод одним із найважливіших методів другого порядку.
Практична Частина: Як Метод Ньютона Працює на Конкретному Прикладі
Теоретична схема методу стає значно зрозумілішою, коли її розглядають на конкретній задачі. Саме тому тепер послідовно пройдемо всі основні кроки для функції двох змінних. Так буде легше побачити, як саме формула методу Ньютона застосовується на практиці.
Приклад 1. Знайти мінімальне значення функції \( f(x_1,x_2)=x_1^2+x_2^2-x_1\cdot x_2-2\cdot x_1-4\cdot x_2+6 \) з точністю \( \varepsilon=0.001 \), використовуючи метод Ньютона
Розглянемо функцію
\[
f(x_1,x_2)=x_1^2+x_2^2-x_1\cdot x_2-2\cdot x_1-4\cdot x_2+6.
\]
Для неї послідовно застосуємо формулу методу Ньютона. Візьмемо початкове наближення
\[
\bar{x}_0=
\begin{pmatrix}
0\\
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}
2\cdot x_1-x_2-2\\
2\cdot x_2-x_1-4
\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}
2 & -1\\
-1 & 2
\end{pmatrix}.
\]
Бачимо, що матриця Гессе є сталою, тобто не залежить від точки. Тепер обчислимо градієнт у початковій точці \( \bar{x}_0=(0,0)^T \):
\[
\nabla f(0,0)=
\begin{pmatrix}
2\cdot 0-0-2\\
2\cdot 0-0-4
\end{pmatrix}
=
\begin{pmatrix}
-2\\
-4
\end{pmatrix}.
\]
Знайдемо обернену матрицю до матриці Гессе:
\[
H^{-1}=
\begin{pmatrix}
2 & -1\\
-1 & 2
\end{pmatrix}^{-1}
=
\frac{1}{3}
\cdot
\begin{pmatrix}
2 & 1\\
1 & 2
\end{pmatrix}.
\]
Тоді за формулою методу Ньютона
\[
\bar{x}_{k+1}=\bar{x}_k-H^{-1}(\bar{x}_k)\cdot \nabla f(\bar{x}_k)
\]
для першої ітерації маємо
\[
\bar{x}_1=\bar{x}_0-H^{-1}\cdot \nabla f(\bar{x}_0).
\]
Підставляємо знайдені значення:
\[
\bar{x}_1=
\begin{pmatrix}
0\\
0
\end{pmatrix}
–
\frac{1}{3}
\cdot
\begin{pmatrix}
2 & 1\\
1 & 2
\end{pmatrix}
\cdot
\begin{pmatrix}
-2\\
-4
\end{pmatrix}.
\]
Спочатку виконаємо множення матриці на вектор:
\[
\begin{pmatrix}
2 & 1\\
1 & 2
\end{pmatrix}
\cdot
\begin{pmatrix}
-2\\
-4
\end{pmatrix}
=
\begin{pmatrix}
2\cdot(-2)+1\cdot(-4)\\
1\cdot(-2)+2\cdot(-4)
\end{pmatrix}
=
\begin{pmatrix}
-8\\
-10
\end{pmatrix}.
\]
Отже,
\[
\bar{x}_1=
\begin{pmatrix}
0\\
0
\end{pmatrix}
–
\frac{1}{3}
\begin{pmatrix}
-8\\
-10
\end{pmatrix}
=
\begin{pmatrix}
\frac{8}{3}\\
\frac{10}{3}
\end{pmatrix}.
\]
Тепер знайдемо градієнт у точці \( \bar{x}_1 \):
\[
\nabla f\left(\frac{8}{3},\frac{10}{3}\right)=
\begin{pmatrix}
2\cdot\frac{8}{3}-\frac{10}{3}-2
\\[6pt]
2\cdot\frac{10}{3}-\frac{8}{3}-4
\end{pmatrix}
=
\begin{pmatrix}
0\\
0
\end{pmatrix}.
\]
Отже,
\[
\|\nabla f(\bar{x}_1)\|=0.
\]
Оскільки
\[
0<0.001,
\]
ітераційний процес можна завершити вже після першого кроку.
Отже, останню знайдену точку приймаємо за наближене значення точки мінімуму:
\[
\bar{x}^*=
\begin{pmatrix}
\frac{8}{3}\\
\frac{10}{3}
\end{pmatrix}.
\]
Оскільки матриця Гессе
\[
H=
\begin{pmatrix}
2 & -1\\
-1 & 2
\end{pmatrix}
\]
є додатно визначеною, знайдена стаціонарна точка відповідає локальному мінімуму. Крім того, для цієї квадратичної функції цей мінімум є глобальним.
Тепер обчислимо мінімальне значення функції:
\[
f_{\min}\approx f\left(\frac{8}{3},\frac{10}{3}\right).
\]
Підставляємо знайдені значення:
\[
f\left(\frac{8}{3},\frac{10}{3}\right)
=
\left(\frac{8}{3}\right)^2+\left(\frac{10}{3}\right)^2-\frac{8}{3}\cdot\frac{10}{3}-2\cdot\frac{8}{3}-4\cdot\frac{10}{3}+6.
\]
Послідовно обчислюємо:
\[
f\left(\frac{8}{3},\frac{10}{3}\right)
=
\frac{64}{9}+\frac{100}{9}-\frac{80}{9}-\frac{16}{3}-\frac{40}{3}+6.
\]
Зведемо вираз до спільного знаменника:
\[
f\left(\frac{8}{3},\frac{10}{3}\right)=\frac{64+100-80-48-120+54}{9}=\frac{-30}{9}=-\frac{10}{3}.
\]
Отже, методом Ньютона отримуємо
\[
\bar{x}^*=
\begin{pmatrix}
\frac{8}{3}\\
\frac{10}{3}
\end{pmatrix},
\qquad
f_{\min}=-\frac{10}{3}.
\]
Таким чином, у цьому прикладі послідовно показано всі основні кроки методу Ньютона: вибір початкової точки, обчислення градієнта й матриці Гессе, знаходження нового наближення, перевірку умови точності та обчислення мінімального значення функції в знайденій точці.
Що Варто Розглянути Далі: Теми для Подальшого Вивчення
Тему методу Ньютона для функції кількох змінних ми вже розглянули послідовно й наочно. Однак куди рухатися далі? Цілком логічно звернути увагу на інші підходи, які допомагають краще побачити особливості багатовимірної мінімізації.
- Метод Ньютона з параметром: Як змінюється крок — У цій статті йтиметься про те, як додатковий параметр впливає на рух до мінімуму та чому інколи це робить метод стійкішим.
- Покоординатний спуск: Як працює почерговий пошук — Тут буде показано, як мінімум шукають послідовно за окремими змінними та чому такий підхід є зручним у багатьох задачах.
- Градієнтний спуск: Як рухатися в напрямі спаду — У цій темі розглядатиметься один із найвідоміших методів мінімізації, де нові наближення знаходять за напрямом найшвидшого зменшення функції.
Метод Ньютона і Код: Спробуйте Створити Власну Програму
Схема нижче — це вже не лише доповнення до статті, а й цілком практична підказка для самостійної роботи. Чому б не використати її як основу та не створити на улюбленій мові програмування невеликий застосунок, який знаходить мінімальне значення функції кількох змінних методом Ньютона? Коли ви переносите математичну ідею в код, тема сприймається набагато ясніше: формули перестають бути лише теоретичним матеріалом і перетворюються на зрозумілу послідовність дій. До того ж це гарний спосіб перевірити себе на практиці та подивитися, як метод працює для різних прикладів.
