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

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

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

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

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

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

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

$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},$

где $\ i$ — мнимая единица.

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

$z_{k+1} = z_k - \dfrac{f(z_k)}{f'(z_k)},$

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

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

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

$\| F(x + \eta) − F(x) − P\eta \|_Y = o(\| \eta \|_H).$

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

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

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

$\| 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.$

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

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

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

$x_{n + 1} = x_{n} - (F'(x_n))^{-1} F(x_n)$

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

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

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

3 Литература

<references \>