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

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

История

Метод был впервые описан английским математиком Исааком Ньютоном в работе «Метод флюксий и бесконечных рядов» (лат. Methodus fluxionum et serierum infinitarum), написанной около 1669 года, но опубликованной посмертно в 1736 году. Ньютон предложил алгоритм для нахождения корней многочленов, используя разложение в ряд Тейлора и последующее отбрасывание членов высшего порядка.

В 1690 году английский математик Джозеф Рафсон опубликовал работу «Общий анализ уравнений» (лат. Analysis Aequationum Universalis), в которой представил более простую и современную формулировку метода, близкую к той, что используется сегодня. Рафсон предложил итерационную формулу, не требующую вычисления производных высших порядков, что сделало метод более практичным.

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

Описание метода

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

Пусть требуется найти корень непрерывно дифференцируемой функции \( f(x) \). Выбирается начальное приближение \( x_0 \), достаточно близкое к искомому корню. В точке \( (x_0, f(x_0)) \) строится касательная к графику функции. Точка пересечения этой касательной с осью абсцисс принимается за следующее приближение \( x_1 \). Процесс повторяется до достижения требуемой точности.

Итерационная формула

Для функции \( f(x) \), имеющей производную \( f'(x) \), итерационная формула метода Ньютона — Рафсона имеет вид:

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

Геометрически это соответствует построению касательной в точке \( x_n \) и нахождению её пересечения с осью \( x \).

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

Метод сходится, если выполнены следующие условия:

1. Функция \( f(x) \) непрерывно дифференцируема в окрестности корня.
2. Производная \( f'(x) \) не равна нулю в окрестности корня (корень является простым).
3. Начальное приближение \( x_0 \) выбрано достаточно близко к истинному корню.

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

Критерий остановки

Итерации прекращаются, когда выполняется одно из условий:

• \( |x_{n+1} - x_n| < \varepsilon \) — малость изменения приближения.
• \( |f(x_n)| < \varepsilon \) — малость значения функции.
• Достигнуто заданное максимальное число итераций.

Здесь \( \varepsilon \) — заданная точность вычислений.

Пример применения

Рассмотрим уравнение \( x^2 - 2 = 0 \), корнем которого является \( \sqrt{2} \approx 1.41421356 \). Функция \( f(x) = x^2 - 2 \), её производная \( f'(x) = 2x \). Выберем начальное приближение \( x_0 = 1.5 \).

Итерации:

1. \( x_1 = 1.5 - \frac{1.5^2 - 2}{2 \cdot 1.5} = 1.5 - \frac{2.25 - 2}{3} = 1.5 - \frac{0.25}{3} = 1.4166667 \)
2. \( x_2 = 1.4166667 - \frac{1.4166667^2 - 2}{2 \cdot 1.4166667} = 1.4166667 - \frac{2.006944 - 2}{2.833333} \approx 1.4142157 \)
3. \( x_3 = 1.4142157 - \frac{1.4142157^2 - 2}{2 \cdot 1.4142157} \approx 1.4142136 \)

Уже на третьей итерации получено значение с точностью до семи знаков после запятой.

Виды и модификации

Классический метод Ньютона

Описанный выше метод для скалярного уравнения. Требует вычисления производной на каждом шаге.

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

Для системы \( n \) нелинейных уравнений с \( 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}(\mathbf{x}_n) \) — матрица Якоби (матрица частных производных) системы. На практике вместо обращения матрицы решают систему линейных уравнений.

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

Производная вычисляется только один раз в начальной точке \( x_0 \) и используется на всех итерациях:

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_0)} \]

Это снижает вычислительные затраты, но уменьшает скорость сходимости (становится линейной).

Метод Ньютона с регуляризацией

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

Метод Ньютона — Рафсона для комплексных чисел

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

Применение

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

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

Преимущества и недостатки

Преимущества

• Высокая скорость сходимости (квадратичная) вблизи корня.
• Относительная простота реализации.
• Возможность обобщения на многомерные задачи.

Недостатки

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

Критика и альтернативы

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

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

Источники

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. «Численные методы». — М.: Бином. Лаборатория знаний, 2008.
• Калиткин Н. Н. «Численные методы». — М.: Наука, 1978.
• Самарский А. А., Гулин А. В. «Численные методы». — М.: Наука, 1989.
• Фаддеев Д. К., Фаддеева В. Н. «Вычислительные методы линейной алгебры». — М.: Физматгиз, 1963.
• 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.