Метод Ньютона у задачах багатовимірної оптимізації належить до важливих методів другого порядку. Однак у практичних обчисленнях не завжди зручно використовувати повний ньютонівський крок. Саме тому розглядають варіант, у якому до схеми додають спеціальний параметр. Такий підхід робить процес пошуку гнучкішим і дає змогу краще керувати переходом до нового наближення. У літературі Метод Ньютона з параметром також часто називають демпфованим методом Ньютона, тобто методом, у якому повний крок Ньютона за потреби зменшують. Далі послідовно розглянемо, як будується цей метод, який вигляд має його ітераційна формула та за якою умовою завершують обчислення.
Метод Ньютона з Параметром: Як Будують Напрям Переходу
Нехай задано функцію кількох змінних
\[ 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. \]
Оскільки в знайденій точці обидва діагональні елементи матриці Гессе є додатними, матриця Гессе тут є додатно визначеною. Отже, знайдена стаціонарна точка відповідає локальному мінімуму. Для цієї функції вона є одним із двох симетричних мінімумів.
Таким чином, у цьому прикладі послідовно видно головну ідею методу Ньютона з параметром. Спочатку знаходять ньютонівський приріст, далі коригують довжину кроку за допомогою параметра, а потім перевіряють умову зупинки. Саме цей приклад наочно показує, що схема з параметром може бути доречнішою за класичний метод Ньютона тоді, коли повний крок виявляється занадто великим і не дає бажаного зменшення функції.
Що Варто Розглянути Далі: Корисні Напрями Для Продовження
Тему методу Ньютона з параметром ми вже розглянули послідовно: від основної ідеї до практичного прикладу. Однак на цьому знайомство з методами мінімізації не завершується. Що ще варто прочитати далі, щоб краще бачити різницю між підходами та їх можливостями?
- Покоординатний спуск: Як працює покрокова мінімізація — У цій статті йтиметься про мінімізацію функції багатьох змінних шляхом послідовної зміни однієї координати за раз.
- Градієнтний спуск: Як шукають мінімум за напрямом спаду — Тут буде показано, як для функції декількох змінних будують ітераційний процес на основі градієнта та вибору напряму зменшення.
- Метод Ньютона для однієї змінної: Як працює класична схема — У цьому матеріалі розглядатиметься пошук мінімуму функції однієї змінної методом Ньютона та основні кроки цього процесу.
Метод Ньютона з Параметром у Коді: Ідея Для Власної Реалізації
Готова блок-схема дає чудову можливість перейти від теорії до програмування. На її основі можна написати невелику програму на будь-якій зручній мові, яка обчислюватиме мінімальне значення функції кількох змінних методом Ньютона з параметром. Така робота допомагає краще зрозуміти сам підхід, адже математичні міркування поступово перетворюються на зрозумілий обчислювальний процес. До того ж це хороший спосіб перевірити себе на практиці, уважніше розібратися з роллю параметра та побачити, як метод поводиться на різних прикладах.
