Фрактал Ньютона

Метод Ньютона ищет корень многочлена $p$, повторяя один и тот же шаг из начальной точки $z_0$:

Каждый пиксель изображения — начальная точка комплексной плоскости. Он получает цвет корня, в круг которого попадает первым. Для каждого круга есть доказанная гарантия: по γ-теореме Смейла метод Ньютона из любой точки внутри него сходится к соответствующему корню, поэтому цвет никогда не выбирается по догадке «какой корень ближе». Вокруг простого корня $\zeta$ круг имеет радиус $(3-\sqrt7)/(2\gamma)$, где $\gamma = \max_{k\ge2}\bigl|p^{(k)}(\zeta)/(k!\,p'(\zeta))\bigr|^{1/(k-1)}$.

Оттенок показывает, сколько шагов нужно начальной точке, чтобы попасть в круг; распределение светлых и тёмных тонов зависит от выбранного оформления. Тонкие линии отмечают границы «начальных точек, попадающих в круг не более чем за k шагов» — уровней, которые красная кнопка показывает по очереди. Чёрный означает лишь, что начальная точка не попала ни в один круг за выполненные шаги. Плавные оттенки, свечение вдоль границы и золотая сетка оформления «Позолота» — только визуальные эффекты; то, к какому корню приходит пиксель и за сколько шагов, — численные результаты 32-битных вычислений.

Полный бассейн притяжения корня состоит из всех начальных точек, которые в итоге к нему приходят, включая небольшие участки вдали от корня. У всех этих бассейнов одна и та же граница: множество Жюлиа отображения $N$. Поэтому сколь угодно близко к любой точке границы есть начальные точки, приходящие к каждому из корней. Именно поэтому цвета чередуются на любом масштабе, а режим показа всего бассейна одного корня показывает его в каждой бусине вдоль границы.

Вблизи этой границы несколько шагов метода Ньютона могут далеко разнести соседние начальные точки. В примере «На волосок друг от друга» для $z^3-1$ расстояние между двумя начальными точками равно 0.02, после одного шага — 0.047, а после двух — 0.268; они попадают в круги разных корней на шагах 6 и 7.

Когда корней всего два, картина проста: граница — серединный перпендикуляр к отрезку между двумя корнями. В координате $w = (z-1)/(z+1)$ (корни в ±1) шаг Ньютона принимает вид $w \mapsto w^2$. С третьим корнем граница становится фрактальной.

Для $p(z) = z^3 - 2z + 2$ начальная точка 0 переходит в 1 и обратно в 0 бесконечно: это цикл, мультипликатор $N'(0)\,N'(1)$ которого равен 0, поэтому любая достаточно близкая к нему начальная точка тоже в него попадает. Эти точки образуют чёрные островки; они никогда не приходят к корню.

Где могут появиться такие циклы? $N' = p\,p''/p'^2$ обращается в нуль в каждом корне, поэтому каждый корень — критическая точка $N$ и лежит в собственном бассейне. Остальные критические точки — свободные критические точки — это нули $p''$, не являющиеся корнями; там, где $p'$ тоже обращается в нуль, $N$ имеет кратный полюс, который по-прежнему является критической точкой и переходит в ∞. По теореме Фату каждый притягивающий цикл притягивает хотя бы одну критическую точку. Цикл, не являющийся корнем, не может притягивать корень, который остаётся в своём бассейне, поэтому он должен притягивать свободную критическую точку. Таким образом, наблюдение за свободными критическими точками может выявить такие неудачи. В списке используются численные приближения; если нули нельзя надёжно разделить, результат для них указывается как неопределённый, без утверждения о кратной точке или полюсе. Обратное неверно: для $z^3-1$ свободная критическая точка 0 — также нуль $p'$; она переходит в ∞, отталкивающую неподвижную точку $N$, и чёрных островков нет.

При трёх корнях $p''$ имеет один нуль — центроид корней. Он является единственной свободной критической точкой, кроме случаев, когда сам является корнем (например, для $z^3-z$). Во вставке показана карта положений выбранного корня при двух остальных неподвижных: каждая точка получает цвет корня, в круг с доказанной гарантией сходимости которого попадает орбита центроида, когда выбранный корень помещён в эту точку, или чёрный цвет, если за 300 шагов она не попадает ни в один круг. В этом семействе кубических многочленов чёрные блоки показывают небольшие копии структуры множества Мандельброта, впервые замеченные в компьютерных экспериментах Карри, Гарнетта и Салливана (1983). Перетащите выбранный корень сквозь один из них, и чёрные островки на изображении будут появляться и исчезать. При перемещении корня 1 многочлена $z^3-2z+2$ влево по вещественной оси сквозь его блок (пример «Сквозь чёрный блок») период цикла удваивается, 2 → 4 → 8, примерно при −1.8045 и −1.832 (численно) — как вдоль вещественной оси множества Мандельброта.

В 1879 году Артур Кэли задал вопрос: какой корень находит метод Ньютона из заданной комплексной начальной точки? Он решил задачу для двух корней, а случай трёх оказался трудным. Пьер Фату и Гастон Жюлиа построили теорию итераций рациональных отображений примерно в 1918–1920 годах, задолго до компьютерных изображений. Изображения бассейнов Ньютона и структуры, похожей на множество Мандельброта, в их пространстве параметров появились в начале 1980-х; оценки Стива Смейла (1986) дают используемые здесь доказанные круги.