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

Метод Ньютона
Последовательный алгоритм
Последовательная сложность	[math]O(kn^3)[/math]
Объём входных данных	[math]2n+1[/math]
Объём выходных данных	[math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]000[/math]
Ширина ярусно-параллельной формы	[math]000[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]x_k = x_k + s_k[/math]

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

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

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

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

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

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

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

3 Литература

<references \>