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

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

Авторы: Гирняк О.Р., Васильков Д.А.

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

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

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

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

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

Рассмотрим систему нелинейных уравнений

[math]F(x) = 0, F(x), x \in \mathbb{R}^{n}, (1)[/math]

и предположим, что существует вектор [math]\bar{x} \in D \subset \mathbb{R}^{n}[/math], являющийся решением системы (1).

Будем считать, что [math]F(x) = (f_1(x), f_2(x), ... f_n(x))^T[/math], причем [math]f_i(\cdot) \in C^1(D) \forall i[/math]

Разложим [math]F(x)[/math] в окрестности точки [math]\bar{x}: F(x) = F(x^0) + F'(x^0)(x-x^0) + o(||x-x^0||)[/math]. Здесь [math]F'(x) = \frac{\partial{F(x)}}{\partial{x}} = \begin{pmatrix} \frac{\partial{f_1(x_1)}}{\partial{x_1}} & \frac{\partial{f_1(x_2)}}{\partial{x_2}} & \cdots & \frac{\partial{f_1(x_n)}}{\partial{x_n}} \\\frac{\partial{f_2(x_1)}}{\partial{x_1}} & \frac{\partial{f_2(x_2)}}{\partial{x_2}} & \cdots & \frac{\partial{f_2(x_n)}}{\partial{x_n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{f_n(x_1)}}{\partial{x_1}} & \frac{\partial{f_n(x_2)}}{\partial{x_2}} & \cdots & \frac{\partial{f_n(x_n)}}{\partial{x_n}} \end{pmatrix} [/math]