Метод Ньютона: Мінімізація Функції Однієї Змінної

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

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

Метод Ньютона для Мінімізації: Як Будується Локальне Наближення

Нехай задано функцію \( f(x) \), для якої потрібно знайти точку локального мінімуму. У методі Ньютона не виконують послідовне звуження відрізка, як в інтервальних методах. Тут обирають початкове наближення \( x_0 \), а далі будують послідовність точок

\[
x_0, x_1, x_2, x_3, \dots
\]

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

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

\[
f(x_k+t) \approx f(x_k) + f’(x_k)\cdot t + \frac{1}{2}\cdot f’’(x_k)\cdot t^2,
\]

де \( t \) позначає приріст від поточного наближення.

Таким чином, замість безпосередньої роботи з функцією \( f(x) \) на кожному кроці ми працюємо з її локальним квадратичним наближенням. Це важливий момент: метод Ньютона на кожній ітерації мінімізує не саму функцію, а саме цю наближену квадратичну модель.

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

Побудова Формули Методу Ньютона: Як Отримується Наступне Наближення

Тепер перейдемо від загальної ідеї до конкретної формули. Позначимо локальне квадратичне наближення через

\[
\varphi(t)=f(x_k) + f’(x_k)\cdot t + \frac{1}{2}\cdot f’’(x_k)\cdot t^2.
\]

Саме функцію \( \varphi(t) \) потрібно мінімізувати за змінною \( t \). Для цього прирівнюємо її похідну до нуля:

\[
\varphi’(t)=0.
\]

Обчислюємо похідну:

\[
\varphi’(t)=f’(x_k)+f’’(x_k)\cdot t.
\]

Тому одержуємо рівняння

\[
f’(x_k)+f’’(x_k)\cdot t=0.
\]

Звідси знаходимо величину кроку:

\[
f’’(x_k)\cdot t=-f’(x_k),
\qquad
t=-\frac{f’(x_k)}{f’’(x_k)}.
\]

Оскільки нова точка визначається співвідношенням

\[
x_{k+1}=x_k+t,
\]

то після підстановки маємо основну ітераційну формулу методу Ньютона:

\[
x_{k+1}=x_k-\frac{f’(x_k)}{f’’(x_k)}.
\]

Саме цей запис використовують у практичних обчисленнях. Він показує, як із поточного наближення \( x_k \) перейти до нового наближення \( x_{k+1} \).

Тут важливо звернути увагу ще на одну річ. Якщо в деякій точці мінімуму \( x_{\min} \) виконується

\[
f’(x_{\min})=0,
\qquad
f’’(x_{\min})>0,
\]

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

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

Умова Зупинки Ітерацій: Як Визначити Кінцевий Результат

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

Найчастіше використовують умову

\[
|x_{k+1}-x_k|<\varepsilon,
\]

де \( \varepsilon>0 \) — наперед задана точність. У такому випадку перевіряють, наскільки близькими стали два сусідні наближення. Якщо різниця між ними вже мала, то вважають, що послідовність наближень практично стабілізувалася. Отже, тут \( \varepsilon \) контролює близькість сусідніх наближень за змінною \( x \), а не безпосередньо похибку значення функції.

Інколи застосовують і ще один критерій:

\[
|f’(x_k)|<\varepsilon.
\]

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

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

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

\[
x^*\approx x_{k+1}.
\]

Після цього вже обчислюють наближене мінімальне значення функції:

\[
f_{\min}\approx f(x^*).
\]

Практична Частина: Як Метод Ньютона Працює на Конкретній Задачі

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

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

Розглянемо функцію \( f(x)=x^4-4 \cdot x^2+5 \) на відрізку \( [1,2] \). На цьому проміжку вона є достатньо гладкою, тобто має першу і другу похідні. Візьмемо початкове наближення \( x_0=1.5 \), оскільки воно належить заданому відрізку. Крім того, воно розташоване поблизу точки мінімуму, тому є зручним для початку ітераційного процесу.

Спочатку знайдемо похідні:

\[
f’(x)=4\cdot x^3-8\cdot x,
\qquad
f’’(x)=12\cdot x^2-8.
\]

Для першої ітерації обчислюємо значення похідних у точці \( x_0=1.5 \):

\[
\begin{gathered}
f’(1.5)=4\cdot(1.5)^3-8\cdot1.5=13.5-12=1.5,
\\[6pt]
f’’(1.5)=12\cdot(1.5)^2-8=27-8=19.
\end{gathered}
\]

Тоді нове наближення дорівнює

\[
x_1=x_0-\frac{f’(x_0)}{f’’(x_0)}=1.5-\frac{1.5}{19}\approx 1.421.
\]

Для другої ітерації беремо точку \( x_1\approx 1.421 \):

\[
\begin{gathered}
f’(1.421)=4\cdot(1.421)^3-8\cdot1.421\approx 0.337,
\\[6pt]
f’’(1.421)=12\cdot(1.421)^2-8\approx 16.234.
\end{gathered}
\]

Отже,

\[
x_2=x_1-\frac{f’(x_1)}{f’’(x_1)}\approx 1.421-\frac{0.337}{16.234}\approx 1.4.
\]

Тепер перевіряємо умову точності:

\[
|x_2-x_1|=|1.4-1.421|=0.021.
\]

Оскільки \( 0.021<0.05 \), ітераційний процес можна завершити.

Останнім знайденим наближенням є \( x_2 \), тому саме його беремо за наближене значення точки мінімуму:

\[
x^*\approx x_2\approx 1.4.
\]

Після цього обчислюємо мінімальне значення функції:

\[
f_{\min}\approx f(x^*)=f(1.4).
\]

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

\[
f(1.4)=(1.4)^4-4\cdot(1.4)^2+5.
\]

Маємо

\[
(1.4)^2=1.96,
\qquad
(1.4)^4=3.8416.
\]

Тому

\[
f(1.4)=3.8416-4\cdot1.96+5=3.8416-7.84+5=1.0016.
\]

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

\[
x^*\approx 1.4,
\qquad
f_{\min}\approx 1.0016.
\]

Цей результат добре узгоджується з точною відповіддю, оскільки для функції \( f(x)=x^4-4 \cdot x^2+5 \) на відрізку \( [1,2] \) мінімум досягається при \( x=\sqrt{2} \), а відповідне найменше значення дорівнює \( f(\sqrt{2})=1 \).

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

Що Варто Розглянути Далі: Наступні Теми з Оптимізації

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

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

Метод Ньютона в Програмуванні: Спробуйте Реалізувати Алгоритм Самостійно

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

Метод Ньютона: Як Знайти Мінімум Функції Однієї Змінної