Алгоpитм постpоения множества мандельбpота


Содержание

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

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

Рассмотрим функцию fc:C→C, c∈C. Множество Мандельброта M(f) определяется как множество всех c∈C , для которых орбита точки z=0 при отображении fc(z) ограничена. Наиболее часто используется fc(z)=z 2 +c. Раскладывая на действительную и мнимую часть, получаем:

Re: x 2 -y 2 +a
Im: 2xy+b

приняв, что z=x+yi и c=a+bi. Цвет обычно выбирают по числу итераций, но есть и другие способы.

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

  • действительная часть z меньше определённого числа;
  • мнимая часть z меньше определённого числа;
  • и мнимая, и действительная части z меньше какого-либо числа.

Есть и другие способы.
Ниже приведены изображения для fc(z)=z n +c

Множество Жулиа

Удивительно, но множества Жулиа образуются по той же самой формуле, что и множество Мандельброта. Множество Жулиа было изобретено французским математиком Гастоном Жулиа, по имени которого и было названо множество. Первый вопрос, возникающий после визуального знакомства с множествами Мандельброта и Жулиа это «если оба фрактала сгенерированы по одной формуле, почему они такие разные?» Сначала посмотрите на картинки множества Жулиа. Достаточно странно, но существуют разные типы множеств Жулиа. При рисовании фрактала с использованием различных начальных точек (чтобы начать процесс итераций), генерируются различные изображения. Это применимо только ко множеству Жулиа.

Хотя это нельзя увидеть на картинке, фрактал Мандельброта — это, на самом деле, множество фракталов Жулиа, соединенных вместе. Каждая точка (или координата) множества Мандельброта соответствует фракталу Жулиа.

Рассмотрим функцию f:C→C. ество Жюлиа определяется как граница множества точек z, стремящихся к бесконечности при итерировании f(z):

При c=i множество Жюлиа превращается в дендрит:

Алгоpитм постpоения множества мандельбpота

Два комплексных числа можно складывать и вычитать как обычные двучлены, приводя подобные слагаемые, содержащие мнимую единицу. Пусть z = x + ⅈ ⁢ y и w = u + ⅈ ⁢ v . Тогда z ± w = x ± u + ⅈ ⁢ y ± v .

Для комплексных чисел определяется также операция умножения. Два числа умножаются так же, как двучлены, только встретившиеся в полученном выражении квадраты мнимой единицы заменяются на − 1 : z ⁢ w = x + ⅈ ⁢ y ⁢ u + ⅈ ⁢ v = x ⁢ u + ⅈ ⁢ x ⁢ v + y ⁢ u + ⅈ 2 ⁢ y ⁢ v = x ⁢ u − y ⁢ v + ⅈ ⁢ x ⁢ v + y ⁢ u .

Чтобы определить деление комплексных чисел, преобразуем дробь z w , умножив её числитель и знаменатель на число w ¯ = u − ⅈ ⁢ v , отличающееся от знаменателя знаком мнимой части (такое число называется комплексно-сопряжённым): z w = z ⁢ w ¯ w ⁢ w ¯ = x + ⅈ ⁢ y ⁢ u − ⅈ ⁢ v u + ⅈ ⁢ v ⁢ u − ⅈ ⁢ v = x ⁢ u + y ⁢ v + ⅈ ⁢ y ⁢ u − x ⁢ v u 2 + v 2 . Конечно же знаменатель должен быть ненулевым.

Множество комплексных чисел, для которых определены операции арифметики, называют полем комплексных чисел. Оно заслужило отдельное обозначение ℂ .

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

Рассмотрим квадратный многочлен f ⁡ z = w + z 2 , где z w ∈ ℂ . Положим z 0 = 0 . Тогда с помощью многочлена можно построить рекуррентную последовательность комплексных чисел z k + 1 = f ⁡ z k . Будем называть эту последовательность орбитой нуля (термин «орбита» уже употреблялся в главе 15. «Десятичные дроби»). Нуля — потому что первый элемент последовательности ноль. Итак, вот первые несколько элементов орбиты: 0 w w + w 2 w + w 2 + 2 ⁢ w 3 + w 4 … .

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

Определение ограниченности орбиты

Перед нами встала задача определения ограниченности или неограниченности орбиты нуля для каждого заданного комплексного числа w . К сожалению, выписать общую формулу для элементов орбиты z k = f ⁡ f ⁡ f ⁡ … f ⁡ 0 … , где k значков f , не представляется возможным. Так что вряд ли аналитические методы помогут решить задачу. Для наших целей практически неограниченной можно считать орбиту, которая, рано или поздно, вырывается за пределы некоторого круга с центром в нуле достаточно большого радиуса R , скажем, равного 100 . Но это может произойти рано, поздно, или же не произойти никогда. Тем не менее, алгоритм, выясняющий ограниченность орбиты, должен быть в какой-то момент остановлен. Поэтому нам потребуется сформулировать ещё одно условие, при выполнении которого орбиту можно считать практически ограниченной.

Вспомним о том, что точное представление вещественного числа в компьютере невозможно, и что количество представимых чисел конечно, хоть и очень велико. Из-за этого конечным будет и количество комплексных чисел внутри некоторого круга. Любая орбита при вычислении на компьютере обязательно зациклится, поскольку её элементы принадлежат конечному множеству и вычисляются рекуррентно. Было бы разумно считать орбиту практически ограниченной, если она зациклится раньше, чем покинет большой круг. Определить момент зацикливания помогает метод Флойда, подробно изложенный нами в разделе «Метод Черепахи и Зайца». Напомним, что ключевым обстоятельством, на котором основан метод Флойда, является выполнение равенства z k = z 2 ⁢ k для некоторого k , то есть совпадение элементов «черепашьей» последовательности z k и «заячьей» z 2 ⁢ k . Как только равенство выполнится, можно утверждать, что Черепаха уже вступила в цикл.

Беда в том, что в самом худшем случае зацикливание может наступить не раньше, чем орбита (Черепаха) посетит по очереди все до единого комплексные числа, попавшие в круг, а их очень и очень много. Мы не будем дожидаться, когда наступит момент зацикливания. Вместо этого станем считать орбиту практически зациклившейся, если черепашья последовательность достаточно сблизится с заячьей, то есть выполнится условие z k − z 2 ⁢ k 1 R .

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

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

Теперь для каждого комплексного числа w можно определить, принадлежит ли оно множеству Мандельброта, или нет. Можно раскрасить точки множества в чёрный цвет, оставив все остальные белыми. Но изображение на рисунке 48.1. «Множество Мандельброта» цветное. Каков же смысл этой раскраски? Само множество Мандельброта изображено красным цветом. Внешность множества зелёная. Чем быстрее орбита нуля покинет круг радиуса R , тем светлее зелёная раскраска точки w . Внутри множества, вопреки традиции, мы также использовали различные степени интенсивности красного цвета, чтобы получить более выразительное изображение. Красный цвет тем светлее, чем быстрее обнаруживается ограниченность орбиты.

Таким образом, для каждого числа w можно вычислять цвет, которым оно будет закрашено на изображении, как число I из отрезка 0 1 . Это будет интенсивность красного (для точек из множества) или зелёного (для всех остальных) цветов на картинке. В любом случае найденное число должно зависеть от количества n элементов орбиты, найденных до момента обнаружения её ограниченности или неограниченности, и убывать с ростом этого количества. Чтобы различать эти случаи ограниченности или неограниченности, припишем знак этому числу: для ограниченных орбит пусть это будет минус. Цвет, красный или зелёный, выбирается в зависимости от знака.

Мы экспериментировали, подбирая зависимость интенсивности цвета от n , и остановились на I ⁡ n = ± 1 n 4 + 1 (прибавление единицы под знаком корня исключает деление на ноль при n = 0 , а деление на 4 осветляет картинку). Нетрудно понять, что самые большие значения n , и, следовательно, самые тёмные цвета обнаружатся вблизи границы множества Мандельброта, где орбита проводит особенно много времени, решая либо устремиться к бесконечности, либо остаться ограниченной. Рисунки 48.1 и 48.2 подтверждают эту мысль.

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

Рисунок 48.1 демонстрирует важное свойство множества Мандельброта — его симметричность относительно вещественной оси. Иными словами, при комплексном сопряжении множество переходит само в себя. Это легко доказать. Заметим, что ограниченность или неограниченность орбиты не изменится, если каждый её элемент подвергнуть комплексному сопряжению. Осталось доказать, что орбиты нуля для w и w ¯ симметричны друг другу при отражении относительно вещественной оси. Для w получаем орбиту O ⁡ w = 0 w w + w 2 w + w 2 + 2 ⁢ w 3 + w 4 … , а для w ¯ — O ⁡ w ¯ = 0 w ¯ w ¯ + w ¯ 2 w ¯ + w ¯ 2 + 2 ⁢ w ¯ 3 + w ¯ 4 … . Поскольку все элементы орбиты O ⁡ w являются многочленами от w с вещественными коэффициентами, остаётся доказать, что комплексное сопряжение можно выносить за знак таких многочленов: g ⁡ w ¯ = g ⁡ w ¯ . Последний факт вытекает из двух легко проверяемых свойств комплексного сопряжения: p ± q ¯ = p ¯ ± q ¯ и p ⋅ q ¯ = p ¯ ⋅ q ¯ для любых комплексных чисел p и q . Итак, O ⁡ w ¯ = O ⁡ w ¯ , что и требовалось доказать.

Грех не воспользоваться доказанным обстоятельством в тех случаях, когда изображаемый фрагмент комплексной плоскости содержит участок вещественной оси. Тогда для некоторых точек можно не находить цвет, вычисляя элементы орбиты, а просто скопировать его с комплексно-сопряжённой точки. Это, конечно, ускорит вычисления ценой небольшого усложнения алгоритма.

Алгоpитм постpоения множества мандельбpота

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

Если переформулировать эти выражения в виде итеративной последовательности значений координат комплексной плоскости и , т. е. заменив на , а на , мы получим:

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

Алгоритм построения множества таких точек достаточно прост: берется простейшее итерационное уравнение в комплексных числах с возведением некоторого стартового числа в квадрат и прибавлением константы. Но поскольку, это целое множество точек, каждый раз в ходе итераций по уравнению, константа изменяется в интервале [-2.0 + 2.0i; 2.0 + 2.0i] — и каждый раз проверяется не уходит ли точка из прямоугольной области 2 * 2: для чего проверяется, меньше ли модуль полученного значения чем 2 (если стартовое значение после некоторого количества итераций дает модуль больше 2, то значит точка с соответствующими координатами не принадлежит множеству Мандельброта и скорее всего траектория этой точки уйдет в бесконечность).

Собственно, наша задача проста — необходимо провести итерации по вот такому уравнению:

и отобразить некоторые точки.

В итоге, получается:

Как оно работает: создаем приложение DGui, после чего перегружаем, как обычно, функцию onPaint, подставляя в нее вызов drawMandelbrotSet(c, 0.005), где 0.005 — это приращение для каждого из циклов, кроме цикла с итерациями по самой формуле. Переменная isMandelbrotPoint обозначает принадлежность точки к множеству Мандельброта и установлена в начале в true, так как предполагается изначально, что точка принадлежит множеству, а значение этой переменной изменяется лишь в том случае, если в самом внутреннем цикле модуль комплексного числа превысит число 2 (т.е. в том случае, если точка выйдет в бесконечность).

Одним из не очевидных моментов может быть подключение std.complex, части стандартной библиотеки, которая содержит структуру complex и функцию abs (модуль комплексного числа). Дело в том, что стандартными средствами D, несмотря на нативную поддержку комплексных чисел, нельзя построить комплексное число, используя в качестве аргументов значения действительной и мнимой части, кроме того, эта библиотека содержит еще и уйму полезных предопределенных функций и перегруженных операторов (например, сложение и умножение).

Ну и в конце концов, после компиляции получаем вот такую безрадостную картинку, чем-то напоминающую филейную часть тела:

Алгоpитм постpоения множества мандельбpота

Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Слово фрактал образовано от латинского fractus и в переводе означает состоящий из фрагментов. Оно было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта `The Fractal Geometry of Nature’. В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему.

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

Одним из основных свойств фракталов является самоподобие. В самом простом случае небольшая часть фрактала содержит информацию о всем фрактале. Определение фрактала, данное Мандельбротом, звучит так: «Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому».

В качестве примера рассмотрим множество Мандельброта. Алгоритм его построения достаточно прост и основан на простом итеративном выражении: Z[i+1] = Z[i] * Z[i] + C, где Zi и C — комплексные переменные. Итерации выполняются для каждой стартовой точки с прямоугольной или квадратной области — подмножестве комплексной плоскости. Итерационный процесс продолжается до тех пор, пока Z[i] не выйдет за пределы окружности радиуса 2, центр которой лежит в точке (0,0), (это означает, что аттрактор динамической системы находится в бесконечности), или после достаточно большого числа итераций (например 200-500) Z[i] сойдется к какой-нибудь точке окружности. В зависимости от количества итераций, в течении которых Z[i] оставалась внутри окружности, можно установить цвет точки C (если Z[i] остается внутри окружности в течение достаточно большого количества итераций, итерационный процесс прекращается и эта точка растра окрашивается в черный цвет).

За основу мы взяли проект Mandelbrot-Set-in-Verilog, и адаптировали для нашей платы VE-XC6SLX9.

Основной модуль проекта представлен ниже:

  • vga — Основной модуль проекта. Генерирует VGA развертку, управляет параметрами отображения и собирает во едино остальные модули.
  • ram — модуль управления памятью.
  • mandelbrot — генератор множества Мандельброта

Управление отображением осуществляется с помощью кнопок Key1— сброс, Key2— приближение. А также перемещение изображения с помошью клавиатуры, как в нашем примере Первый проект для VE-XC6SLX9. Часть 3.

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

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

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

Расширенное определение Править

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

$ c=x+i \cdot y \, $ $ Z_0=0 \, $ $ \beginZ_1&=&Z_0^2+c \\ \ &=& x+iy\end \, $ $ \beginZ_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 \, $ $ Z_3=Z_2^2+c=. \, $

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

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

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

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

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

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

Добавление цвета Править

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

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

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

Илон Маск рекомендует:  Что такое код utf8_encode

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

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

Оптимизация Править

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


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

$ \rho = \sqrt <\left( x - <1 \over 4>\right)^2 + y^2> $ , $ \theta = \hbox_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 за одинаковое число итераций или наоборот принадлежит множеству Мандельброта, то любая точка внутри этой кривой будет обладать тем же свойством, и следовательно вся область внутри границы закрашивается одинаковым цветом.

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

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

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

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

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

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

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

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

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

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

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

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

Его определение и название обусловлено Adrien Дуади , в дань математике Бенуа Мандельброта . Комплект подключается к набору Джулии , и связанное с ними множество Жюлиа производит так же сложные фрактальные формы.

Множество Мандельброта изображение может быть создано путем выборки комплексных чисел и тестирования для каждой точки образца , является ли последовательность стремится к бесконечности (на практике — оставляет ли он некоторую предопределенную ограниченную окрестность 0 после заданного числа итераций). Лечение в реальных и мнимые части в качестве изображения координат на комплексной плоскости , пиксели затем может быть окрашены в соответствии с тем, как скоро последовательность пересекает произвольно выбранное пороговое значение, с помощью специального цвета (обычно черного цвета) , используемого для значений , для которых последовательности имеет не переступил порог после заданного числа итераций (это необходимо четко различать множество Мандельброта изображения от образа его дополнения). Если поддерживаются постоянным и начальное значение -denoted по -is переменного вместо этого, получается соответствующее множество Жюлиа для каждой точки в пространстве параметров от простой функции. с <\ Displaystyle с>е с ( 0 ) , е с ( е с ( 0 ) ) , . <\ Displaystyle F_ (0), F_ (F_ (0)), \ dotsc> с <\ Displaystyle с>| е с ( 0 ) | , | е с ( е с ( 0 ) ) | , . <\ Displaystyle | f_ <с>(0) |, | f_ <с>(f_ <с>(0)) |, \ dotsc> с <\ Displaystyle с>с <\ Displaystyle с>Z <\ Displaystyle г>Z 0 <\ Displaystyle z_ <0>> с

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

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

содержание

история

Множество Мандельброта имеет свое место в сложной динамике , поле первого расследованных французских математиков Пьер Фату и Гастон Жюлиа в начале 20 — го века. Этот фрактал впервые была определена и нарисовано в 1978 году Роберт У. Брукс и Питер Мателски в рамках изучения групп Клейна . С 1 марта 1980 года в IBM «s Thomas J. Watson Research Center в Йорктаун Хайтс , Нью — Йорк , Бенуа Мандельброт первым увидел визуализации множества.

Мандельброт изучил пространство параметров из квадратичных полиномов в статье, опубликованной в 1980 г. Математического исследования Мандельброта действительно начался с работой математиками Adrien Дуади и Джон Х. Хаббард , который установил многие из его основных свойств и назвали множество в честь Мандельброта для его влиятельной работы в фрактальной геометрии .

Математики Хайнц Отто Пейтген и Питер Рихтер стал хорошо известен для содействия набор с фотографиями, книгами, и на международном турне по выставке немецкого Гёте-Института .

Крышку статья августа 1985 Scientific American представила широкую аудиторию к алгоритму для вычисления множества Мандельброта. Крышка признаки изображения , расположенное на -0.909 -0.275 + и была создана Peitgen и др. Множество Мандельброта стало заметным в середине 1980-х годов , как компьютерные графики демо , когда персональные компьютеры стали достаточно мощными , чтобы построить и отобразить набор в высоком разрешении.

Работа Дуадь и Хаббард совпала с огромным ростом интереса к сложной динамике и абстрактной математике , а также изучение множества Мандельброта было краеугольным камнем этой области до сих пор. Исчерпывающий список всех , кто внес вклад в понимание этого набора с тех пор долго , но будет включать в себя Михаил Любич , Курт McMullen , Джон Милнор , Митсуайро Шишикур и Йокко .

Формальное определение

Множество Мандельброта представляет собой набор значений с в комплексной плоскости , для которых орбита 0 при итерации в квадратичной карте

остается ограниченным . То есть комплексное число с является частью множества Мандельброта , если при старте с г = 0 и применяя итерации повторно, абсолютное значение из г п остается ограниченным , однако большая п получает. Это также может быть представлено в виде

Например, давая C = 1 дает последовательность 0, 1, 2, 5, 26, . которая стремится к бесконечности . Поскольку эта последовательность не ограничена, 1 не является элементом множества Мандельброта. С другой стороны, с = -1 дает последовательность 0, -1, 0, -1, 0, . которая ограничена, и поэтому -1 принадлежит множеству Мандельброта.

Множество Мандельброта определяется семейством комплексных квадратичных полиномов M

где представляет собой комплексный параметр. Для каждого , учесть поведение последовательности с <\ Displaystyle с>с

полученная итерация старта в критической точке , которая либо уходит на бесконечность или остается в пределах диска некоторых конечного радиуса . Множество Мандельброта определяется как множество всех точек таким образом, что указанная последовательность никак не избежать до бесконечности. п с ( Z ) <\ Displaystyle Р- (г)> Z знак равно 0 <\ Displaystyle г = 0>с

Как объяснено ниже, это на самом деле можно упростить это определение, принимая . s знак равно 2

Математически, множество Мандельброта просто набор комплексных чисел. Данный комплекс номер с либо принадлежит М , либо нет. Изображение множества Мандельброта можно окрашивая все точки , которые принадлежат М черным, а все остальные точки белыми. Более красочные картинки , как правило , видны генерируются красящих точек , не в наборе , согласно которому член последовательности является первым членом с абсолютным значением , большим , чем определенное значение отсечки, как правило , 2. Список используемых цветов всегда предопределенный программа , используемая или созданный пользователем, следующий цвет в списке выбирается , когда число итераций возрастает. Смотрите раздел по компьютерным чертежам ниже для более подробной информации. с <\ Displaystyle с>| п с N ( 0 ) | <\ Displaystyle | Р- <с>^ <п>(0) |>

Множество Мандельброта также может быть определена как связности локуса семейства многочленов . То есть, это подмножество комплексной плоскости , состоящая из тех параметров , для которых Жюлиа из будет подключен . п с ( Z ) <\ Displaystyle Р- (г)> с <\ Displaystyle с>п с <\ Displaystyle Р- <с>>

Основные свойства

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

Другими словами, если абсолютное значение из когда — либо становится больше , чем 2, то последовательность будет уходить на бесконечность в короткий промежуток времени. п с N ( 0 ) <\ Displaystyle Р- ^ <п>(0)>

Пересечение из с действительной осью именно интервал [-2, 1/4]. Параметры вдоль этого интервала можно поставить в один-однозначном соответствии с интересами реальной логистической семьи , M

Z ↦ λ Z ( 1 — Z ) , λ ∈ [ 1 , 4 ] ,

На самом деле, это дает соответствие между всем пространством параметров логистической семьи и что множества Мандельброта.

Дуади и Хаббард показали , что множество Мандельброта подключен . На самом деле, они построили явный конформный изоморфизм между дополнением множества Мандельброта и дополнением замкнутого единичного диска . Мандельброт первоначально предположил , что множество Мандельброта отключен . Эта гипотеза была основана на компьютерных файлов , созданных с помощью программ, которые не могут обнаружить тонкие нити , связывающие различные части . После дальнейших экспериментов, он пересмотрел свою гипотезу, решив , что должно быть подключено. Там также существует топологическое доказательство связности , который был обнаружен в 2001 году Джереми Кан. M <\ Displaystyle M>M

Динамическая формула для uniformisation дополнения множества Мандельброта, возникающей из Дуади и Хаббарда доказательства связности , приводит к возникновению внешних лучам множества Мандельброта. Эти лучи могут быть использованы для изучения множества Мандельброта в комбинаторных терминах и образует костяк parapuzzle Yoccoz. M

Граница множества Мандельброта точно раздвоение локус квадратичной семьи; то есть, набор параметров , для которых динамика резко изменяется при малых изменениях он может быть выполнен в виде предельного набора последовательности плоских алгебраических кривых , то кривые Мандельброта , общего типа , известный как полиномиальные лемнискаты . Кривые Мандельброта определяются путем установки р = г , р п + 1 = р п 2 + г , а затем интерпретировать множество точек | р п ( г ) | = 2 в комплексной плоскости в виде кривой в реальном декартовой плоскости степени 2 п +1 в х и у . Эти алгебраические кривые появляются в образах множества Мандельброта , рассчитанном с использованием «алгоритма времени выхода» , упомянутый ниже. с <\ Displaystyle с>с ,

Другие свойства

Основные кардиоидных и период луковицы


После глядя на картину множества Мандельброта, один сразу же замечает большой кардиоида -образный область в центре. Эта основная кардиоида является областью параметров , для которых имеет притягивающую неподвижную точку . Он состоит из всех параметров вида с <\ Displaystyle с>п с <\ Displaystyle Р- <с>>

Слева от главного кардиоиды, прикрепленного к нему в точке , круговой-образной форме шарик виден. Эта лампа состоит из тех параметров , для которых имеет притягивающий цикл периода 2 . Этот набор параметров является актуальной круг, а именно , что радиус 1/4 вокруг -1. с знак равно — 3 / 4 <\ Displaystyle с = -3/4>с <\ Displaystyle с>п с <\ Displaystyle Р- <с>>

Есть бесконечно много других луковицы по касательной к основной кардиоиде: для каждого рационального числа , с р и д копервичным , есть такая лампа , которая является касательной в параметре п Q <\ Displaystyle <\ tfrac <р><д>>>

Эта лампа называется -bulb множества Мандельброта. Он состоит из параметров , которые имеют притягивающий цикл периода и комбинаторное число оборотов . Точнее, периодические компоненты Фаты , содержащие притягивающий цикл всего прикосновение в общей точке (обычно называют -fixed точки ). Если мы обозначаем эти компоненты в ориентацией против часовой стрелки, а затем отображает компонент к компоненту . п Q <\ Displaystyle <\ tfrac <р><д>>> Q <\ Displaystyle д>п Q <\ Displaystyle <\ tfrac <р><д>>> Q <\ Displaystyle д> α U 0 , . , U Q — 1 <\ Displaystyle u_ <0>, \ точками, U_ > п с <\ Displaystyle Р- <с>> U J <\ Displaystyle U_ > U J + п ( модификация ⁡ Q ) <\ Displaystyle U_ д)>>

Изменение поведения , происходящее в известене как бифуркации : притягивающая неподвижная точка «сталкивается» с периодом отталкивающей д — циклом. Как мы пройти через бифуркационного параметра в -bulb, притягивающая неподвижная точка превращается в отталкивающей неподвижной точке ( -fixed точка), а период д -циклом становится привлечение. с п Q <\ Displaystyle с _ <\ гидроразрыва <р><д>>> п Q <\ Displaystyle <\ tfrac <р><д>>> α

гиперболические компоненты

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

Высказано предположение , что они являются только внутренние области . Эта проблема, известная как плотность гиперболичности , может быть наиболее важной нерешенной проблемой в области сложной динамики. Гипотетические не-гиперболические компоненты множества Мандельброта часто называют как «квир» или компонентов призрака. Для вещественных квадратичных полиномов, этот вопрос был решен положительно в 1990 — х годах независимо друг от друга Любича и Graczyk и Swiatek. (Заметим , что гиперболические компоненты пересекающиеся числовой оси точно соответствуют периодическим окна в диаграмме Фейгенбаума . Таким образом , этот результат состоит в том , что такие окна существуют возле каждого параметра на диаграмме) . M

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

Каждый из гиперболических компонентов имеет центр , который является точкой с таким образом, что внутренний домен Фата для имеет супер-притягивающий цикл — то есть, что притяжение бесконечно (см изображения здесь ). Это означает , что цикл содержит критическую точку 0, так что 0 итеративен обратно к себе после нескольких итераций. Таким образом , мы имеем , что п для некоторого п . Если мы назовем этот многочлен (позволяя это зависит от с вместо г ), имеем и что степень есть . Таким образом , мы можем построить центры гиперболических компонентов путем последовательного решения уравнений . Количество новых центров , возникающих на каждом этапе дается Слоана OEIS : A000740 . п с ( Z ) <\ Displaystyle Р- (г)> п с <\ Displaystyle Р- <с>> ( 0 ) знак равно 0 <\ Displaystyle (0) = 0>Q N ( с ) <\ Displaystyle Q ^ <п>(с)> Q N + 1 ( с ) знак равно Q N ( с ) 2 + с <\ Displaystyle Q ^ <п + 1>(с) = Q ^ <п>(с) ^ <2>+ с> Q N ( с ) <\ Displaystyle Q ^ <п>(с)> 2 N — 1 <\ Displaystyle 2 ^ > Q N ( с ) знак равно 0 , N знак равно 1 , 2 , 3 , , , , <\ Displaystyle Q ^ <п>(с) = 0, п = 1,2,3, . >

Локальное подключение

Высказано предположение , что множество Мандельброта локально связным . Эта известная гипотеза известна как MLC (для Мандельброта локально подключено ). К работе Adrien Дуади и Джон Х. Хаббардом , эта гипотеза может привести к простой абстрактной модели «защемление диска» множества Мандельброта. В частности, это будет означать важные гиперболичности гипотезу , упомянутую выше.

d установила локальную связность множества Мандельброта на все конечно перенормируемые параметры; то есть, грубо говоря , те , которые содержатся только в конечном числе маленьких копий Мандельброта. С тех пор, локальное подключение было доказано во многих других точках , но полная гипотеза остается открытым. M

Самоподобие

Множество Мандельброта самоподобный при увеличении в окрестностях точек Мисюревича . Он также высказал предположение, что самоподобная вокруг обобщенных точек Фейгенбаум (например, -1,401155 или -0,1528 + 1,0397 я ), в том смысле , сходящихся к пределу набора.

Множество Мандельброта в целом не является строго самоподобным но квази-самоподобным как маленькие немногими разные версии самого по себе могут быть найдены при сколь угодно малых масштабах.

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

Дальнейшие результаты

Хаусдорфова от границы множества Мандельброта равно 2 , как определено в результате Митсуайро Шишикура . Не известно , имеет ли граница множества Мандельброта положительной планарной меру Лебега .

В Э.Блюм-Смейл модели реального расчета , множество Мандельброта не вычислимое, а его дополнение вычислимо перечислит . Тем не менее, многие простые объекты ( например , график экспоненциации) также не вычислимая в модели ПБС. В настоящее время неизвестно , является ли множество Мандельброта вычислит в моделях реальных вычислений на основе вычислимого анализа , которые соответствуют более близко к интуитивному понятию «построение набора с помощью компьютера». Хертлинг показал , что множество Мандельброта вычислит в этой модели , если Гиперболичность гипотеза верна.

Отношения с множествами Жюлиа

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

Этот принцип используется практически во всех глубоких результатов на множестве Мандельброта. Например, Shishikura доказал , что для плотного множества параметров в границах множества Мандельброта, множество Жюлиа имеет хаусдорфовую размерность два, а затем передает эту информацию в плоскость параметров. Точно так же, Yoccoz первым доказал локальную связность множеств Жюлиа, прежде чем создать его для множества Мандельброта в соответствующих параметрах. Adrien Дуадьте фразы этого принципа , как:

Плуг в динамической плоскости, и урожай в пространстве параметров.

Геометрия

Для каждого рационального числа , где р и д является взаимно простыми , гиперболическим компонент периода д разветвляется от основного кардиоида. Часть множества Мандельброта , подключенное к основным кардиоидному в этой точке бифуркации называется р / д -limb . Компьютерные эксперименты показывают , что диаметр конечности стремится к нулю , как . Лучшая текущая оценка известная является Yoccoz-неравенство , в котором говорится , что размер стремится к нулю , как . п Q <\ Displaystyle <\ tfrac <р><д>>> 1 Q 2 <\ Displaystyle <\ tfrac <1><д ^ <2>>>> 1 Q <\ Displaystyle <\ tfrac <1><д>>>

Период- д конечности будет иметь Q — 1 «усики» на верхней части его конечности. Таким образом , мы можем определить период данной колбы путем подсчета этих антенн.

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

В попытке продемонстрировать , что толщина р / д -limb равна нуль, Дэвид Болл провел компьютерный эксперимент в 1991 году, где он вычисляется количество итераций , требуемых для ряда расходиться при г = ( будучи его местоположением) , По мере того как серия не расходятся при точном значении Z = число итераций возрастает при необходимости небольшого е. Оказывается, умножив значение ε с числом итераций дает приближение П , который становится лучше при меньшем е. Так , например, при е = 0,0000001 число итераций равно 31415928 и продукт 3,1415928. — 3 4 + я ε <\ Displaystyle - <\ tfrac <3><4>> + I \ эпсилон> — 3 4 <\ Displaystyle - <\ tfrac <3><4>>> — 3 4 <\ Displaystyle - <\ tfrac <3><4>>>

Фибоначчи последовательность в множестве Мандельброта

Последовательность Фибоначчи последовательность такова , что каждое число в последовательности является суммой двух предыдущих чисел и могут быть найдены в Мандельброта. Начиная с периодом одного кардиоидой и период второй колбой, последовательность периодов луковицы , где каждые последующие лампами являются самой крупной луковицей прикреплен к кардиоидному между двумя предыдущими луковицами следует последовательности Фибоначчей. Например, период три шарика является вторым по величине лампы после периода два лампы, срок пять колбы является самым крупной между периодом два и периодом три луковицей, и периодом восемь колбой является самым крупной между периодом три и периодом пяти луковицами , Они соответствуют номерам последовательности Фибоначчи , начиная с 1, 2, 3, 5, 8, 13, 21, и так далее.

Картинная галерея последовательности масштабирования

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

Увеличение последнего изображения относительно первого составляет около 10 10 к 1. , относящемуся к обычному монитору, он представляет собой сечение множество Мандельброта с диаметром 4 миллиона километров. Его граница будет показывать астрономическое число различных фрактальных структур.

Начните. Множество Мандельброта с непрерывно окрашенной средой.

Зазор между «головой» и «телом», также называемым «коньком долиной»

Дважды спиралей на левой стороне, «коньков» справа

«Конек» с ног на голову

Конек «тело» состоит из 25 «спиц» , состоящих из двух групп 12 «спиц» каждые и один «говорили» подключение к главному кардиоиды. Эти две группы могут быть отнесены на какой — то метаморфозы в двух «пальцев» на «верх» из множества Мандельброта; Таким образом, количество «спиц» увеличивается от одного «конька» к другому на 2; «центр» является так называемой точкой Мисюревича . Между «верхней части тела» и «хвост» искаженной уменьшенная копия множества Мандельброта называется спутник может быть распознан.

Центральная конечная точка «конек хвоста» также является точка Мисюревича .

Часть «хвост» — есть только один путь , состоящий из тонких структур , которые ведут через весь «хвост». Этот зигзаг путь проходит «концентраторы» из крупных объектов с 25 «спицами» на внутреннюю и внешнюю границе «хвост»; Таким образом , множество Мандельброта является односвязным множеством, что означает , что нет островов и нет петли дороги вокруг отверстия.

Спутник. Два «Seahorse хвостов» являются началом серии концентрических коронок со спутником в центре. Открыть это место в интерактивном зрителе.

Каждая из этих коронок состоит из подобных «Seahorse хвостов»; их число возрастает с увеличением степени числа 2, типичного явления в среде спутников. Единственный путь к центру спирали проходит спутник из канавки кардиоидной в верхней части «антенны» на «голове».

«Антенна» спутника. Несколько спутники второго порядка могут быть признаны.

«Конек долина» спутника. Все структуры от начала масштабирования снова.

Дважды спиралей и «коньки» — в отличии от 2 — го образа с самого начала, они имеют приложение , состоящее из структур , как «Seahorse хвосты»; это демонстрирует типичное увязывание п + 1 различных структур в среде спутников порядка п , здесь для простейшего случая п = 1.

Дважды спиралей со спутниками второго порядка — по аналогии с «коньков», в виде двойной спирали, может быть интерпретирована как метаморфоза «антенны»

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

Часть «двойной крючок»


Фрагмент одного острова

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

Обобщения

наборы Multibrot

Multibrot множество ограниченных множеств найденных в комплексной плоскости для членов общего унитарного одномерного полиномиального семейства рекурсий

Для целого д, эти множества связанность локусы для множеств Julia , построенных из одной и той же формулы. Также был изучен полный кубический связанность локус; здесь один считает рекурсию двухпараметрической , чья две критических точек являются сложными квадратными корнями параметра к . Параметр находится в кубической связности локуса , если обе критические точки являются стабильными. Для общих семейств голоморфных функций , то граница множества Мандельброта обобщается на бифуркационном локус , который является естественным объектом для изучения , даже когда связанность локус не является полезным. Z ↦ Z 3 + 3 К Z + с <\ Displaystyle г \ mapsto г ^ <3>+ 3kz + с>

Множество Multibrot получается путем изменения значения показателя г . Статье есть видео , которое показывает развитие от г = 0 до 7, и в этот момент есть 6 т ( д — 1) лопасти по всему периметру. Подобное развитие с отрицательными показателями результатов в (1 — г ) расщелины на внутренней стороне кольца.

Илон Маск рекомендует:  outline-style в CSS

Более высокие размеры

Там нет идеального расширения множества Мандельброта в 3D. Это происходит потому , что нет 3D аналога комплексных чисел для того , чтобы перебирать дальше. Тем не менее, есть расширение комплексных чисел в 4 -х измерениях, называемых кватернионов , что создает идеальное расширение множества Мандельброта и Жюлиа в 4 -х измерениях. Затем они могут быть либо разрезают в поперечном направлении, или проецируются в 3D — структуры.

Другое, неаналитический, отображение

Особый интерес представляет треугольный фрактал, связанность локус антиголоморфным семьи

Треуголка (также иногда называют набор Mandelbar [скорее всего , из — за разницы между множеством треуголка и Мандельброта Черта над правой Z]) был сталкиваются Милнором в своем исследовании параметризованных срезах реальных кубических полиномов . Он не локально связно. Это свойство наследуется связности локуса вещественных кубических многочленов.

Другой неаналитическое обобщение является Горящий корабль фрактал , который получается итерацией следующее:

Компьютерные рисунки

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

Бегство алгоритм времени

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

В й и у места расположения каждой точки использует в качестве исходных значений в повторяющемся или итерации расчета (подробно описан ниже). Результат каждой итерации используется в качестве исходных значений для следующего. Значения проверяются при каждой итерации , чтобы увидеть , были ли они достигли критического «побег» состояние, или «катапультирование». Если это условие будет достигнуто, то расчет прекращается, пиксель рисуется, а следующие х , у рассматривается точка. Для некоторых исходных значений, побег происходит быстро, только после небольшого числа итераций. Для начальных значений очень близких, но не в наборе, это может занять сотни или тысячи итераций , чтобы избежать. Для значений в пределах множества Мандельброта, побег никогда не произойдет. Программист или пользователь должен выбрать , сколько итераций, или «глубина», они хотят исследовать. Чем выше максимальное число итераций, тем больше деталей и тонкость появляются в конечном изображении, но больше времени потребуется для расчета фрактальных изображений.

Условия эвакуации могут быть простыми или сложными. Потому что ни комплексное число с реальной или мнимой части больше , чем 2 может быть частью набора, общее спасение не избежать , когда либо коэффициент превышает 2. Более вычислительно сложный метод , который обнаруживает побеги рано, чтобы вычислить расстояние от начала координат , используя теорема Пифагора , то есть, чтобы определить абсолютное значение , или модуль , комплексного числа. Если это значение превышает 2, или что то же самое, когда сумма квадратов действительных и мнимых частей превышает 4, точка достигла побега. Более интенсивные варианты вычислительно рендеринга включают Buddhabrot методы, который находит убегающую точку и участки их итерационную координату.

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

Для визуализации такого изображения, область комплексной плоскости мы рассматриваем подразделяют на определенное количество пикселей . Для того, чтобы окрасить любой такой пиксель, пусть середина этого пикселя. Теперь мы итерация критической точки-при , проверяя на каждый шаг , имеет ли точка орбиты модуля больше , чем 2. Если это так, мы знаем , что не принадлежат к множеству Мандельброта, и покрасят наш пиксель в соответствии с количеством итерации используются , чтобы узнать. В противном случае, мы продолжаем итерацию до фиксированного числа шагов, после чего мы решили , что наш параметр «вероятно» в множество Мандельброта, или по крайней мере очень близко к нему, и цвет пикселя черный. с <\ Displaystyle с>п с <\ Displaystyle Р- <с>> с

В псевдокоде , этот алгоритм будет выглядеть следующим образом . Алгоритм не использует комплексные числа и вручную имитирует комплексно-номер операции , используя два действительных числа, для тех , кто не имеют сложный тип данных . Программа может быть упрощена , если язык программирования включает в себя операцию комплексно-данных типа.

и так, как это можно видеть в псевдокоде при вычислении х и у :

Для того, чтобы получить красочные образы набора, присвоение цвета каждому значению числа выполненных итераций может быть сделано с помощью одного из множества функций (линейная, экспоненциальная и т.д.). Одним из практических способов, без замедления расчетов являются использование числа выполненных итераций как запись к справочной цветовой палитре таблице инициализируется при запуске. Если таблица цветов имеет, например, 500 записей, то выбор цвета п кратна 500, где п есть число итераций.

Гистограмма раскраски

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

Во- первых, создать массив размера п . Для каждого пикселя, который взял я итерации, найти I — го элемента и увеличивают его. Это создает гистограмму при вычислении изображения. Затем, когда закончена, выполняют второй «рендеринг» проходить над каждым пикселем, используя заполненную гистограмму. Если вы имели непрерывную цветовую палитру в диапазоне от 0 до 1, вы могли бы найти нормализованный цвет каждого пикселя следующим образом , используя переменные из выше.

Этот способ может быть объединен с методом гладкого красящим ниже для более эстетически изображений.

LiveInternetLiveInternet

Рубрики

  • Вышивка крестом (257)
  • Немецкая вышивка крестом (55)
  • Французская вышивка крестом (51)
  • Вышивка крестом Новый Год (22)
  • Гномы и пр. (21)
  • Вышивка журналы (20)
  • Acufactum (15)
  • Органайзер (12)
  • Примитивы (7)
  • Veronique Enginger вышивка крестом (6)
  • Растения (181)
  • Сады (32)
  • Комнатные растения (26)
  • Мини- сады (24)
  • Огород (11)
  • Цветы (121)
  • Поделки (48)

  • Иллюстрации (44)
  • Наука (32)
  • Физика (14)
  • Математика (11)
  • Камни (5)
  • Гномы, ниссе и т.п. (31)
  • Книги (25)
  • Путешествия (24)
  • Советы (20)
  • Мифология Археология (19)
  • Восток (7)
  • Древняя Греция (1)
  • Мифы востока (7)
  • Разное (11)
  • Вязание (8)
  • Цветы балкон Zenya_Z (7)
  • Юмор (4)
  • Вышивка крестиком Zenya_Z (3)

Поиск по дневнику

Подписка по e-mail

Интересы

Постоянные читатели

Сообщества

Статистика

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

Среда, 20 Мая 2015 г. 23:41 + в цитатник

Мно́жество Мандельбро́та — это множество таких точек c на комплексной плоскости, для которых итерационная последовательность при является ограниченной. То есть, это множество таких c, для которых существует такое действительное R, что неравенство |z n| -9 . Точная координата центра масс(расположенного на оси абсцисс) тоже неизвестна и оценивается как -0,286 768 420 48 ± 3.35×10 -9 [1] .

Содержание

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

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

Если переформулировать эти выражения в виде итеративной последовательности значений координат комплексной плоскости и , т. е. заменив на , а на , мы получим:

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

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

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

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

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

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

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

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

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

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

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

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

Порядок определения, попадает ли точка z 0 внутрь множества (традиционно закрашиваемого чёрным цветом) или нет (закрашивается цветом, зависящим от скорости движения к бесконечности) следующий: на каждой итерации для z n = x n + y n ·i вычисляется значение модуля , которое затем сравнивается с «границей бесконечности» (обычно берётся значение, равное 2). Здесь важно обратить внимание, что уже на данном этапе можно ввести определённую оптимизацию вычислений, если проверять не 2″ src=»https://upload.wikimedia.org/math/f/2/6/f26493adca50ee26f98fcf29db5befaa.png» /> , а 4″ src=»https://upload.wikimedia.org/math/9/0/0/9000e582014deb177c6f1934993583ba.png» /> , что значительно снизит время расчётов. Строго математически, изображения множеств Мандельброта и Жюлиа должны быть чёрно-белыми. Точка либо попадает внутрь множества, либо нет. Несмотря на это, с помощью компьютера мы можем построить и цветные изображения. Самым распространённым способом является раскрашивание точек снаружи множества в цвет, соответствующий количеству итераций, за которое точка уходит в «бесконечность» или, с точки зрения программы, на определённое расстояние от нуля.

Таким образом, если |z n| 2 ≤ 4 при любом числе итераций (на практике — при всех вычисленных итерациях), то цвет точки чёрный, в противном случае он зависит от последнего значенияn, при котором |z n| 2 ≤ 4. Значение n, фактически, обозначает скорость движения z n в бесконечность, и может быть просто индексом в таблице цветов, или использоваться как параметр в более сложном алгоритме.

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

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

Оптимизация


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

Таким образом, для точки необходимо вычислить

Если то точка попадает внутрь множества и закрашивается чёрным цветом, а итеративные вычисления можно пропустить.

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

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

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

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

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

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

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

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

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

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

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

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

Mitsuhiro Shishikura доказал, что размерность Хаусдорфа границы множества Мандельброта равна 2. Но остается неизвестным ответ на вопрос, имеет ли граница множества Мандельброта положительную меру Лебега на плоскости. Douady и Hubbard доказали, что множество Мандельброта является связным, хотя в это и трудно поверить, глядя на хитрые системы мостов, соединяющие различные его части. Однако неизвестно, является ли оно локально связным. Это известная гипотеза в комплексной динамике получила название MLC (Mandelbrot Localy Connected), многие математики прилагают усилия к её доказательству. Jean-Christophe Yoccoz доказал, что гипотеза верна во всех точках с конечной ренормализацией, затем многие другие математики доказывали справедливость гипотезы во многих отдельных точках множества Мандельброта, но общая гипотеза остается недоказанной.

Число итераций [чего?] очень близко к логарифму электрического потенциала, который возникает, если зарядить множество Мандельброта. Точнее, предел совпадает с этим потенциалом.

Осваиваем F#: построение красочного множества Мандельброта с навигацией и интеграция с C#

Два комплексных числа можно складывать и вычитать как обычные двучлены, приводя подобные слагаемые, содержащие мнимую единицу. Пусть z = x + ⅈ ⁢ y и w = u + ⅈ ⁢ v . Тогда z ± w = x ± u + ⅈ ⁢ y ± v .

Для комплексных чисел определяется также операция умножения. Два числа умножаются так же, как двучлены, только встретившиеся в полученном выражении квадраты мнимой единицы заменяются на − 1 : z ⁢ w = x + ⅈ ⁢ y ⁢ u + ⅈ ⁢ v = x ⁢ u + ⅈ ⁢ x ⁢ v + y ⁢ u + ⅈ 2 ⁢ y ⁢ v = x ⁢ u − y ⁢ v + ⅈ ⁢ x ⁢ v + y ⁢ u .

Чтобы определить деление комплексных чисел, преобразуем дробь z w , умножив её числитель и знаменатель на число w ¯ = u − ⅈ ⁢ v , отличающееся от знаменателя знаком мнимой части (такое число называется комплексно-сопряжённым): z w = z ⁢ w ¯ w ⁢ w ¯ = x + ⅈ ⁢ y ⁢ u − ⅈ ⁢ v u + ⅈ ⁢ v ⁢ u − ⅈ ⁢ v = x ⁢ u + y ⁢ v + ⅈ ⁢ y ⁢ u − x ⁢ v u 2 + v 2 . Конечно же знаменатель должен быть ненулевым.

Множество комплексных чисел, для которых определены операции арифметики, называют полем комплексных чисел. Оно заслужило отдельное обозначение ℂ .

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

Рассмотрим квадратный многочлен f ⁡ z = w + z 2 , где z w ∈ ℂ . Положим z 0 = 0 . Тогда с помощью многочлена можно построить рекуррентную последовательность комплексных чисел z k + 1 = f ⁡ z k . Будем называть эту последовательность орбитой нуля (термин «орбита» уже употреблялся в главе 15. «Десятичные дроби»). Нуля — потому что первый элемент последовательности ноль. Итак, вот первые несколько элементов орбиты: 0 w w + w 2 w + w 2 + 2 ⁢ w 3 + w 4 … .

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

Определение ограниченности орбиты

Перед нами встала задача определения ограниченности или неограниченности орбиты нуля для каждого заданного комплексного числа w . К сожалению, выписать общую формулу для элементов орбиты z k = f ⁡ f ⁡ f ⁡ … f ⁡ 0 … , где k значков f , не представляется возможным. Так что вряд ли аналитические методы помогут решить задачу. Для наших целей практически неограниченной можно считать орбиту, которая, рано или поздно, вырывается за пределы некоторого круга с центром в нуле достаточно большого радиуса R , скажем, равного 100 . Но это может произойти рано, поздно, или же не произойти никогда. Тем не менее, алгоритм, выясняющий ограниченность орбиты, должен быть в какой-то момент остановлен. Поэтому нам потребуется сформулировать ещё одно условие, при выполнении которого орбиту можно считать практически ограниченной.

Вспомним о том, что точное представление вещественного числа в компьютере невозможно, и что количество представимых чисел конечно, хоть и очень велико. Из-за этого конечным будет и количество комплексных чисел внутри некоторого круга. Любая орбита при вычислении на компьютере обязательно зациклится, поскольку её элементы принадлежат конечному множеству и вычисляются рекуррентно. Было бы разумно считать орбиту практически ограниченной, если она зациклится раньше, чем покинет большой круг. Определить момент зацикливания помогает метод Флойда, подробно изложенный нами в разделе «Метод Черепахи и Зайца». Напомним, что ключевым обстоятельством, на котором основан метод Флойда, является выполнение равенства z k = z 2 ⁢ k для некоторого k , то есть совпадение элементов «черепашьей» последовательности z k и «заячьей» z 2 ⁢ k . Как только равенство выполнится, можно утверждать, что Черепаха уже вступила в цикл.

Беда в том, что в самом худшем случае зацикливание может наступить не раньше, чем орбита (Черепаха) посетит по очереди все до единого комплексные числа, попавшие в круг, а их очень и очень много. Мы не будем дожидаться, когда наступит момент зацикливания. Вместо этого станем считать орбиту практически зациклившейся, если черепашья последовательность достаточно сблизится с заячьей, то есть выполнится условие z k − z 2 ⁢ k 1 R .

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

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

Теперь для каждого комплексного числа w можно определить, принадлежит ли оно множеству Мандельброта, или нет. Можно раскрасить точки множества в чёрный цвет, оставив все остальные белыми. Но изображение на рисунке 48.1. «Множество Мандельброта» цветное. Каков же смысл этой раскраски? Само множество Мандельброта изображено красным цветом. Внешность множества зелёная. Чем быстрее орбита нуля покинет круг радиуса R , тем светлее зелёная раскраска точки w . Внутри множества, вопреки традиции, мы также использовали различные степени интенсивности красного цвета, чтобы получить более выразительное изображение. Красный цвет тем светлее, чем быстрее обнаруживается ограниченность орбиты.

Таким образом, для каждого числа w можно вычислять цвет, которым оно будет закрашено на изображении, как число I из отрезка 0 1 . Это будет интенсивность красного (для точек из множества) или зелёного (для всех остальных) цветов на картинке. В любом случае найденное число должно зависеть от количества n элементов орбиты, найденных до момента обнаружения её ограниченности или неограниченности, и убывать с ростом этого количества. Чтобы различать эти случаи ограниченности или неограниченности, припишем знак этому числу: для ограниченных орбит пусть это будет минус. Цвет, красный или зелёный, выбирается в зависимости от знака.

Мы экспериментировали, подбирая зависимость интенсивности цвета от n , и остановились на I ⁡ n = ± 1 n 4 + 1 (прибавление единицы под знаком корня исключает деление на ноль при n = 0 , а деление на 4 осветляет картинку). Нетрудно понять, что самые большие значения n , и, следовательно, самые тёмные цвета обнаружатся вблизи границы множества Мандельброта, где орбита проводит особенно много времени, решая либо устремиться к бесконечности, либо остаться ограниченной. Рисунки 48.1 и 48.2 подтверждают эту мысль.

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

Рисунок 48.1 демонстрирует важное свойство множества Мандельброта — его симметричность относительно вещественной оси. Иными словами, при комплексном сопряжении множество переходит само в себя. Это легко доказать. Заметим, что ограниченность или неограниченность орбиты не изменится, если каждый её элемент подвергнуть комплексному сопряжению. Осталось доказать, что орбиты нуля для w и w ¯ симметричны друг другу при отражении относительно вещественной оси. Для w получаем орбиту O ⁡ w = 0 w w + w 2 w + w 2 + 2 ⁢ w 3 + w 4 … , а для w ¯ — O ⁡ w ¯ = 0 w ¯ w ¯ + w ¯ 2 w ¯ + w ¯ 2 + 2 ⁢ w ¯ 3 + w ¯ 4 … . Поскольку все элементы орбиты O ⁡ w являются многочленами от w с вещественными коэффициентами, остаётся доказать, что комплексное сопряжение можно выносить за знак таких многочленов: g ⁡ w ¯ = g ⁡ w ¯ . Последний факт вытекает из двух легко проверяемых свойств комплексного сопряжения: p ± q ¯ = p ¯ ± q ¯ и p ⋅ q ¯ = p ¯ ⋅ q ¯ для любых комплексных чисел p и q . Итак, O ⁡ w ¯ = O ⁡ w ¯ , что и требовалось доказать.

Грех не воспользоваться доказанным обстоятельством в тех случаях, когда изображаемый фрагмент комплексной плоскости содержит участок вещественной оси. Тогда для некоторых точек можно не находить цвет, вычисляя элементы орбиты, а просто скопировать его с комплексно-сопряжённой точки. Это, конечно, ускорит вычисления ценой небольшого усложнения алгоритма.

Вступительное слово

Данная статья расчитана на тех, кто уже хотя бы немного знаком с языками С# и F#. В любом случае, я старался сделать код как можно более читабельным и давать описание каждому фрагменту. Ознакомиться с языком F# можно в следующих статьях:

  • Введение в F#, или полезное о бесполезном
  • F#: Hello, World!
  • MSDN: Первое знакомство с F#

На Хабре уже много писали общих слов о языке F# — его истории, происхождении, особенностях. Не хочется повторяться, поэтому предлагаю сразу перейти к делу. Итак, план действий следующий:

  1. Построение множества Мандельброта,
  2. Визуализация результатов,
  3. Интеграция с C# и не только с ним.

Итак, поехали.

Как определяется множество Мандельброта?

Рассмотрим последовательность чисел, генерируемых следующим уравнением:
Cn+1 = Cn 2 + c
Если такая последовательность не выходит за рамки двух комплексных чисел C1(1, 1i) и C2(-1, -1i), то комплексное число c принадлежит множеству Мандельброта. Значит, множество Мандельброта — это множество всех таких чисел c, при котором рассмотренная выше последовательность остается в рамках C1 и C2.

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

Для работы с комплексными числами в F# существует библиотека Microsoft.FSharp.Math, которая, в свою очередь, доступна в пакете FsharpPowerPack (по ссылке также можно найти руководство по установке и другую полезную информацию о данном паке). Добавляем данную библиотеку в наш проект и указываем ее:

Теперь мы можем в программе манипулировать комплексными числами. Определим минимальную и максимальную границы:

Перейдем непосредственно к функции. Реализуем функцию проверки на принадлежность к множеству следующим образом:

Рекурсивная функция isInMandelbrotSet работает, пока проверяемое число не вышло за границы cMax и cMin, а глубина рекурсии не превысила числа итераций. По завершении, функция возвращает число совершённых шагов рекурсии (это пригодится нам в дальнейшем, когда мы будем «раскрашивать» наше множество).

Визуализация результатов


Само множество мы уже построили, осталось лишь его вывести на экран. Но тут и начинается самое интересное.

Илон Маск рекомендует:  Что такое код hw_api &#62;srcanchors

Так как комплексные числа состоят из двух частей, то мы можем создать их отображение на двумерной плоскости. Множество Мандельброта существует между C1(1, 1i) и C2(-1, -1i), поэтому нужная нам система координат будет иметь центр в точке (0, 0), оси абсцисс и ординат будут ограничены значениями -1.0 и 1.0.

Поэтому нам необходимо осуществить перенос координат точек с комплексной плоскости на ту, которая используется при построении изображения.

Сделаем это следующим образом:

Данная функция будет возвращать для каждой точки «привычной» плоскости соответствующее ей комплексное число. Величины mx и my мы будем использовать в дальнейшем для реализации навигации по нашему изображению.

Теперь мы можем легко отрисовать все наше множество на привычной плоскости. Для этого нам необходимо «пройтись» по всем координатам плоскости и проверить принадлежность каждой точки (точнее, соответствующего ей комплексного числа) к множеству Мандельброта. Если точка принадлежит множеству, сделаем её черной, в противном случае — раскрасим ее в другой цвет. Для этого, сделаем специальную функцию «раскраски»:

Функция будет принимать число итераций, которое мы получили из функции isInMandelbrotSet, и определять RGB-значение цвета. Числовые коэффициенты можно поставить любые, но чтобы добиться плавности перехода цветов, желательно задавать их с маленькой разницей. Также, здесь нам потребуется библиотека System.Drawing:

При помощи данной библиотеки, мы создадим новое bitmap-изображение и будем добавлять к нему точки определнного цвета. Так, наша функция отрисовки будет иметь следующий вид:

Здесь мы используем компонент System.Windows.Forms:

Осталось только запустить нашу программу и порадоваться результатом. Сделать это можно следующим образом:

Мы указываем начальные параметры: масштаб, смещение по X и Y, а также число итераций. Чем число итераций больше, тем детальнее будет наше изображение (и, соответственно, дольше будет создаваться). Примерно таким должен получиться результат работы:

Итак, полный листинг нашей программы:

Промежуточные итоги

Как вы видите, на создание «цветного» множества Мандельброта нам потребовалось чуть больше 40 строк и не так и много времени. Но всецело насладиться всей прелестью фрактальных изображений мы пока не можем (точнее можем, но это совсем неудобно — менять перед каждой компиляцией масштаб изображения). Для преодоления этой проблемы, необходимо добавить элементы интерфейса — клавиши навигации и увеличения/уменьшения изображения, желательно изменяя при этом детализацию.

Конечно, можно создать все элементы интерфейса внутри F# так же, как мы создавали саму форму, используя библиотеку System.Windows.Forms. Но с другой стороны, было бы куда интереснее (и, пожалуй, логичнее) сделать это в рамках полноценного Windows Forms приложения! Хорошо, тогда этим сейчас и займемся.

Интеграция с C# и не только с ним

После сборки F#-приложения, на выходе мы получаем библиотеку, содержащую весь необходимый нам функционал. Для удобного доступа к необходимым функциям этой библиотеки, объявим namespace в коде F#. Делается это следующим образом: в самом начале кода добавим

Кроме того, нам больше не нужна форма, а также код, ее запускающий. Поэтому теперь функция, которую мы будем вызывать извне, будет выглядеть так:

Вызываемая функция createImage возвращает созданное bitmap-изображение, содержащее множество Мандельброта.

Используем F#-библиотеку в Windows Forms

На самом деле, все очень просто: необходимо лишь добавить готовую библиотеку в новый проект (наример, Windows Forms или любой другой). Создав проект, в MS Visual Studio сделать это можно командой Add Reference окна Solution Explorer, выбрав необходимую библиотеку. Так как ранее мы обозначили namespace в библиотеке ( module Fractal ), то в новом проекте нам доступны все функции этой библиотеки. Теперь вызвать функцию, которая сгенерирует готовое изображение, можно следующим образом:

Полученное bitmap-изображение можно уже использовать любым способом — например, добавить в качестве background’а к элементу PictureBox.

Добавление элементов навигации

Как вы видите, мы можем «запросить» генерацию изображения с различными параметрами: масштабом, количеством итераций, смещением относительно X и Y. А значит, добавить навигацию не составит труда. В качестве контейнера для нашего изображения возьмем PictureBox, навигацию осуществим при помощи 6-ти кнопок: приблизить/отдалить, сдвинуть вверх/вниз, вправо/влево.

Для удобства создадим отдельный класс FractalClass, который будет хранить состояние текущего фрактала: масштаб, смещения от центра, уровень приближения. Основной метод класса будет запрашивать изображение множества с текущими параметрами.

Остальные методы класса будут изменять состояние фрактала и обращаться к методу Draw(). Так, например, может выглядеть метод приближения:

Осталось только добавить в обработку нажатия клавиш навигации вызов соответсвующих методов класса FractalClass. Результат будет примерно следующим:

Возможность передавать в функцию нужное количество итераций позволяет детализировать фрактал при приближении. Поэтому с каждым шагом изображение становится всё интереснее и интереснее:

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

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

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

Пред тем, как переходить к визуализации, дадим определение множества Мандельброта.

Рассмотрим, вначале, произвольное комплексное число z = x + iy. Этому числу соответствует точка на комплексной плоскости с координатами (x, y). В дальнейшем будем отождествлять комплексные числа с соответствующими им точками комплексной плоскости. Комплексную последовательность

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

Простейшая визуализация множества Мандельброта заключается в следующем. Точкам некоторой прямоугольной области комплексной плоскости естественным образом ставятся в соответствие пиксели холста для рисования. Пиксели, соответствующие точкам плоскости, принадлежащим множеству Мандельброта, закрашиваются чёрным цветом, а остальные — белым. Кстати, известно, что точки множества Мандельброта более или менее «помещаются» в квадрат с центром в точке (-1/2, 0) со стороной 2.

Для построения такой визуализации, очевидно, требуется алгоритм, устанавливающий принадлежность или непринадлежность той или иной точки комплексной плоскости множеству Мандельброта. Проблема заключается в том, что универсального алгоритма, «работающего» для любой точки, не существует. Однако известно, что последовательность Мандельброта, модуль некоторого члена которой превышает 2, стремится по модулю к бесконечности, т. е. не ограничена. Это означает, что начальный член этой последовательности не принадлежит множеству Мандельброта.

Это утверждение позволяет нам использовать алгоритм определения «условной» принадлежности точки данному множеству. Заключается он в вычислении фиксированного, заранее выбранного числа первых членов последовательности Мандельброта для проверяемой точки. Если модуль ни одного из вычисленных членов не превосходит числа 2, то испытуемая точка считается принадлежащей множеству Мандельброта. В противном случае точка считается этому множеству не принадлежащей.

Авторы упомянутой ранее книги предлагают ограничиться нахождением первых 255 членов последовательности (включая саму проверяемую точку). Если все 255 чисел оказываются по модулю не превосходящими 2, то соответствующие им пиксели окрашиваются в чёрный цвет. Если же начальный член (т. е. сама проверяемая точка) превосходит по модулю 2, то соответствующий ей пиксель закрашивается в белый цвет.

Если же установлена непринадлежность точки z множеству Мандельброта по причине того, что для некоторого минимального k такого, что 1 ≤ k ≤ 254, выполняется неравенство |zk| > 2, то в этом случае логично окрашивать соответствующий точке пиксель также в белый цвет. Однако авторы книги предлагают иной подход: закрашивать пиксель оттенком серого цвета. При этом цвет закраски должен быть тем ближе к белому, чем меньше k и тем ближе к чёрному, чем больше k. Более конкретно: интенсивность серого цвета предлагается вычислять как разность 255 − k.

В данном случае имеется в виду интенсивность, которая совпадает со значениями каждой из трёх компонент при сохранении цветов в RGB-формате. Напомним, что каждому оттенку серого соответствует именно совпадение компонент.

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

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

Структура программы. Директивы препроцессора

Программа будет состоять из главного файла main.c, а также трёх файлов, образующих библиотеку pgraph. К main.c будет подключён заголовочный файл библиотеки pgraph.h с помощью директивы #include . Вот как выглядят директивы препроцессора, с которых начинается файл main.c:

Как видим, кроме praph.h, к нашему файлу подключается также заголовочный файл стандартной библиотеки для работы с комплексными числами complex.h (о поддержке языком C99 комплексных чисел (в рамках использования компилятора MinGW64) можно почитать здесь).

Далее с помощью директивы #define определяются 5 макросов, имеющих следующий смысл:

  • W — ширина изображения,
  • H — высота изображения,
  • X0 — абсцисса пикселя в исходной системе координат, в который помещено начало новой системы координат,
  • Y0 — ордината пикселя в исходной системе координат, в который помещено начало новой системы координат,
  • L — длина отрезка, имеющего в новой системе координат единичную длину, выраженная в пикселях.

Поясним, что под исходной системой координат понимается та, которая используется в библиотеке pgraph и позволяет обращаться к пикселям изображения по координатам. А новая система координат — это та, которая вводится нами на комплексной плоскости для построения в ней изображения множества Мандельброта.


Легко заметить, что пиксель, имеющий координаты (i, j) в исходной системе координат будет соответствовать точке с координатами

((i — X0) / L, (j — Y0) / L)

в новой системе координат.

Как мы видим (см. код), наше изображение будет квадратным, отображающим область комплексной плоскости размером примерно 2,1×2,1, а начало координат равноудалено от «нижней» и «верхней» границ квадрата и примерно в 2 раза ближе к «правой» его границе, чем к «левой». Выбор параметров, приводящий к описанному положению вещей, обусловлен упоминавшейся ранее особенностью «локализации» точек множества Мандельброта.

В файле main.c будут содержаться определения двух функций: get_gray_color() и main() . Рассмотрим каждую из них.

Вычисление интенсивности серого цвета пикселя: функция get_gray_color()

Ниже приведён код функции get_gray_color() .

Функция принимает в качестве параметра точку комплексной плоскости и возвращает «цвет», которым должен быть раскрашен пиксель, соответствующий данной точке. Слово «цвет» помещено в кавычки, т. к., если быть точным, то пиксель раскрашивается в один из оттенков серого цвета (включая белый и чёрный цвета), и данная функция возвращает, на самом деле, интенсивность серого цвета в диапазоне от 0 до 255. Поясним, что тип uchar определён в файле pgraph.h и эквивалентен типу unsigned char .

Алгоритм нахождения интенсивности уже был описан ранее. Текущее значение интенсивности содержится в переменной gray (стр. 4). В ходе цикла for (см. стр. 4-9) gray пробегает значения интенсивности от 255 до 1, также в ходе цикла вычисляются значения последовательности Мандельброта для исходной точки (см. стр. 8). Для каждого значения интенсивности проверяем, превосходит ли текущая точка последовательности Мандельброта число 2. Если превосходит, то прерываем цикл и возвращаем текущую интенсивность (стр. 6-7).

Если же модуль ни одного из вычисленных первых 255 членов последовательности не достигает и не превышает 2, то считаем, что начальная точка принадлежит множеству и возвращаем нулевую интенсивность (стр. 10), соответствующую чёрному цвету.

Построение изображения множества Мандельброта: функция main()

Главная функция нашей программы, непосредственно создающая изображение множества Мандельброта, выглядит так:

Создаём изображение (стр. 3). Перебираем в двух циклах for (см. стр. 4, 5) все его пиксели. Для каждого пикселя вычисляем координаты точки на комплексной плоскости, которой он соответствует (стр. 7, 8). Формируем из координат точки комплексное число (стр. 9). Передаём это число в функцию get_gray_color() и получаем «цвет» текущего пикселя (стр. 10). Если «цвет» пикселя отличен от белого, то закрашиваем пиксель данным цветом (стр. 11-12) (изначально холст для рисования белый, поэтому нет необходимости в окрашивании его пикселей в белый цвет).

Записываем изображение в файл «out.bmp» (стр. 14) и удаляем изображение (стр. 15).

Раскрашиваем изображение множества Мандельброта

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

Действовать будем следующим образом. Передавая комплексное число в функцию get_gray_color() , будем теперь рассматривать интенсивность серого цвета, возвращаемую функцией, как номер цвета из некоторого предопределённого списка цветов. Именно этим цветом и будем раскрашивать пиксель, соответствующий данному комплексному числу.

Очевидно, что изменять функцию get_gray_color() не требуется. А вот функцию main() нужно переделать. Вот её новая, «цветная» версия:

Список предопределённых цветов, о котором шла речь выше, формируется в виде массива colors в строках 3-11. Принцип формирования достаточно простой: выбираются по 8 оттенков красного и зелёного цветов, а также 4 оттенка синего. Далее эти оттенки смешиваются, в результате чего получаются 256 цветов, коими и заполняется массив colors посредством трёх вложенных циклов (см. стр. 7-11). Интенсивности каждого из трёх цветов примерно равномерно распределяются по спектру интенсивностей данного цвета (см. стр. 3-5).

Теперь значение, возвращаемое функцией get_gray_color() , интерпретируем как индекс элемента массива colors , содержащего цвет, которым нужно раскрасить текущий пиксель (см. стр. 19-21). Заметим, что значениям 0 и 1, возвращаемым функцией, как и в предыдущем («чёрно-белом») случае, соответствуют чёрный и белый цвета пикселя соответственно.

В результате выполнения новой версии программы получаем следующее изображение:

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

Ясно, что существует огромное количество способов раскраски множества Мандельброта. Для получения некоторых из них можно, например, изменить порядок следования выражений внутри фигурных скобок, отвечающих за значения полей элементов массива colors (см. стр. 11). Существуют, очевидно, 6 вариантов расположения выражений:

Заменяя 11-ю строку функции main() одной из приведённых выше строк (за исключением 1-й), получаем ещё 5 вариантов раскраски. Изображения множества Мандельброта, раскрашенного всеми 6-ю способами, соответствующими 6-ю приведённым выше строкам, изображены ниже.

6 изображений множества Мандельброта (щёлкните для увеличения)

Мне, пожалуй, больше всего понравилось 2-е изображение. Давайте, кстати, чтобы рассмотреть его более тщательно, увеличим разрешение примерно в 2 раза. Для этого изменим значения некоторых макросов:

В качестве 11-й строки (см. код функции main() ) будем использовать следующую:

После запуска и компиляции программы получаем изображение, которое можно посмотреть по ссылке (откроется в новом окне, исходный файл преобразован в формат JPG, размер JPG-файла составляет 475 КБ). Это же изображение можно получить, щёлкнув по приведённой ниже картинке, представляющей уменьшенную его версию.

Ещё одно изображение множества Мандельброта (щёлкните для увеличения)

И последнее. Из алгоритма раскраски множества Мандельброта следует, что раскраске подвергаются лишь пиксели, соответствующие точкам комплексной плоскости, удалённым от начала координат не более, чем на 2, т. е. лежащими внутри круга радиуса 2 с центром в начале координат или на его границе. Давайте рассмотрим этот круг полностью. Для этого изменим значения макросов, определённых в файле main.c следующим образом:

После запуска и компиляции программы получаем изображение, уменьшенная версия которого приведена ниже (оригинал изображения размером 237 КБ, переведённый в формат JPG, можно получить, щёлкнув по картинке или по ссылке, которая откроется в новом окне).

Множество Мандельброта с высоты птичьего полёта (щёлкните для увеличения)

Заключение

Итак, мы создали программы, позволяющие строить «чёрно-белые» и «цветные» изображения множества Мандельброта. Отметим, что цель написать код, максимально эффективный в плане быстродействия, не ставилась. Программы, описанные в статье, и так выполняются за достаточно короткий промежуток времени: за доли секунды.

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

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

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

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

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

Если переформулировать эти выражения в виде итеративной последовательности значений координат комплексной плоскости и , т. е. заменив на , а на , мы получим:

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

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

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

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

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

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

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

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

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

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

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

$step = ($x_min + $x_max)/$img_w;

$step = ($x_max — $x_min)/$img_w;

$step = (-$x_min + $x_max)/$img_w; >

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

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

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

Порядок определения, попадает ли точка внутрь множества (традиционно закрашиваемого чёрным цветом) или нет (закрашивается цветом, зависящим от скорости движения к бесконечности) следующий: на каждой итерации для вычисляется значение модуля , которое затем сравнивается с «границей бесконечности» (обычно берётся значение, равное 2). Здесь важно обратить внимание, что уже на данном этапе можно ввести определённую оптимизацию вычислений, если сравнивать не 2″ w />, а 4\!» w />, что значительно снизит время расчётов.

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

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

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

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

Оптимизация

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

Таким образом, для точки необходимо вычислить

Если то точка попадает внутрь множества и закрашивается чёрным цветом, а итеративные вычисления можно пропустить.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL