Метод Ньютона

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

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

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

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

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

Пусть задана некоторая функция [math]\ f(x) [/math], её производная [math]\ f'(x) [/math] и сетка на комплексной плоскости вида

[math] z_0 = \left( x_0 + \alpha \dfrac{x_1 - x_0}{N} \right) + i \cdot \left( y_0 + \beta \dfrac{y_1 - y_0}{M} \right), \qquad \alpha = \overline{1, N},\ \beta = \overline{1, M}, [/math]

где [math]\ i [/math] — мнимая единица.

Получим решения уравнения [math]\ f(z) = 0 [/math] с помощью итерационного процесса, определяемого формулой:

[math] z_{k+1} = z_k - \dfrac{f(z_k)}{f'(z_k)}, [/math]

где в качестве начального приближения [math]\ z_0[/math] перебираются всевозможные точки рассмотренной сетки.

1.2.1 Теоретическое обоснование

Пусть [math]\ F(x)[/math] — оператор, отображающий линейное нормированное пространство [math]H[/math] на линейное нормированное пространство [math]Y[/math]. Линейный оператор [math]P[/math], действующий из пространства [math]H[/math] в пространство [math]Y[/math], назовём производной оператора [math]F(x)[/math] в точке [math]x[/math], если

[math] \| F(x + \eta) − F(x) − P\eta \|_Y = o(\| \eta \|_H). [/math]

Будем обозначать такой оператор [math]P[/math] как [math]F′(x)[/math].

Пусть [math]\ X[/math] — решение уравнения [math]F(X) = 0[/math], [math]\ \Omega_a = \{ x: \| x - X \| \lt a \}[/math]. Пусть также при некоторых [math]a \gt 0,\ a_1 \ge 0,\ a_2 \le \infty[/math] выполнены условия:

[math]\label{requirement_one} \| (F'(X))^{-1} \|_{Y} \le a_1 \text{ при } x \in \Omega_a, [/math]

[math] \| F(u_1) - F(u_2) - F'(u_2)(u_1 - u_2) \|_{Y} \le a_2 \|u_2 - u_1 \|_{H}^{2} \text{ при } u_1, u_2 \in \Omega_a. [/math]

Обозначим [math]c = a_1 a_2[/math], [math]b = \min \{a, c^{-1}\}[/math].

Метод Ньютона применим на основании следующей теоремы:

Теорема. Если выполнены указанные условия и начальное приближение [math]x_0[/math] принадлежит [math]\Omega_b[/math], то итерационный процесс Ньютона

[math] x_{n + 1} = x_{n} - (F'(x_n))^{-1} F(x_n) [/math]

сходится с оценкой погрешности

[math] \| x_n - X \|_{H} \le c^{-1} \left( c \| x_0 - X \|_{H} \right)^{2^n}. [/math]

Доказательство этой теоремы можно найти в литературе.

1.3 Вычислительное ядро алгоритма

Вычислительную сложность алгоритма представляют операции вычисления значения функций в заданной точке, а так же операции вычитания и деления. При этом итерационный процесс запускается [math]N \cdot M[/math] раз, а количество итераций в каждом процессе, вообще говоря, не определено; наиболее популярными условиями останова являются следующие:

[math] \| z_{n + 1} - z_{n} \| \lt \varepsilon, [/math]

[math] | f(z_{n}) | \lt \varepsilon. [/math]

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

1.4 Макроструктура алгоритма

Для обеспечения параллелизма сперва исходная сетка разбивается на [math]n[/math] по возможности равных участков (например, на полосы длины [math]M[/math]). В каждом участке последовательно запускаются итерационные процессы для каждого узла сетки, в ходе которых:

• 1. вычисляются значения функций [math]\ f(z_k)[/math], [math]\ f'(z_k)[/math] (предполагается, что функции заданы аналитически);
• 2. вычисляется следующая точка:

[math] z_{k+1} = z_k - \dfrac{f(z_k)}{f'(z_k)}; [/math]

• 3. если условие останова не выполнено, переходим к шагу 1.

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

Последовательный алгоритм является частным случаем описанного алгоритма при [math]n = 1[/math].

3 Литература

<references \>