Метод Ньютона (Newton method)

Синонимы: Метод касательных, Алгоритм Ньютона

Разделы: Алгоритмы

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

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

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

Алгоритм

1. Задается начальное приближение $X_0$.
2. Пока не выполнено условие остановки, в качестве которого можно взять $|X_{n+1}-X_n|<\epsilon$ или $|f^{\prime }\left(X_{n+1}\right)|<\epsilon$ (то есть погрешность в нужных пределах), вычисляют новое приближение:

$X_{n+1}=X_n-\frac{f\left(X_n\right)}{f^{\prime }\left(X_n\right)}$.

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