Множество мандельброта

Множество Мандельброта

В математике мно́жество Мандельбро́та — это фрактал, определённый как множество точек $c\!$ на комплексной плоскости, для которых итеративная последовательность

$z_0 = 0\!$

$z_{n+1} = {z_n}^2 + c\!$

не уходит на бесконечность.

Расширенное определение

Таким образом, вышеуказанная последовательность может быть раскрыта для каждой точки $c\!$ на комплексной плоскости следующим образом:

$c=x+i \cdot y \,$

$Z_0=0 \,$

$\begin{matrix}Z_1&=&Z_0^2+c \\ \ &=& x+iy\end{matrix} \,$

$\begin{matrix}Z_2&=&Z_1^2+c \\ \ &=&(x + iy)^2+x+iy \\ \ &=&x^2+2ixy-y^2+x+iy \\ \ &=&x^2-y^2+x+(2xy+y)i\end{matrix} \,$

$Z_3=Z_2^2+c=... \,$

и так далее.

Если переформулировать эти выражения в виде итеративной последовательности значений координат комплексной плоскости $x\!$ и $y\!$, т. е. заменив $z_n\!$ на $x_n + i \cdot y_n$, а $c\!$ на $p + i \cdot q\!$, мы получим:

$x_{n+1} = {x_n}^2 - {y_n}^2 + p \,$

$y_{n+1} = 2{x_n} {y_n} + q \,$

Визуально, внутри множества Мандельброта можно выделить бесконечное количество элементарных фигур, причём самая большая в центре представляет собой кардиоиду. Также есть набор кругов, касающихся кардиоиды, размер которых постепенно уменьшается, стремясь к нулю. Каждый из этих кругов имеет свой набор меньших кругов, диаметр которых также стремится к нулю и т. д. Этот процесс продолжается бесконечно, образуя фрактал. Также важно, что эти процессы ветвления фигур не исчерпывают полностью множество Мандельброта: если рассмотреть с увеличением дополнительные «ветки», то в них можно увидеть свои кардиоиды и круги, не связанные с главной фигурой. Самая большая фигура (видимая при рассматривании основного множества) из них находится в области от −1,78 до −1,75 на отрицательной оси действительных значений.

История множества Мандельброта

Впервые множество Мандельброта было описано в 1905 году Пьером Фату (Pierre Fatou), французским математиком, работавшим в области аналитической динамики комплексных чисел. Фату изучал рекурсивные процессы вида

$z \to z^2 + c\,$

Начав с точки $z_0\!$ на комплексной плоскости, можно получить новые точки, последовательно применяя к ним эту формулу. Такая последовательность точек называется орбитой $z_0\!$ при преобразовании $z \to z^2 + c\,$

Фату нашел, что орбита $z_0 = 0\!$ при этом преобразовании показывает достаточно сложное и интересное поведение. Существует бесконечное множество таких преобразований — своё для каждого значения $c\!$. В те времена компьютеров ещё не было, и Фату, конечно, не мог построить орбиты всех точек плоскости, ему приходилось всё делать вручную. Основываясь на своих расчётах, он доказал, что орбита точки, лежащей на расстоянии больше 2 от начала координат, всегда уходит в бесконечность.

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

Фракталы были описаны Мандельбротом в 1975 году в его книге «Les Objets Fractals: Forme, Hasard et Dimension» («Фрактальные объекты: форма, случайность и размерность»). В этой книге Мандельброт впервые использовал термин «фрактал» для обозначения математического феномена, демонстрирующего столь непредсказуемое и удивительное поведение. Эти феномены рождались при использовании рекурсивного алгоритма для получения какой-либо кривой или множества. Множество Мандельброта — один из таких феноменов, названный по имени своего исследователя.

Взаимодействие с множеством Жюлиа

Фрагмент множества Мандельброта, лежащий в районе его границы

Множество Мандельброта изначально было построено как каталог множеств Жюлиа: каждой точке на комплексной плоскости соответствует своё множество Жюлиа. Точки, лежащие внутри множества Мандельброта, точно соответствуют связным множествам Жюлиа, а точки снаружи — несвязным.

Отсюда понятно, что интересные варианты множества Жюлиа соответствуют точкам, лежащим на границе множества Мандельброта. Точки глубоко внутри образуют простые геометрические фигуры, а внешние выглядят как пыль, окружающая цветные пятна. Некоторые программы, например, Fracint, позволяют пользователю прямо на экране указать точку, для которой необходимо построить соответствующее множество Жюлиа, упрощая поиск красивых изображений.

Множество Мандельброта и само содержит структуры, напоминающие множество Жюлиа: для любого $c\!$ область множества Мандельброта около $c\!$ напоминает центр множества Жюлиа с параметром $c\!$.

Построение множества

Было доказано, что как только модуль $z_n\!$ окажется больше 2 (или в терминах действительной и мнимой частей $\sqrt {x^2 + y^2} > 2\!$), последовательность станет стремиться к бесконечности. Сравнение $|z_n|\!$ с этим числом (в англоязычной литературе его называют «bail-out») позволяет выделять точки, не попадающие внутрь множества. Для точек, лежащих внутри множества, последовательность не будет иметь тенденции к бесконечности и никогда не достигнет этого числа, поэтому после определённого числа итераций расчёт необходимо принудительно завершить. Максимальное число итераций, после которых число считается попавшим внутрь множества, задается в программе.

Изображение, полученное таким способом, является лишь приближением к реальному множеству Мандельброта. Более качественные результаты можно получать, увеличивая максимальное количество итераций, однако при этом пропорционально вырастает и время расчётов.

Пример программы построения множества (

Добавление цвета

Строго математически, изображения множеств Мандельброта и Жюлиа должны быть чёрно-белыми. Точка либо попадает внутрь множества, либо нет. Несмотря на это, с помощью компьютера мы можем построить и цветные изображения. Самым распространённым способом является раскрашивание точек снаружи множества в цвет, равный количеству итераций, за которое точка уходит в «бесконечность» или, с точки зрения программы, на определённое расстояние от нуля.

Порядок определения, попадает ли точка $z_0\!$ внутрь множества (традиционно закрашиваемого чёрным цветом) или нет (закрашивается цветом, зависящим от скорости движения к бесконечности) следующий: на каждой итерации для $z_n = x + i \cdot y \!$ вычисляется значение модуля $|z_n| = \sqrt{x_n^2 + y_n^2}$, которое затем сравнивается с «границей бесконечности» (обычно берётся значение, равное 2). Здесь важно обратить внимание, что уже на данном этапе можно ввести определённую оптимизацию вычислений, если сравнивать не $\sqrt{x_n^2 + y_n^2} > 2$, а $x_n^2 + y_n^2 > 4\!$, что значительно снизит время расчётов.

Таким образом, если $|z_n|^2 < 4\!$ при любом числе итераций, то цвет точки чёрный, в противном случае он зависит от последнего значения $n\!$. Значение $n\!$, фактически, обозначает скорость движения $z_n\!$ в бесконечность, и может быть просто индексом в таблице цветов, или использоваться как параметр в более сложном алгоритме.

Итак, мы получили алгоритм определения, лежит ли точка снаружи множества Мандельброта — это происходит, если она удаляется больше чем на 2 от начала координат. Каким же образом определить, что она лежит внутри множества? Это не так просто и для этого есть много способов. В этом суть проблемы. Если бы всё было по-другому, у нас бы не было столь большого количества разнообразных алгоритмов для построения множества Мандельброта. Самое простое решение — ограничить максимальное количество итераций. Если точка не вышла за указанную границу, можно считать, что она находится внутри множества.

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

Оптимизация

Одним из способов уменьшения объема вычислений при вычислении общей картины множества может служить проверка, попадает ли точка в область главной кардиоиды. Формула кардиоиды в полярных координатах выглядит следующим образом:

$\rho_c = {1 \over 2} - {1 \over 2} \cos \theta$

Таким образом, для точки $(x, y)\!$ необходимо вычислить

$\rho = \sqrt{\left( x - {1 \over 4} \right)^2 + y^2}$,

$\theta = \hbox{atn}_2 \left( y, x - {1 \over 4} \right)$,

$\rho_c = {1 \over 2} - {1 \over 2} \cos \theta$.

Если $\rho \le \rho_c$ то точка $(x, y)\!$ попадает внутрь множества и закрашивается чёрным цветом, а итеративные вычисления можно пропустить.

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

На практике наибольшее уменьшение объёма вычислений даёт трассировка границы: если есть некоторая замкнутая кривая, не пересекающая ось абсцисс, каждая точка которой уходит за предел bailout за одинаковое число итераций или наоборот принадлежит множеству Мандельброта, то любая точка внутри этой кривой будет обладать тем же свойством, и следовательно вся область внутри границы закрашивается одинаковым цветом.

Применение множества Мандельброта в искусстве

Поиск красивых изображений множества Мандельброта — интересное хобби для очень многих людей. Они собирают коллекции таких изображений, причём каждое из них может быть описано небольшим количеством параметров, например, просто координатами центра.

Есть большое количество программ для рисования фракталов, но, несмотря на это, многие люди пишут свои программы для большей гибкости при экспериментах.

Вариации множества Мандельброта

Фрактал Жюлиа

Зачастую, под названием «Множество Мандельброта» понимается только множество, описанное выше. Но на самом деле, любая функция комплексной переменной имеет соответствующее множество Мандельброта, которое также характеризуется наличием или отсутствием связного множества Жюлиа.

Например:

$f_c(z) = z^3 + c\!$.

Для каждого значения $c\!$ ищется соответствующее связное множество Жюлиа, и при его наличии считается, что $c\!$ попадает внутрь множества Мандельброта.

Эти утверждения можно обобщить и на множества Жюлиа, определяемые больше, чем двумя числами. Например, множество Жюлиа, определяемое тремя действительными числами, имеет соответствующее трёхмерное множество Мандельброта.

Математические факты о множестве Мандельброта

Множество Мандельброта является связным, хотя в это и трудно поверить, глядя на хитрые системы мостов, соединяющие различные его части.

Число итераций очень близко к логарифму электрического потенциала, который возникает, если зарядить множество Мандельброта. Точнее, предел ln(ln( | z_n | ) / 2ⁿ) + const совпадает с этим потенциалом.

Если сильно увеличить множество Мандельброта в граничной точке c и то же самое проделать с множеством Жюлиа для этого же значения c и в этой же точке, то картины будут асимптотически стремиться друг к другу при все больших увеличениях.

Литература

• Бенуа Мандельброт, Ричард Л. Хадсон (Не)послушные рынки: фрактальная революция в финансах = The Misbehavior of Markets. — М.: «Вильямс», 2005. — С. 400. — ISBN 5-8459-0922-8