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

Метод Ньютона приближает корень f — число r с $f(r) = 0$ — повторением одного шага. Для текущего приближения $x_n$ возьмите касательную к графику в $(x_n, f(x_n))$, заданную формулой $L(x) = f(x_n) + f'(x_n)(x - x_n)$. Около $x_n$ касательная остаётся близко к кривой, поэтому её пересечение с осью x лучше приближает точку пересечения самой кривой. Решение $L(x) = 0$ даёт следующее приближение. На графике каждый шаг идёт от $x_n$ к кривой по бледному пунктиру, затем по касательной до оси.

Обозначим погрешность через $e_n = x_n - r$. Если r — простой корень ($f'(r) \ne 0$), а f имеет непрерывную вторую производную, разложение шага по Тейлору даёт $e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$, когда $x_n$ близко к r. Возведение погрешности в квадрат примерно удваивает число верных цифр. Для x² − 2 из x₀ = 1 погрешности равны 0.086, 0.0025, 2.1 × 10⁻⁶ и 1.6 × 10⁻¹²; показания демонстрируют, как $e_n/e_{n-1}^2$ устанавливается около $1/(2\sqrt2) \approx 0.354$. Вдали от корня такой гарантии нет. При $f''(r) = 0$ квадратичный член исчезает и сходимость ещё быстрее: для arctan x погрешность примерно равна $-\tfrac23 e_n^3$, то есть на каждом шаге возникает куб предыдущей погрешности.

Для шага необходимо $f'(x_n) \ne 0$. Горизонтальная касательная никогда не встречает ось, а почти горизонтальная встречает её далеко: для x² − 2 из 0.1 первый шаг попадает в 10.05. Метод может не сработать и без ухода вдаль. Для x³ − 2x + 2 касательная в 0 приводит в 1, а в 1 возвращает в 0; близкие к 0 начальные точки притягиваются к этому циклу: последовательность остаётся ограниченной, но предела не имеет. Для arctan x есть граница α ≈ 1.3917 — число, удовлетворяющее $2\alpha = (1 + \alpha^2)\arctan\alpha$. Начальные точки с |x₀| < α сходятся, а лежащие за границей каждый раз попадают ещё дальше на другой стороне. Переключатель «Все начальные точки» раскрашивает ось x по исходу для каждой начальной точки. Для x³ − 2x + 2 примерно пятая часть [−3, 3] попадает в цикл, в том числе узкие полосы, сгущающиеся к точкам с горизонтальной касательной $\pm\sqrt{2/3}$. Если начать с комплексных чисел, эти полосы превращаются во фрактал Ньютона.

У кратного корня также выполняется $f'(r) = 0$, и квадратичная сходимость теряется. Для $(x - 1)^2$ шаг в точности равен $x_{n+1} = (x_n + 1)/2$, поэтому погрешность уменьшается вдвое на каждом шаге. Это линейная сходимость: примерно 3.3 шага на каждый новый десятичный знак. Около корня кратности m отношение $e_{n+1}/e_n$ стремится к $(m - 1)/m$.