Фрактал Ньютона: бассейны притяжения корней

Метод Ньютона: от чисел к фракталу

Метод Ньютона — один из первых численных алгоритмов: чтобы найти корень уравнения f(z) = 0, начни с любой точки и итерируй:

$z_{n+1} = z_n - \frac{f(z_n)}{f'(z_n)}$

Для вещественных чисел это работает надёжно: точка «скатывается» к ближайшему корню. Но что происходит, если применить тот же алгоритм ко всей комплексной плоскости?

Бассейны притяжения

Возьмём многочлен z³ − 1 = 0. Корни — три числа:

$z_0 = 1, \quad z_1 = e^{2\pi i/3}, \quad z_2 = e^{4\pi i/3}$

Для каждой начальной точки z₀ ∈ ℂ запустим итерацию. Зальём пиксель красным, если итерация сошлась к z₀ = 1, зелёным — к z₁, синим — к z₂. Яркость — скорость сходимости.

Результат: три цветных «бассейна» — области, тяготеющие к каждому корню. Кажется, что граница между ними должна быть простой линией. Но нет.

Граница — фрактал

В 1879 году Артур Кэйли поставил вопрос: есть ли простое правило, какому корню принадлежит та или иная точка? Он решил задачу для двух корней — там граница прямая. Но для трёх корней застрял и написал: «задача, по-видимому, требует значительного труда».

Труд занял 100 лет. Ответ дали Жюлиа и Фату в 1918–1919 годах, не видя изображений:

Граница между бассейнами — это множество Жюлиа для функции f.

Это значит: она фрактальная, с бесконечной сложностью. На границе нет ни одной «нейтральной» точки — каждая точка граничит сразу со всеми тремя бассейнами одновременно.

Что видно в анимации

z³ − 1: классический трёхлучевой фрактал Ньютона. Три бассейна расходятся от центра под углом 120°. Вблизи границ — бесконечное чередование всех трёх цветов.

z⁴ − 1: четыре корня ±1, ±i. Крестовая симметрия. Граница сложнее — тонкие язычки бассейнов проникают глубоко в соседние области.

z⁵ − 1 … z⁸ − 1: с ростом степени симметрия становится красивее, а граница — тоньше. При n = 8 паттерн напоминает снежинку.

Приближение: кликните вблизи границы двух бассейнов — на каждом масштабе будут видны новые детали той же сложности. Самоподобие.

Связь с Мандельброт и Жюлиа

Фрактал Ньютона — частный случай комплексной динамики. Итерационная функция

$F(z) = z - \frac{f(z)}{f'(z)}$

— это рациональная функция. Её «заполненное множество Жюлиа» — объединение всех бассейнов притяжения. Граница — классическое множество Жюлиа для F.

Множество Мандельброта — это «карта» параметров для семейства z² + c. Для метода Ньютона аналогичную карту можно построить, меняя коэффициенты многочлена.

→ Множество Мандельброта: z → z² + c, карта характеров → Множество Жюлиа: фиксируем c, меняем начальную точку