Метод Ньютона-Рафсона

Материал из MachineLearning.

Статья написана с использованием LLM GPT-5.5 и проверена участником Iurii Patrakov 02:54, 10 июля 2026 (MSD)

Метод Ньютона-Рафсона — это итерационный метод численного решения нелинейных уравнений вида $f(x)=0$ , в котором очередное приближение строится как корень касательной к функции в текущей точке. В оптимизации тот же принцип применяется к условию стационарности $\nabla F(x)=0$ , поэтому метод Ньютона-Рафсона является одним из базовых методов второго порядка в численных методах, выпуклой оптимизации и машинном обучении.

Идея метода

Пусть дана дифференцируемая функция $f:\mathbb{R}\to\mathbb{R}$ и требуется найти её корень $x^\ast$ , то есть значение, для которого

$f(x^\ast)=0.$

В окрестности текущего приближения $x_k$ функция заменяется своей линейной аппроксимацией:

$f(x)\approx f(x_k)+f'(x_k)(x-x_k).$

Если приравнять эту касательную к нулю, получается новое приближение:

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

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

Обобщение на несколько переменных

Для системы нелинейных уравнений

$F(x)=0,\quad F:\mathbb{R}^n\to\mathbb{R}^n$

используется матрица Якоби $J_F(x_k)$ . Шаг Ньютона находится из линейной системы

$J_F(x_k) p_k = -F(x_k),$

после чего

$x_{k+1}=x_k+p_k.$

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

Метод Ньютона в оптимизации

Если требуется минимизировать дважды дифференцируемую функцию

$F(x)\to \min,$

то необходимое условие локального экстремума имеет вид

$\nabla F(x)=0.$

Применяя метод Ньютона к этому уравнению, получают шаг

$\nabla^2 F(x_k)p_k=-\nabla F(x_k),$

где $\nabla F(x_k)$ — градиент, а $\nabla^2 F(x_k)$ — матрица Гессе. Затем

$x_{k+1}=x_k+\alpha_k p_k,$

где $\alpha_k$ — длина шага. В классическом локальном варианте часто берут $\alpha_k=1$ , но в прикладных задачах используют демпфирование, линейный поиск или методы доверительной области.

Смысл ньютоновского шага состоит в минимизации квадратичной модели функции:

$F(x_k+p)\approx F(x_k)+\nabla F(x_k)^Tp+\frac{1}{2}p^T\nabla^2F(x_k)p.$

В отличие от градиентного спуска, который использует только направление наискорейшего локального убывания, метод Ньютона учитывает кривизну поверхности ошибки. Поэтому он может делать более «масштабированные» шаги: идти осторожнее в направлениях большой кривизны и смелее в плоских направлениях.

Историческая справка

Идея метода восходит к работам Исаака Ньютона по численному решению алгебраических уравнений. Ньютон описал близкую процедуру в рукописи De analysi per aequationes numero terminorum infinitas, написанной в 1669 году и опубликованной в 1711 году, а также в работах о флюксиях.

Джозеф Рафсон в книге Analysis aequationum universalis 1690 года дал более явную итерационную форму метода для приближённого решения уравнений. Современная формула метода является результатом последующей математической переработки этих идей. Двойное название подчёркивает вклад Ньютона в исходную идею и вклад Рафсона в её более алгоритмическое изложение.

Условия сходимости

Классическая локальная теория утверждает: если $f$ дважды непрерывно дифференцируема, корень $x^\ast$ является простым, то есть $f'(x^\ast)\ne 0$ , а начальное приближение достаточно близко к $x^\ast$ , то метод Ньютона-Рафсона сходится квадратично:

$|x_{k+1}-x^\ast|\le C|x_k-x^\ast|^2$

для некоторой константы $C$ .

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

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

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

Значение для машинного обучения

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

Методы второго порядка лежат в основе или влияют на следующие подходы:

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

В задачах машинного обучения часто минимизируется эмпирический риск

$F(w)=\frac{1}{m}\sum_{i=1}^{m}\ell(f_w(x_i),y_i)+\lambda R(w),$

где $w$ — параметры модели, $\ell$ — функция потерь, $R$ — регуляризатор. Ньютоновский шаг учитывает не только средний наклон этой функции, но и её локальную кривизну относительно параметров.

Пример: логистическая регрессия

Для бинарной логистической регрессии с отрицательным логарифмом правдоподобия градиент и матрица Гессе имеют удобную форму. Если $X$ — матрица объектов, $p$ — вектор предсказанных вероятностей, $y$ — вектор меток, то

$\nabla F(w)=X^T(p-y),$

а матрица Гессе равна

$\nabla^2F(w)=X^T W X,$

где $W$ — диагональная матрица с элементами $p_i(1-p_i)$ . Шаг Ньютона решает систему

$X^T W X\,p_k=-X^T(p-y).$

Эта структура связывает метод Ньютона с взвешенным методом наименьших квадратов и объясняет его эффективность для классических статистических моделей.

Ограничения

Главный недостаток метода Ньютона-Рафсона — вычислительная стоимость. Для задачи с $n$ параметрами требуется работать с матрицей Гессе размера $n\times n$ . Её хранение требует $O(n^2)$ памяти, а прямое решение линейной системы обычно требует до $O(n^3)$ операций. Для современных нейронных сетей с миллионами или миллиардами параметров это неприемлемо.

Другие ограничения:

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

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

Связанные и производные методы

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

Демпфированный метод Ньютона — использует шаг $\alpha_k p_k$ с подбором $\alpha_k$ , что повышает устойчивость вдали от решения.
Методы доверительной области — минимизируют квадратичную модель только внутри области, где она считается надёжной.
Квазиньютоновские методы — строят приближение к матрице Гессе или её обратной без явного вычисления вторых производных; классический пример — BFGS и его ограниченная по памяти версия L-BFGS.
Усечённый метод Ньютона — решает ньютоновскую систему приближённо, часто методом сопряжённых градиентов.
Безгессианова оптимизация (англ. Hessian-free optimization) — не строит матрицу Гессе явно, а использует произведения матрицы Гессе на вектор.
Стохастические ньютоновские методы — используют подвыборки данных для приближения градиента, матрицы Гессе или ньютоновского шага.
Проксимальные ньютоновские методы — применяются к задачам, где функция состоит из гладкой части и негладкого регуляризатора, например при $L_1$ -регуляризации.

Современные направления

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

построение дешёвых приближений матрицы Гессе;
использование случайных проекций и эскизирования для уменьшения размерности ньютоновских систем;
подвыборка объектов при вычислении кривизны;
эффективное вычисление произведений «Гессе на вектор» через автоматическое дифференцирование;
устойчивые методы второго порядка для невыпуклых задач;
сочетание ньютоновских идей с адаптивными методами первого порядка;
анализ седловых точек и отрицательной кривизны в обучении нейронных сетей;
распределённые и параллельные варианты для больших наборов данных.

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

Практические замечания

При реализации метода Ньютона-Рафсона важно учитывать несколько правил.

Не следует явно вычислять обратную матрицу Якоби или Гессе; лучше решать линейную систему.
В одномерных задачах полезно совмещать метод Ньютона с более надёжными методами, например бисекцией.
Для задач оптимизации нужно проверять, что матрица Гессе положительно определена; иначе ньютоновское направление может не быть направлением убывания.
В невыпуклых задачах часто нужна регуляризация: например, замена $H$ на $H+\lambda I$ .
Критерий остановки должен учитывать не только изменение аргумента, но и норму градиента или невязки.
Масштабирование признаков может существенно влиять на численную устойчивость.

См. также

Литература

Nocedal J., Wright S. J. Numerical Optimization. 2nd ed. Springer, 2006.
Boyd S., Vandenberghe L. Convex Optimization. Cambridge University Press, 2004.
Ortega J. M., Rheinboldt W. C. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, 1970.
Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P. Numerical Recipes: The Art of Scientific Computing. 3rd ed. Cambridge University Press, 2007.
Kelley C. T. Iterative Methods for Linear and Nonlinear Equations. SIAM, 1995.
Dembo R. S., Eisenstat S. C., Steihaug T. Inexact Newton Methods. SIAM Journal on Numerical Analysis, 1982.
Martens J. Deep Learning via Hessian-free Optimization. Proceedings of ICML, 2010.

Ссылки

Newton method — статья в Encyclopedia of Mathematics.
Nocedal J., Wright S. J. Numerical Optimization — страница книги на Springer.
Boyd S., Vandenberghe L. Convex Optimization — страница книги со свободно доступной электронной версией.
Bollapragada R., Byrd R., Nocedal J. Exact and Inexact Subsampled Newton Methods for Optimization — работа о стохастических и подвыборочных вариантах метода Ньютона.
Byrd R. H., Nocedal J., Oztoprak F. An Inexact Successive Quadratic Approximation Method for Convex L-1 Regularized Optimization — работа о проксимальном ньютоновском подходе для задач с $L_1$ -регуляризацией.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0-%D0%A0%D0%B0%D1%84%D1%81%D0%BE%D0%BD%D0%B0»

Категории: Численные методы | Оптимизация | Машинное обучение | Математические методы | Алгоритмы