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

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

Мно́жество Мандельбро́та — это множество таких точек c на комплексной плоскости, для которых итеративная последовательность z₀=0, z_n=z_n-1²+c (n=1, 2, 3, …) не уходит на бесконечность. То есть, это множество таких c, для которых существует действительное R, что неравенство |z_n|<R выполняется при всех натуральных n.

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

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

Таким образом, вышеуказанная последовательность может быть раскрыта для каждой точки $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» («Фрактальные объекты: форма, случайность и размерность»). В этой книге Мандельброт впервые использовал термин «фрактал» для обозначения математического феномена, демонстрирующего столь непредсказуемое и удивительное поведение. Эти феномены рождались при использовании рекурсивного алгоритма для получения какой-либо кривой или множества. Множество Мандельброта — один из таких феноменов, названный по имени своего исследователя.

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

Несложно доказать, что как только модуль z_n окажется больше 2 (или, в терминах действительной и мнимой частей, x_n²+y_n²>4), последовательность станет стремиться к бесконечности. В случае |c|≤2 это можно доказать с помощью метода математической индукции. При |c|>2 точка c заведомо не принадлежит множеству Мандельброта, что также можно вывести методом индукции, используя равенство z₀=0. (Хотя в этом случае может существовать другое z₀, для которого соответствующая последовательность ограничена по модулю, но для некоторого n выполняется неравенство |z_n|>2.)

Сравнение |z_n| с этим числом (в англоязычной литературе его называют «bail-out») позволяет выделять точки, не попадающие внутрь множества. Для точек, лежащих внутри множества, последовательность не будет иметь тенденции к бесконечности и никогда не достигнет этого числа, поэтому после определённого числа итераций расчёт необходимо принудительно завершить. Максимальное число итераций, после которых число считается попавшим внутрь множества, задается в программе.

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

Пример программы построения множества (на языке программирования PHP):

<?php
/* Множество Мандельброта. */
/* Время создания */
set_time_limit(120); 
function re_microtime() { 
    list($usec, $sec) = explode(" ", microtime()); 
    return ((float)$usec + (float)$sec); }
/* Засекаем */
$time_start = re_microtime(); 
 
/* Размер картинки */
$img_w = 900;
$img_h = 600;
 
/* Начало и конец чертежа */
$x_min = -2;
$x_max = 1;
$y_min = -1;
$y_max = 1;
 
/* Подсчёт шага */
if($x_min >= 0 && $x_max >= 0){ 
        $step = ($x_min + $x_max)/$img_w;
} elseif($x_min < 0 && $x_max >= 0) { 
        $step = ($x_max - $x_min)/$img_w;
} else {
        $step = (-$x_min + $x_max)/$img_w; }
 
$img = imagecreatetruecolor($img_w,$img_h);
$c = array();
 
$yy = 0;
for($y = $y_min; $y < $y_max; $y = $y + $step){
        $xx = 0;
        for($x = $x_min; $x < $x_max; $x = $x + $step){
 
                $c['x'] = $x;
                $c['y'] = $y;
                $X = $x;
                $Y = $y;
                $ix=0; $iy=0; $n=0;
 
                while(($ix*$ix + $iy*$iy < 5) and ($n < 64)){
                        $ix = $X*$X - $Y*$Y + $c['x'];
                        $iy = 2*$X*$Y + $c['y'];
                        $X = $ix;
                        $Y = $iy;
                        $n++;
                }
 
                $col = imagecolorallocate($img, 255-$n*5, 0, 0);
                imagesetpixel($img, $xx, $yy, $col);
 
        $xx++; }
$yy++; }
 
$time_end = re_microtime(); 
header("Content-type: image/png");
/* выводим в заголовках время создания */
header ("X-Exec-Time: ".($time_end - $time_start)); 
imagepng($img);
imagedestroy($img);
?>

Пример программы построения множества (на языке программирования C#):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Mnoj
{
    class Program
    {
        static void Main(string[] args)
        {
            double realCoord, imagCoord;
            double realTemp, imagTemp, realTemp2, arg;
            int iterations;
            for (imagCoord = 1.2; imagCoord >= -1.2; imagCoord -= 0.05)
            {
                for (realCoord = -0.6; realCoord <= 1.77; realCoord += 0.03)
                {
                    iterations = 0;
                    realTemp = realCoord;
                    imagTemp = imagCoord;
                    arg = (realCoord * realCoord) + (imagCoord * imagCoord);
                    while ((arg < 4) && (iterations < 40))
                    {
                        realTemp2 = (realTemp * realTemp) - (imagTemp * imagTemp) - realCoord;
                        imagTemp = (2 * realTemp * imagTemp) - imagCoord;
                        realTemp = realTemp2;
                        arg = (realTemp * realTemp) + (imagTemp * imagTemp);
                        iterations += 1;
                    }
                    switch (iterations % 4)
                    {
                        case 0:
                            Console.Write(".");
                            break;
                        case 1:
                            Console.Write("o");
                            break;
                        case 2:
                            Console.Write("0");
                            break;
                        case 3:
                            Console.Write("@");
                            break;
                    }
                }
                Console.Write("\n");
            }
            Console.ReadKey();
        }
    }
}

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

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

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

Порядок определения, попадает ли точка z₀ внутрь множества (традиционно закрашиваемого чёрным цветом) или нет (закрашивается цветом, зависящим от скорости движения к бесконечности) следующий: на каждой итерации для z_n=x_n+y_n·i вычисляется значение модуля $|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|² ≤ 4 при любом числе итераций (на практике — при всех вычисленных итерациях), то цвет точки чёрный, в противном случае он зависит от последнего значения n, при котором |z_n|² ≤ 4. Значение n, фактически, обозначает скорость движения z_n в бесконечность, и может быть просто индексом в таблице цветов, или использоваться как параметр в более сложном алгоритме.

Данный алгоритм определяет, что если точка удаляется больше чем на 2 от начала координат, то она лежит снаружи множества Мандельброта. Для того, чтобы определить, что точка лежит внутри множества есть много способов. Самое простое решение — ограничить количество итераций неким максимумом. Если точка не вышла за указанную границу, можно считать, что она находится внутри множества.

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

Пример добавления цвета (на PHP):

<?php
 
// Default: http://<host>/<dir>/<filename>.php?iter1=64&width=600&height=400&coef=32
 
function BN($n, $l, $r) {return $n>$l && $n<=$r;}
function SQR($a) {return $a*$a;}
 
define("COEF",  $_GET["coef"]);
$iter1  =       $_GET["iter1"];
$width  =       $_GET["width"];
$height =       $_GET["height"];
 
header("Content-type: image/png");
 
$img    =       imagecreatetruecolor($width, $height);
$iter2  =       0.01/($width/300);
$yy     =       -1;
 
for ($y = -1; $y < 1; $y = $y + $iter2) {
        $yy++; $xx=-1;
        for($x = -2; $x < 1; $x = $x + $iter2) {
                $xx++;
                $Cx     =       $x;
                $Cy     =       $y;
                $X      =       $x;
                $Y      =       $y;
                $ix     =       0;
                $iy     =       0;
                $n      =       0;
                while ((SQR($ix) + SQR($iy) < 4) and ($n < $iter1)) {
                        $ix     =       SQR($X) - SQR($Y) + $Cx;
                        $iy     =       2*$X*$Y + $Cy;
                        $X      =       $ix;
                        $Y      =       $iy;
                        $n++;
                }
                if(BN($n,0,7)) $col = imagecolorallocate($img,COEF*$n,0,0);
                elseif(BN($n,7,14)) $col = imagecolorallocate($img,COEF*$n,COEF*$n,0);
                elseif(BN($n,14,21))$col = imagecolorallocate($img,COEF*$n,0,COEF*$n);
                elseif(BN($n,21,28))$col = imagecolorallocate($img,0,COEF*$n,0);
                elseif(BN($n,28,35))$col = imagecolorallocate($img,COEF*$n,COEF*$n,0);
                elseif(BN($n,35,42))$col = imagecolorallocate($img,0,COEF*$n,COEF*$n);
                elseif(BN($n,42,49))$col = imagecolorallocate($img,0,0,COEF*$n);
                elseif(BN($n,49,56))$col = imagecolorallocate($img,COEF*$n,0,COEF*$n);
                elseif(BN($n,56,64))$col = imagecolorallocate($img,0,COEF*$n,COEF*$n);
                imagesetpixel($img, $xx, $yy, $col);
        }
}
imagepng($img);
imagedestroy($img);
?>

Оптимизация

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

$\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)\!$ попадает внутрь множества и закрашивается чёрным цветом, а итеративные вычисления можно пропустить.

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

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

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

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

Увеличение на границе множества Мандельброта формирует изображения, аналогичное множеству Жюлиа

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

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

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

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

Зачастую под названием «Множество Мандельброта» понимается только множество, описанное выше. Однако любая функция комплексной переменной имеет соответствующее множество Мандельброта, которое также характеризуется наличием или отсутствием связного множества Жюлиа. Например, можно положить f_c(z)=z³+c. Тогда для каждого значения c проверяется связность множества Жюлиа функции f_c, и при наличии связности считается, что c принадлежит множеству Мандельброта. В описанном случае связность можно проверить тем же способом, что и для f_c(z)=z²+c.

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

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

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

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

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

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

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

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

Литература

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

См. также

• Лампочка Мандельброта

Ссылки

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

• Множества Мандельброта и Жюлиа на сайте FractalWorld
• Benoit Mandelbrot: Fractals and the art of roughness, запись выступления на конференции TED
• Mandelbrot 4.0 — бесплатная (под общественной лицензией GNU) программа для создания Множества Мандельброта и Множества Жюлиа