Участник:N Zakharov/Метод Ньютона для решения систем нелинейных уравнений

Метод Ньютона
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ 000 }[/math]
Объём входных данных	[math]\displaystyle{ 000 }[/math]
Объём выходных данных	[math]\displaystyle{ 000 }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ 000 }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ 000 }[/math]

Илья Ильич слез с дивана, но по-прежнему ждет Захара.

Свойства и структура алгоритма

Общее описание алгоритма

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

Историческая справка

Метод был описан Исааком Ньютоном в рукописи «Об анализе уравнениями бесконечных рядов» (лат. «De analysi per aequationes numero terminorum infinitas»), адресованной в 1669 году Барроу, и в работе «Метод флюксий и бесконечные ряды» (лат. «De metodis fluxionum et serierum infinitarum») или «Аналитическая геометрия» (лат. «Geometria analytica») в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения [math]\displaystyle{ x_{n} }[/math], а последовательность полиномов и в результате получал приближённое решение [math]\displaystyle{ x }[/math].

Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе «Общий анализ уравнений» (лат. «Analysis aequationum universalis»). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений [math]\displaystyle{ x_{n} }[/math] вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

В 1879 году Артур Кэли в работе «Проблема комплексных чисел Ньютона — Фурье» (англ. «The Newton-Fourier imaginary problem») был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

Математическое описание алгоритма

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

Пусть необходимо найти решение системы:

[math]\displaystyle{ \left\{\begin{matrix}f_1(x_1, ..., x_n) = 0 \\ ... \\ f_n(x_1, ..., x_n) = 0, \end{matrix}\right. }[/math]

где [math]\displaystyle{ f_i : \mathbb{R}^n \rightarrow \mathbb{R} }[/math] - непрерывно дифференцируемое отображение в окрестности решения.

При начальном приближении [math]\displaystyle{ x_0 }[/math] и сделанных предположениях [math]\displaystyle{ (k+1) }[/math]-я итерация метода будет выглядеть следующим образом: [math]\displaystyle{ x_{k+1} = x_k - [f'(x_k)]^{-1}f(x_k) }[/math]

Литература

<references \>