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

Метод Ньютона
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(kn^3) }[/math]
Объём входных данных	[math]\displaystyle{ 2n+1 }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/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 = (f_1, ..., f_n) : \mathbb{R}^n \rightarrow \mathbb{R}^n }[/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]

Проекционные итерационные методы основываются на тех же принципах, что и методы, которые используются для задач поиска собственных значений. На самом деле, многие методы Крылова напрямую вытекают из алгоритмов Арнольди. Приближенное решение можно найти по формуле [math]\displaystyle{ \tilde{x} = x_0 + V_my }[/math], а после подставления условий Петрова-Гарелкина оно принимает вид [math]\displaystyle{ \tilde{x} = x_0 + V (W^TAV)^{-1}W^Tr_0 }[/math], где [math]\displaystyle{ r_0 = b - Ax_0 }[/math], [math]\displaystyle{ V = \{v_1, v_2, ..., v_m\} }[/math] - матрица, чьи столбцы являются ортонормированным базисом пространства, а матрица [math]\displaystyle{ W }[/math] находится из соотношения [math]\displaystyle{ W^HV = I }[/math].
[math]\displaystyle{ V^T_mAV_m = H_m }[/math]
[math]\displaystyle{ G(y) = \left \| b-Ax \right \| = \left \| b-A(x_0+V_my) \right \| = \left \| r_0 -AV_my \right \| }[/math]

Схема реализации последовательного алгоритма

Выбор начального приближения [math]\displaystyle{ x_k }[/math]

Вычисление вектора [math]\displaystyle{ F(x_k) }[/math]

WHILE (условие остановки не выполнено)

Вычисление якобиана [math]\displaystyle{ J(x_k) = F'(x_k) }[/math]

Решение линейной системы уравнений [math]\displaystyle{ J(x_k)s_k = -F(x_k) }[/math]

[math]\displaystyle{ x_k = x_k + s_k }[/math]

Вычисление вектора [math]\displaystyle{ F(x_k) }[/math]

Последовательная сложность алгоритма

На каждом шаге необходимо выполнить:

• Вычисление Якобиана : [math]\displaystyle{ O(n^2) }[/math]
• Решение СЛАУ методом Гаусса : [math]\displaystyle{ O(n^3) }[/math]
• Вычисление нового приближения
• Вычисление нового значения функции : [math]\displaystyle{ O(n^2) }[/math]

Если считать, что количество итераций равно [math]\displaystyle{ k }[/math], то общая сложность алгоритма равна [math]\displaystyle{ O(kn^3) }[/math]

Ресурс параллелизма алгоритма

Вообще говоря, метод Ньютона является последовательным методом, но на определенных шагах, таких как решение СЛАУ, приближенное вычисление Якобиана, можно применить идеи параллельных вычислений.

Входные и выходные данные алгоритма

Входные данные:
Объём входных данных:
Выходные данные:
Объём выходных данных:

Литература

<references \>