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

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

История и происхождение

Классический метод Ньютона, также известный как метод Ньютона — Рафсона, был разработан в XVII веке Исааком Ньютоном и усовершенствован Джозефом Рафсоном. Его основная идея заключается в линеаризации функции в окрестности текущего приближения с помощью разложения в ряд Тейлора и последующем решении линейного уравнения для нахождения следующего приближения. Для скалярного уравнения \( f(x) = 0 \) итерационная формула имеет вид: \[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. \] Для систем уравнений \( \mathbf{F}(\mathbf{x}) = \mathbf{0} \) формула обобщается: \[ \mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{J}(\mathbf{x}_n)]^{-1} \mathbf{F}(\mathbf{x}_n), \] где \( \mathbf{J} \) — матрица Якоби.

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

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

Для скалярного уравнения

Пусть требуется решить уравнение \( f(x) = 0 \), где \( f \) — непрерывно дифференцируемая функция. Выбирается начальное приближение \( x_0 \). В упрощённом методе Ньютона производная \( f'(x) \) вычисляется один раз в точке \( x_0 \): \[ k = f'(x_0). \] Тогда итерационная формула принимает вид: \[ x_{n+1} = x_n - \frac{f(x_n)}{k}, \quad n = 0, 1, 2, \dots \] Таким образом, на каждом шаге требуется только вычисление значения функции \( f(x_n) \), а деление на константу \( k \) выполняется быстро.

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

Для системы \( \mathbf{F}(\mathbf{x}) = \mathbf{0} \), где \( \mathbf{F}: \mathbb{R}^m \to \mathbb{R}^m \), упрощённый метод Ньютона записывается как: \[ \mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{J}(\mathbf{x}_0)]^{-1} \mathbf{F}(\mathbf{x}_n). \] Здесь \( \mathbf{J}(\mathbf{x}_0) \) — матрица Якоби, вычисленная в начальной точке. Обратная матрица \( [\mathbf{J}(\mathbf{x}_0)]^{-1} \) вычисляется один раз и затем используется на всех итерациях. Вместо явного обращения матрицы часто применяют LU-разложение, которое также выполняется однократно, а на каждом шаге решается система линейных уравнений с постоянной матрицей.

Свойства и сходимость

Скорость сходимости

Классический метод Ньютона обладает квадратичной сходимостью вблизи корня при выполнении условий регулярности (ненулевая производная). Упрощённый метод Ньютона, как правило, сходится линейно. Скорость сходимости зависит от того, насколько сильно матрица Якоби меняется в процессе итераций. Если функция почти линейна (т.е. производная меняется слабо), то упрощённый метод может сходиться почти так же быстро, как и классический. В случае сильно нелинейных функций сходимость может быть медленной или отсутствовать вовсе.

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

Для скалярного случая достаточные условия сходимости упрощённого метода Ньютона формулируются так: пусть \( f \) дважды непрерывно дифференцируема на отрезке \([a, b]\), \( f(a)f(b) < 0 \), \( f'(x) \neq 0 \) на \([a, b]\), и существует константа \( M \) такая, что \( |f''(x)| \le M \). Тогда, если начальное приближение \( x_0 \) выбрано достаточно близко к корню \( x^* \), итерационный процесс сходится. Однако радиус сходимости у упрощённого метода меньше, чем у классического.

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

Разновидности и модификации

Метод с периодическим обновлением матрицы

Для улучшения сходимости применяется вариант, при котором матрица Якоби пересчитывается не на каждом шаге, а через заданное число итераций (например, каждые 5–10 шагов). Это позволяет частично компенсировать изменение производной, сохраняя при этом выигрыш в вычислительных затратах.

Метод хорд (секущих)

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

Квазиньютоновские методы

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

Применение

Решение дифференциальных уравнений

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

Оптимизация

В задачах безусловной оптимизации, где требуется найти минимум функции \( \phi(\mathbf{x}) \), применяется метод Ньютона для поиска стационарных точек \( \nabla \phi(\mathbf{x}) = 0 \). Упрощённый вариант, в котором матрица Гессе (матрица вторых производных) вычисляется один раз, называется методом Ньютона с постоянной матрицей Гессе. Он используется в некоторых алгоритмах обучения нейронных сетей и в задачах подгонки кривых.

Инженерные расчёты

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

Достоинства и недостатки

Достоинства

• Снижение вычислительных затрат: основное преимущество — однократное вычисление производной (или матрицы Якоби) и её обращение. Для задач большой размерности это может давать выигрыш в десятки раз.
• Простота реализации: алгоритм легко программируется, не требует сложной логики для обновления матриц.
• Устойчивость к ошибкам округления: поскольку матрица не меняется, накопление ошибок округления при решении систем линейных уравнений может быть меньше, чем при частом пересчёте.

Недостатки

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

Источники

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином. Лаборатория знаний, 2008.
• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. — М.: Мир, 1975.
• Демидович Б. П., Марон И. А. Основы вычислительной математики. — М.: Наука, 1970.