Метод Ньютона с Параметром: Что Стоит Знать Об Этом Подходе

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

Метод Ньютона с Параметром: Как Строят Направление Перехода

Пусть задана функция нескольких переменных

\[
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. Метод Ньютона для одной переменной: Как работает классическая схема — В этом материале будет рассматриваться поиск минимума функции одной переменной методом Ньютона и основные шаги этого процесса.

Метод Ньютона с Параметром в Коде: Идея Для Собственной Реализации

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