Метод Ньютона: Как Найти Минимум Функции

Метод Ньютона относится к классическим численным методам поиска минимума функции одной переменной. Эта тема важна потому, что на практике минимальное значение далеко не всегда удаётся найти с помощью простых преобразований. Именно поэтому используют итерационные методы, которые позволяют шаг за шагом приближаться к искомой точке.

В этой статье мы последовательно рассмотрим основную идею метода, выведем итерационную формулу, разберёмся, когда следует завершать вычисления, а затем применим этот подход к конкретной задаче. Такой порядок помогает увидеть не только итоговую формулу, но и понять, как именно она работает.

Метод Ньютона для Минимизации: Как Строится Локальное Приближение

Пусть задана функция \( 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-x_0|=|1.421-1.5|=0.079.
\]

Поскольку \( 0.079>0.05 \), требуемая точность ещё не достигнута, поэтому переходим к следующей итерации.

Для второй итерации берём точку \( 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^*\approx x_2\approx 1.4.
\]

После этого вычисляем приближённое минимальное значение функции:

\[
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=3.8416-7.84+5=1.0016.
\]

Следовательно, методом Ньютона получаем

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

Если же выполнить ещё одну итерацию, то получим более точное приближение:

\[
x_3=x_2-\frac{f'(x_2)}{f»(x_2)}\approx 1.414,
\]

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

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

Что Стоит Рассмотреть Дальше: Следующие Темы по Оптимизации

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

Метод Ньютона для нескольких переменных: Как меняется поиск минимума — В этой теме речь пойдёт о том, как метод Ньютона переходит к функциям нескольких переменных и что именно меняется при поиске минимума.
Покоординатный спуск: Как работает поочерёдный поиск — Здесь будет показан подход, в котором минимум находят последовательно по каждой переменной, чтобы было легче понять, как происходят вычисления.
Градиентный спуск: Как выбирают направление убывания — В этой статье будет рассматриваться способ поиска минимума функции нескольких переменных через выбор направления, в котором значение функции уменьшается.

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

Блок-схема ниже может стать для вас не просто дополнением к теоретическому материалу, а удобной основой для собственной практической работы. Почему бы не взять её за основу и не создать на любимом языке программирования небольшую программу для нахождения минимального значения функции методом Ньютона? Такой подход помогает увидеть, как математическая идея превращается в последовательный алгоритм, а затем — в понятный код. Кроме того, это хорошая возможность проверить метод на разных функциях и лучше почувствовать его в реальной работе.

Метод Ньютона: Как Найти Минимум Функции Одной Переменной