Метод Ньютона: быстрый поиск корней с помощью итеративного приближения

У некоторых уравнений просто нет аккуратного алгебраического решения.

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

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

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

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

Что такое метод Ньютона?

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

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

Вот и вся идея. Нужна лишь разумная повторяемая формула обновления, которая сходится к ответу.

Формула метода Ньютона

Сердце метода Ньютона — это одно правило обновления, которое вы применяете снова и снова, пока не окажетесь достаточно близко к корню.

Вот формула:

Формула метода Ньютона

Каждая итерация берёт текущую оценку x_n и выдаёт лучшую, x_{n+1}. Вы продолжаете обновления, пока результат не окажется достаточно близок к нулю.

У формулы три компонента:

• x_n — ваша текущая оценка корня

• f(x_n) — значение функции в этой оценке

• f'(x_n) — производная функции в этой оценке, то есть наклон касательной

Если f(x_n) велико, вы далеко от корня. Если f'(x_n) крутая, функция быстро меняется, значит, можно сделать больший шаг. Отношение f(x_n) / f'(x_n) точно говорит, насколько сдвинуться — и вычтя его из текущей догадки, вы приблизитесь к корню.

Если f'(x_n) равно нулю или близко к нему, формула не сработает. Делить на ноль нельзя, а значит, метод не сможет выдать следующую оценку. Об этом подробнее — в разделе с ограничениями.

Как работает метод Ньютона

Метод Ньютона на каждой итерации повторяет одни и те же четыре шага.

1. Выберите начальную догадку: Возьмите начальное значение x_0 где-то рядом с корнем. Точности не требуется — достаточно быть достаточно близко, чтобы функция в этой области вела себя предсказуемо. В разделе о сходимости я поясню, что значит «достаточно близко».

2. Вычислите значение функции: Посчитайте f(x_0). Это показывает, насколько далеко функция от нуля при текущей оценке. Если f(x_0) = 0, вы закончили — корень найден.

3. Вычислите производную: Посчитайте f'(x_0). Это даёт наклон функции в точке x_0, то есть наклон касательной.

4. Обновите оценку: Примените правило обновления по формуле из предыдущего раздела.

И всё!

Новое значение x_1 — это точка пересечения касательной с осью x. Геометрически вы проводите прямую, касающуюся кривой в x_0, и следуете по ней вниз до нуля. Эта точка пересечения — ваша следующая, более точная догадка.

Дальше повторяйте. Подставьте x_1 обратно в шаги 2–4, чтобы получить x_2, затем x_3 и так далее. Каждая итерация строит новую касательную в обновлённой точке и находит, где она пересекает ось x.

Процесс останавливается, когда f(x_n) становится достаточно близким к нулю — обычно когда оно опускается ниже небольшого порога, заданного заранее.

Геометрическая интерпретация метода Ньютона

Представьте кривую на графике — это ваша функция f(x). Корень — это место, где кривая пересекает ось x. Вы пока не знаете, где именно это пересечение, поэтому начинаете с догадки x_0 где-то на оси x.

На каждом шаге вы отмечаете точку (x_0, f(x_0)) на кривой и проводите в ней касательную — прямую, которая касается кривой и имеет тот же наклон. Эта касательная не горизонтальна. Она наклонена, и если проследить её вниз, она пересечёт ось x в некоторой точке. Это и есть следующая оценка, x_1.

Затем повторяете. В x_1 проводите новую касательную и находите, где она пересекает ось x. Это даёт x_2. Каждая касательная — локальная линейная аппроксимация кривой, и каждая точка пересечения оказывается ближе к настоящему корню.

График ниже показывает две итерации метода Ньютона, применённого к f(x) = x^2 - 2, начиная с x_0 = 2.5:

Геометрическая интерпретация

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

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

Пошаговый пример метода Ньютона

Применим метод Ньютона к f(x) = x^2 - 2. Корень этой функции — x = sqrt(2) ≈ 1.4142, то есть мы вычисляем квадратный корень из 2.

Производная равна f'(x) = 2x, поэтому правило обновления становится таким:

Пример (правило обновления)

Начнём с начальной оценки x_0 = 2.5.

Итерация 1:

Пример (итерация 1)

Итерация 2:

Пример (итерация 2)

Итерация 3:

Пример (итерация 3)

Всего после трёх итераций мы получаем точность до четырёх знаков после запятой. Ошибка снизилась с 1.086 при x_0 до 0.0001 при x_3 — и продолжает уменьшаться на каждом шаге.

Вот как выглядят эта оценка и значения ошибки визуально:

Визуальный обзор оценки и ошибки

Левая панель показывает, как каждая оценка приближается к sqrt(2) ≈ 1.4142, а правая — как ошибка уменьшается в логарифмическом масштабе: каждая итерация примерно удваивает точность предыдущей.

Сходимость метода Ньютона

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

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

Для этого должны выполняться два условия:

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

Самый распространённый сбой — почти нулевая производная. 

Если f'(x_n) близка к нулю, вы делите в формуле обновления на очень маленькое число, и следующая оценка уходит далеко от корня. В худшем случае f'(x_n) = 0, и вычисления перестают работать, потому что на ноль делить нельзя.

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

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

Преимущества метода Ньютона

При подходящих условиях метод Ньютона трудно превзойти.

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

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

Ограничения метода Ньютона

За свою скорость метод Ньютона требует многого. Вот несколько ограничений, о которых стоит помнить:

• Требуется производная: Нужна аналитическая формула для f'(x), прежде чем запустить хотя бы одну итерацию. Если производную сложно вычислить (или её нет), понадобится иной подход.

• Чувствительность к начальной догадке: если вы начинаете слишком далеко от корня, метод может увести вас не туда.

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

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

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

Метод Ньютона и другие методы поиска корней

Метод Ньютона — не единственный способ найти корни и подходит не всегда.

Часто рассматривают ещё два метода: бисекцию и секущих. Кратко объясню их.

Метод бисекции

Метод бисекции — самый простой из трёх. Вы начинаете с интервала [a, b], в котором функция меняет знак — значит, где-то внутри есть корень. Затем вы многократно делите интервал пополам, оставляя ту половину, где сохраняется смена знака.

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

Метод секущих

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

Формула метода секущих

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

Применения метода Ньютона

Метод Ньютона встречается повсюду — в науке, инженерии и машинном обучении. Поясню, как именно.

Численное решение уравнений

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

Оптимизация

Найти минимум или максимум функции f(x) — значит найти, где её производная f'(x) = 0. Это задача поиска корня — следовательно, можно применить метод Ньютона. Просто запустите алгоритм на f'(x) вместо f(x), используя вторую производную f''(x) вместо первой.

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

Машинное обучение

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

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) — квазиньютоновский оптимизатор, который аппроксимирует вторую производную, чтобы не вычислять её напрямую. Это стандартный выбор для логистической регрессии и других выпуклых задач. Метод Ньютона также лежит в основе обновлений Ньютона–Рафсона, используемых при подгонке статистических моделей, таких как обобщённые линейные модели.

Физика и инженерия

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

Распространённые ошибки при использовании метода Ньютона

Большинство ошибок при использовании метода Ньютона сводятся к тем же четырём причинам. Перечислю их:

• Старт слишком далеко от корня: неудачная начальная догадка — самая частая причина расходимости или колебаний. Если вы плохо представляете, где находится корень, сначала постройте график функции. Это подскажет, откуда стартовать.

• Неправильная производная: правило обновления зависит от f'(x). Ошибочная производная — из-за просчёта или бага в коде — даёт неверные оценки уже с первой итерации, и ошибка накапливается.

• Отсутствие проверки деления на ноль. Если f'(x_n) равно нулю или становится очень маленьким, шаг обновления невозможен. Добавьте защиту в реализацию: если производная падает ниже заданного малого порога, остановитесь и сообщите о неудаче, вместо того чтобы выдавать бессмысленный результат.

• Слишком ранняя остановка. Прерывание итераций до сходимости оставляет ответ, который выглядит близким, но им не является. Задавайте критерий остановки по фактической ошибке — когда |f(x_n)| или |x_{n+1} - x_n| падает ниже порога, выбранного осознанно, а не просто по фиксированному числу итераций.

Выводы

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

За эту скорость приходится платить условиями. Нужны хорошая начальная догадка, не «плоская» функция, не «зазубренная» функция и ненулевая производная, чтобы добиться быстрой сходимости. Поймите эти условия — и вы будете знать, когда использовать метод Ньютона, а когда — что-то иное (например, бисекцию или метод секущих).

Лучший способ выработать интуицию — практиковаться на простых примерах. Начните с f(x) = x^2 - 2, попробуйте разные стартовые точки и посмотрите, что получится. Перейдите к функциям с несколькими корнями или плоскими участками и посмотрите, где метод даёт сбой.

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