EssayAI
Блог
Блог
Математика и алгоритмы

Метод Ньютона в оптимизации: формула и пример

8 ноября 2026Время чтения: 8 минут
#метод ньютона#оптимизация#минимум функции#гессиан#численные методы
Метод Ньютона в оптимизации: формула и пример

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

В калькуляторе ниже можно изменить начальную точку и увидеть, куда приводит один шаг. Сравните золотую точку на модели с графиком исходной функции: их значения в новой точке вообще говоря различаются.

Как кривизна определяет шаг

Пусть требуется минимизировать гладкую функцию одной переменной f(x)f(x). Зная её значение, первую и вторую производные в текущей точке xkx_k, строим квадратичное приближение:

qk(x)=f(xk)+f′(xk)(x−xk)+12f′′(xk)(x−xk)2.q_k(x)=f(x_k)+f'(x_k)(x-x_k)+\frac12 f''(x_k)(x-x_k)^2.

В точке xkx_k модель совпадает с функцией по значению, наклону и второй производной. Если f′′(xk)>0f''(x_k)>0, её график - парабола с единственным минимумом. Приравняв производную модели к нулю, получаем следующий шаг:

xk+1=xk−f′(xk)f′′(xk).x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}.

Знак производной указывает сторону роста функции, а знаменатель масштабирует поправку с учётом кривизны. Сравните это с методом наискорейшего спуска: там направление определяется градиентом, а длину шага выбирают отдельно. У Ньютона локальная модель сама задаёт и направление, и полный шаг.

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

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

Расчёт на одномерном примере

Возьмём функцию f(x)=x4/4+x2/2f(x)=x^4/4+x^2/2 и начальную точку x0=2x_0=2. Её производные равны

f′(x)=x3+x,f′′(x)=3x2+1.f'(x)=x^3+x,\qquad f''(x)=3x^2+1.

Вторая производная положительна при любом xx, так что функция строго выпукла; её единственная стационарная точка x∗=0x_*=0 является глобальным минимумом. В начальной точке f(2)=6f(2)=6, f′(2)=10f'(2)=10 и f′′(2)=13f''(2)=13. Подстановка даёт

x1=2−1013=1613≈1,231.x_1=2-\frac{10}{13}=\frac{16}{13}\approx1{,}231.

Соответствующая модель q0(x)=6+10(x−2)+132(x−2)2q_0(x)=6+10(x-2)+\tfrac{13}{2}(x-2)^2 принимает минимум примерно 2,1542{,}154. Но значение исходной функции при x1x_1 равно примерно 1,3311{,}331. Это две разные высоты при одной абсциссе: шаг выбирают по модели, а результат оценивают на исходной функции.

График функции и локальной параболы: из точки x₀ = 2 минимум модели расположен при x₁ около 1,231
График функции и локальной параболы: из точки x₀ = 2 минимум модели расположен при x₁ около 1,231

Для второго шага пересчитываем производные уже в x1x_1, а не оставляем прежнюю параболу. Получаем x2≈0,673x_2\approx0{,}673, затем x3≈0,258x_3\approx0{,}258 и x4≈0,0287x_4\approx0{,}0287. Значения функции соответственно примерно 0,2770{,}277, 0,03440{,}0344 и 0,0004110{,}000411. Последовательность приближается к нулю; в этом примере каждый показанный шаг уменьшает функцию. Это свойство конкретного примера, а не гарантия для любой функции.

Несколько переменных: градиент и гессиан

Для f:Rn→Rf:\mathbb{R}^n\to\mathbb{R} первую производную заменяет градиент gk=∇f(xk)g_k=\nabla f(x_k), а вторую - матрица Гессе Hk=∇2f(xk)H_k=\nabla^2 f(x_k). Её элементы - вторые частные производные. Вместо деления решают систему

Hkpk=−gk,xk+1=xk+pk.H_k p_k=-g_k,\qquad x_{k+1}=x_k+p_k.

Если гессиан обратим, формально pk=−Hk−1gkp_k=-H_k^{-1}g_k. На практике обычно решают систему напрямую, не вычисляя обратную матрицу: это удобнее и часто численно устойчивее. Положительно определённый гессиан означает, что квадратичная модель строго выпукла по всем направлениям и найденная точка является её единственным минимумом.

Например, для f(x,y)=x2+2y2f(x,y)=x^2+2y^2 градиент равен (2x,4y)(2x,4y), а гессиан - диагональная матрица с элементами 22 и 44. Из (2,1)(2,1) система даёт p=(−2,−1)p=(-2,-1) и сразу приводит в (0,0)(0,0). Здесь модель совпадает с самой квадратичной функцией во всём пространстве. Поэтому один полный шаг точен независимо от старта; для неквадратичной функции такого ожидать нельзя. Об устройстве подобных задач полезно прочитать в статье про квадратичное программирование.

Когда метод сходится быстро

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

∥xk+1−x∗∥≤C∥xk−x∗∥2.\|x_{k+1}-x_*\|\le C\|x_k-x_*\|^2.

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

Связь с методом касательных для корней прямая: условие стационарности f′(x)=0f'(x)=0 можно решить методом Ньютона для уравнения. Однако нуль производной может быть максимумом или седловой точкой. Для задачи минимизации требуется дополнительная проверка, а не только решение уравнения.

Почему знак кривизны важен

Рассмотрим противоположный пример: функция f(x)=−x2f(x)=-x^2 в точке x=1x=1. Её первая производная равна −2-2, вторая равна −2-2, поэтому формула даёт следующую точку x=0x=0. Но это максимум функции, а не минимум: значение выросло с −1-1 до 00. Парабола модели здесь совпадает с исходной функцией и направлена ветвями вниз. Её стационарная точка действительно находится формулой Ньютона, однако минимизировать такую модель нельзя: снизу она не ограничена.

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

Что делать при неудачном полном шаге

Если гессиан положительно определён и градиент ненулевой, направление Ньютона является направлением спуска: gkTpk=−pkTHkpk<0g_k^Tp_k=-p_k^TH_kp_k<0. Но полный переход на расстояние pkp_k всё же может увеличить функцию: локальная парабола не обязана хорошо описывать её далеко от xkx_k.

Один из способов защиты - демпфирование: положить xk+1=xk+αpkx_{k+1}=x_k+\alpha p_k, где 0<α≤10<\alpha\le1, и уменьшать α\alpha, пока выбранное условие достаточного убывания не выполнится. Такой поиск по направлению требует дополнительных вычислений функции, зато контролирует принятие шага. Его применение рассматривают в лекции Стэнфорда.

Если гессиан вырожден, систему нельзя однозначно решить обычным способом; если он неопределён, направление может вообще не быть спуском. Применяют модификацию гессиана или методы доверительной области, но конкретный выбор зависит от задачи. При большом числе переменных хранение гессиана и решение системы дороги; альтернативы используют приближения или структуру задачи. Для ограничений вида равенств и неравенств одной формулы выше недостаточно: подробнее о другом подходе - в статье про метод штрафных функций.

Стоимость одного шага

Скорость сходимости измеряет число итераций, но не время всей программы. На каждой итерации нужно получить вторые производные и решить систему размерности nn. Для большой плотной матрицы это может стоить заметно дороже шага градиентного метода. Если гессиан разрежен, структуру можно использовать при хранении и решении системы. На практике сравнивают не только количество шагов, но и общую стоимость вычислений, точность решения системы и доступную память. Поэтому метод особенно удобен там, где производные доступны, а размер задачи позволяет эффективно работать с кривизной.

Как организовать вычисление

Сначала задайте функцию, область допустимых значений и стартовую точку. Вычислите градиент и гессиан, проверьте их корректность и решите систему для направления. Если направление не обеспечивает спуск, используйте подходящую модификацию; при необходимости подберите длину шага. Затем обновите точку и повторите вычисления уже в ней.

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

Частые ошибки

  • Забывать вторую производную. Формула для оптимизации применяет метод Ньютона к f′=0f'=0, поэтому знаменатель - f′′f'', а не f′f'.
  • Называть минимум модели минимумом функции. В примере при x1x_1 модель и функция имеют разные значения; функция пересчитывается отдельно.
  • Обещать убывание на каждом полном шаге. Даже направление спуска при слишком длинном шаге может увеличить функцию.
  • Считать нулевой градиент достаточным признаком минимума. Он необходим для внутреннего гладкого минимума, но встречается и в максимуме.
  • Применять формулу при сингулярном гессиане без оговорок. Система может не иметь единственного решения, а вычисления - стать неустойчивыми.

FAQ

Всегда ли метод Ньютона находит глобальный минимум? Нет. Даже сходимость к локальному минимуму требует условий. Глобальный вывод возможен при дополнительных свойствах функции и корректном алгоритме.

Зачем нужен гессиан? Он описывает локальную кривизну по разным направлениям и позволяет построить квадратичную модель. Это дополнительная информация по сравнению с одним градиентом, но её вычисление может быть дорогим.

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

Коротко

Метод Ньютона минимизирует локальную квадратичную модель функции. В одной переменной шаг равен −f′/f′′-f'/f'', в нескольких находится из системы с гессианом. Вблизи невырожденного минимума возможна квадратичная сходимость; вдали от него важны проверка направления, подбор длины шага и оценка исходной функции.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Метод Ньютона для систем нелинейных уравнений

Метод Ньютона для систем нелинейных уравнений

Метод Ньютона для систем нелинейных уравнений: как составить матрицу Якоби, найти поправку, выполнить итерации и проверить точность решения на подробном примере.

8 ноября 20268 минут
Метод секущих для корня уравнения: формула и шаги

Метод секущих для корня уравнения: формула и шаги

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

11 июня 20269 минут
Метод золотого сечения: поиск минимума функции

Метод золотого сечения: поиск минимума функции

Метод золотого сечения для нахождения минимума функции: принцип работы, формулы x1 и x2, скорость сходимости phi^n, примеры задач и типичные ошибки студентов.

11 июня 20267 минут
Комбинированный метод хорд и касательных

Комбинированный метод хорд и касательных

Комбинированный метод хорд и касательных: как выбрать концы отрезка, вычислить границы корня, оценить погрешность и выполнить итерации на примере уравнения.

8 ноября 20268 минут
Метод Эйлера для ОДУ: пошаговый расчёт

Метод Эйлера для ОДУ: пошаговый расчёт

Метод Эйлера для ОДУ: как построить ломаную по начальным данным, составить таблицу шагов, сравнить численный результат с точным решением и оценить погрешность.

8 ноября 20268 минут
Метод предиктор-корректор: прогноз и поправка

Метод предиктор-корректор: прогноз и поправка

Метод предиктор-корректор для задачи Коши: формулы прогноза и поправки, подробный пример пары Адамса и трапеций, оценка ошибки, запуск и ограничения схемы.

8 ноября 20268 минут