Минимизация функции нескольких переменных — одна из важных тем численных методов, ведь во многих задачах требуется найти точку, в которой функция принимает наименьшее значение сразу по нескольким параметрам. Именно для таких задач часто применяют метод Ньютона. Почему этот подход так важен? Дело в том, что он использует не только значение функции, но и её производные первого и второго порядка. Благодаря этому удаётся построить более точное локальное приближение к точке минимума. В этой статье последовательно рассмотрим основную идею метода, роль градиента и матрицы Гессе, а также выведем главную итерационную формулу.
Метод Ньютона: Какова Основная Идея Этого Метода
Пусть задана функция нескольких переменных
\[
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}.
\]
Таким образом, в этом примере последовательно показаны все основные шаги метода Ньютона: выбор начальной точки, вычисление градиента и матрицы Гессе, нахождение нового приближения, проверка условия точности и вычисление минимального значения функции в найденной точке.
Что Стоит Рассмотреть Дальше: Темы для Дальнейшего Изучения
Тему метода Ньютона для функции нескольких переменных мы уже рассмотрели последовательно и наглядно. Однако куда двигаться дальше? Вполне логично обратить внимание и на другие подходы, которые помогают лучше понять особенности многомерной минимизации.
- Метод Ньютона с параметром: Как изменяется шаг — В этой статье речь пойдёт о том, как дополнительный параметр влияет на движение к минимуму и почему иногда это делает метод более устойчивым.
- Покоординатный спуск: Как работает поочерёдный поиск — Здесь будет показано, как минимум ищут последовательно по отдельным переменным и почему такой подход оказывается удобным во многих задачах.
- Градиентный спуск: Как двигаться в направлении убывания — В этой теме будет рассмотрен один из самых известных методов минимизации, где новые приближения находят по направлению наиболее быстрого уменьшения функции.
Метод Ньютона и Код: Попробуйте Создать Собственную Программу
Схема ниже — это уже не просто дополнение к статье, а вполне практическая подсказка для самостоятельной работы. Почему бы не использовать её как основу и не создать на любимом языке программирования небольшое приложение, которое находит минимальное значение функции нескольких переменных методом Ньютона? Когда вы переносите математическую идею в код, тема воспринимается намного яснее: формулы перестают быть только теоретическим материалом и превращаются в понятную последовательность действий. Кроме того, это хороший способ проверить себя на практике и посмотреть, как метод работает на разных примерах.
