Метод Ньютона

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

История

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

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

В XIX веке метод был строго обоснован в рамках математического анализа, а в XX веке, с развитием вычислительной техники, стал одним из ключевых алгоритмов численного анализа.

Математическая формулировка

Пусть дана вещественная функция \( f(x) \), определённая на некотором интервале, и требуется найти её корень \( x^ \), такой что \( f(x^) = 0 \). Метод Ньютона строит последовательность приближений \( \{x_k\} \) по следующей рекуррентной формуле:

\[ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}, \quad k = 0, 1, 2, \dots \]

где \( f'(x_k) \) — производная функции \( f \) в точке \( x_k \), а \( x_0 \) — начальное приближение (выбирается пользователем).

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

Геометрически метод Ньютона означает следующее: в текущей точке \( (x_k, f(x_k)) \) к графику функции проводится касательная прямая. Точка пересечения этой касательной с осью абсцисс (осью \( x \)) даёт следующее приближение \( x_{k+1} \). Отсюда происходит название «метод касательных».

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

Метод Ньютона сходится (то есть последовательность \( x_k \) стремится к корню \( x^* \)) при выполнении следующих условий (теорема о сходимости метода Ньютона):

1. Функция \( f(x) \) дважды непрерывно дифференцируема на отрезке \( [a, b] \).
2. На этом отрезке существует корень \( x^* \) (то есть \( f(a) \cdot f(b) < 0 \)).
3. Первая производная \( f'(x) \) не обращается в ноль на \( [a, b] \) (корень простой).
4. Вторая производная \( f''(x) \) сохраняет знак на \( [a, b] \) (функция выпукла или вогнута).
5. Начальное приближение \( x_0 \) выбрано достаточно близко к корню.

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

Случаи расходимости и потери устойчивости

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

• Нулевая производная в точке приближения: если \( f'(x_k) = 0 \), формула теряет смысл (деление на ноль). Графически это означает, что касательная горизонтальна и не пересекает ось \( x \).
• Плохое начальное приближение: если \( x_0 \) выбрано далеко от корня, метод может «зациклиться» (попасть в бесконечный цикл) или уйти к другому корню.
• Кратный корень: если корень \( x^ \) является кратным (то есть \( f'(x^) = 0 \)), скорость сходимости падает до линейной, и метод может работать медленно.
• Функция с разрывами или точками перегиба: метод может не сходиться к корню, если функция имеет разрыв или резкое изменение выпуклости.

Алгоритм

На практике алгоритм метода Ньютона реализуется следующим образом:

1. Выбор начального приближения: \( x_0 \). Обычно выбирается на основе анализа графика функции или из физических соображений.
2. Итерационный цикл: для \( k = 0, 1, 2, \dots \) выполнять:

• Вычислить \( f(x_k) \) и \( f'(x_k) \).
• Если \( |f(x_k)| < \varepsilon_1 \) (заданная точность по функции) или \( |x_{k+1} - x_k| < \varepsilon_2 \) (заданная точность по аргументу), то остановиться и считать \( x_k \) корнем.
• Иначе вычислить \( x_{k+1} = x_k - f(x_k) / f'(x_k) \).

1. Вывод результата: \( x_k \) как приближённое значение корня.

Модификации и обобщения

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

Метод обобщается на случай системы \( n \) нелинейных уравнений с \( n \) неизвестными. В этом случае вместо производной используется матрица Якоби (матрица частных производных). Итерационная формула принимает вид:

\[ \mathbf{x}_{k+1} = \mathbf{x}_k - [J(\mathbf{x}_k)]^{-1} \mathbf{F}(\mathbf{x}_k) \]

где \( \mathbf{F} \) — вектор-функция, \( J \) — матрица Якоби. На каждом шаге требуется решать систему линейных алгебраических уравнений, что делает метод более затратным, но сохраняет квадратичную сходимость.

Упрощённый метод Ньютона

В этом варианте производная \( f'(x) \) вычисляется только один раз в начальной точке \( x_0 \) и затем используется на всех итерациях. Это снижает вычислительные затраты, но скорость сходимости падает до линейной.

Метод Ньютона с регуляризацией (метод Левенберга — Марквардта)

Используется для решения плохо обусловленных задач или когда матрица Якоби близка к вырожденной. В формулу добавляется регуляризирующий параметр \( \lambda \), что улучшает устойчивость, но замедляет сходимость.

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

Метод Ньютона применяется для поиска экстремумов функций (минимума или максимума). В этом случае ищется корень градиента функции \( \nabla f(x) = 0 \). Итерационная формула использует матрицу Гессе (матрицу вторых производных):

\[ x_{k+1} = x_k - [H(x_k)]^{-1} \nabla f(x_k) \]

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

Применение

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

• Численный анализ: решение нелинейных уравнений и систем, поиск корней многочленов.
• Физика: решение уравнений движения, нахождение равновесных состояний, расчёт траекторий.
• Инженерные расчёты: моделирование механических и электрических цепей, расчёт прочности конструкций, аэродинамика.
• Экономика и финансы: расчёт внутренней нормы доходности, моделирование рыночного равновесия.
• Машинное обучение: обучение нейронных сетей (метод Ньютона для оптимизации, хотя чаще используются его приближения — квазиньютоновские методы, такие как L-BFGS).
• Компьютерная графика: трассировка лучей (нахождение пересечения луча с поверхностью).

Сравнение с другими методами

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

Интересные факты

• Метод Ньютона является частным случаем более общего метода итераций Ньютона — Канторовича, который обоснован в функциональном анализе.
• В некоторых учебниках метод Ньютона называют «методом касательных», а метод Ньютона — Рафсона — его модификацией для систем уравнений.
• Алгоритм метода Ньютона используется в калькуляторах для вычисления квадратного корня: \( x_{k+1} = \frac{1}{2} \left( x_k + \frac{a}{x_k} \right) \). Этот метод известен ещё со времён Вавилона (около 2000 лет до н. э.) и называется вавилонским методом.
• В случае комплексной переменной метод Ньютона может порождать фрактальные множества — так называемые бассейны Ньютона, которые являются одними из первых примеров фракталов, изучавшихся в математике.

Источники

1. Ньютон И. «Математические начала натуральной философии» (1687) — содержит основы метода флюксий.
2. Рафсон Дж. «Analysis aequationum universalis» (1690).
3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. «Численные методы» (2001).
4. Самарский А. А., Гулин А. В. «Численные методы» (1989).
5. Демидович Б. П., Марон И. А. «Основы вычислительной математики» (1970).
6. Кнут Д. Э. «Искусство программирования» (том 2, раздел 4.2.2) — описание вавилонского метода.