Фрактал

множество Мандельброта — классический образец фрактала

Фракта́л (лат. fractus — дроблёный) — термин, введённый Бенуа Мандельбротом в 1975 году для обозначения нерегулярных самоподобных множеств. В его работах использованы результаты других учёных, работавших в той же области (Пуанкаре, Жюлиа, Кантор, Хаусдорф).

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

Еще один вариант определения: Фрактал - самоподобное множество нецелой размерности. Самоподобное множество - множество, представимое в виде объединения одинаковых непересекающихся подмножеств подобных исходному множеству.

Основные свойства фракталов:

• Они имеют тонкую структуру, т. е. содержат произвольно малые масштабы.
• Они слишком нерегулярны, чтобы быть описанными на традиционном геометрическом языке.
• Они имеют некоторую форму самоподобия, допуская приближённую.(1)
• Они имеют дробную размерность Хаусдорфа — Безиковича (HB). (Для самоподобных множеств, типа канторового множества, HB-размерность совпадает с размерностью подобия.)

История

Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «Фрактальная геометрия природы». Фрактальная геометрия - это один из разделов теории хаоса.

Области возникновения и применения фракталов

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

Классификации фракталов

В основном фракталы делят на геометрические, алгебраические и стохастические. Однако существуют и другие классификации:

• Рукотворные и природные. К рукотворным относятся те фракталы, которые были придуманы учёными, они при любом масштабе обладают фрактальными свойствами. На природные фракталы накладывается ограничение на область существования — то есть максимальный и минимальный размер, при которых у объекта наблюдаются фрактальные свойства.
• Детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).

Геометрические фракталы

Кривая Коха

История фракталов началась с геометрических фракталов, которые исследовались математиками в XIX веке. Фракталы этого класса — самые наглядные, потому что в них сразу видна самоподобность.

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

Примерами таких кривых служат:

• кривая дракона;
• кривая Коха;
• кривая Леви;
• кривая Минковского;
• кривая Пеано.

К геометрическим фракталам также относят фракталы, получаемые похожими процедурами, например:

• множество Кантора;
• треугольник Серпиньского;
• коврик Серпиньского;
• кладбище Серпиньского;
• губка Менгера;
• дерево Пифагора.

Алгебраические фракталы

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

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

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

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

Алгоритм построения достаточно прост и основан на итеративном выражении: $$z_{i+1} = F(z_i),$$ где \(F(z)\) — какая-либо функция комплексной переменной.

Для всех точек прямоугольной или квадратной области на комплексной плоскости вычисляем достаточно большое количество раз \(z_{i+1} = F(z_i)\), каждый раз находя абсолютное значение \(z\). При этом значения функции для разных точек комплексной плоскости могут иметь разное поведение:

• С течением времени \(|z|\) стремится к бесконечности;
• \(|z|\) стремится к 0;
• \(|z|\) принимает несколько фиксированных значений и не выходит за их пределы;
• Поведение \(|z|\) хаотично, без каких-либо тенденций.

Одним из самых распространённых способов раскрашивания точек будет сравнение \(|z|\) с заранее выбранным числом, которое считается «бесконечным», т. е. цвет точки равен номеру итерации, на которой \(|z|\) достиг «бесконечности», или чёрному в противном случае.

Фрактальная форма подвида цветной капусты (Brassica cauliflora)

Также можно изменить вид фрактала, если контроль значения z вести другим образом, например:

• Действительная часть \(z\) меньше определённого числа;
• Мнимая часть \(z\) меньше определённого числа;
• И мнимая и действительная части z меньше какого-либо числа;
• Другие способы.

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

Примеры алгебраических фракталов:

• множество Мандельброта;
• множество Жюлиа;
• бассейны Ньютона;
• биоморфы.

Стохастические фракталы

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

Плазма

Плазма

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

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

Рандомизированный(стохастический) фрактал

Рандомизированный фрактал на основе множества Жюлиа

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

Размерность фрактала

В евклидовой геометрии есть понятие размерности: размерность отрезка — единица, размерность круга — два, шара — три (или: прямая - 1, плоскость - 2, ...). Например, если мы будем измерять длину отрезка, то, например, метровых отрезков в нём будет N, полуметровых 2N, дециметровых — 10N и так далее. В данном случае наблюдается прямая пропорциональная зависимость. В случае измерения площади мы уже получим следующие значения: 4N, 100N, то есть здесь зависимость уже квадратичная. Объём трёхмерных фигур пропорционален кубу их линейных размеров.

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

Самым удивительным оказывается то, что и многие природные объекты обладают как бы дробной размерностью, хотя, строго говоря, для природных объектов такую размерность вычислить невозможно. Правильнее сказать, что в определённых диапазонах наблюдения природные объекты, возникшие в результате долгой диффузии и абсорбции, похожи на фрактальные множества. Например, размерность побережья лежит между 1,01 и 1,6, а кровеносной системы человека — между 3,4 и 3,6.

Применение фракталов

Генерация изображений природных объектов

Фрактальное дерево

Геометрические фракталы применяются для получения изображений деревьев, кустов, береговых линий и т. д. Алгебраические и стохастические — при построении ландшафтов, поверхности морей, карт раскраски, моделей биологических объектов и др.

Механика жидкостей

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

• динамика и турбулентность сложных потоков;
• моделирование пламени;
• изучение пористых материалов, в том числе в нефтехимии.

Биология

• Моделирование популяций;
• биосенсорные взаимодействия;
• процессы внутри организма, например, биение сердца.

Литература

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

• неразветвляющееся бесконечное дерево, тождественные самим себе с любой итерации ("У попа была собака...", "Притча о философе, которому снится, что он бабочка, которой снится, что она философ, которому снится...", "Ложно утверждение, что истинно утверждение, что ложно утверждение...")
• неразветвляющиеся бесконечные тексты с вариациями ("У Пегги был веселый гусь...") и тексты с наращениями ("Дом, который построил Джек")

В структурных фракталах схема текста потенциально фрактальна

• венок сонетов (15 стихотворений), венок венков сонетов (211 стихотворений), венок венков венков сонетов (2455 стихотворений)
• "рассказы в рассказе" ("Книга тысячи и одной ночи", Я.Потоцкий "Рукопись, найденная в Сарагоссе")
• предисловия, скрывающие авторство (У.Эко "Имя розы")
• Т.Стоппард "Розенкранц и Гильдернштейн мертвы" (сцена с представлением перед королем)

В семантических и нарративных фракталах автор рассказывает о бесконечном подобии части целому

• Х.Л.Борхес "В кругу развалин"
• Х.Кортасар "Желтый цветок"
• Ж.Перек "Кунсткамера"

Фрактальные антенны

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

Сжатие изображений

Ещё одно фрактальное дерево

Существуют алгоритмы для сжатия изображения с помощью фракталов. Они основаны на теореме Банаха о сжимающих преобразованиях (также известной как Collage Theorem) и являются результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли.

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

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), т. е. определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

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

Несмотря на то, что группой Барнсли было создано программное обеспечение, реализующее эти алгоритмы (например, библиотеки фрактального сжатия используются в Microsoft Encarta), осталась проблема скорости сжатия. Достаточно эффективное решение не найдено до сих пор, а сам Майкл Барнсли продолжает упорно работать в выбранном направлении.

Децентрализованные сети

Система назначения IP адресов в сети Netsukuku использует принцип фрактального сжатия информации для компактного сохранения информации об узлах сети. Каждый узел сети Netsukuku хранит всего 4 Кб информации о состоянии соседних узлов, при этом любой новый узел подключается к общей сети без необходимости в центральном регулировании раздачи IP адресов, что, например, характерно для сети Интернет. Таким образом, принцип фрактального сжатия информации гарантирует полностью децентрализованную, а следовательно, максимально устойчивую работу всей сети.

Литература

1. Мандельброт Б. Фрактальная геометрия природы. — М.: «Институт компьютерных исследований», 2002.
2. Пайтген Х.-О., Рихтер П. Х. Красота фракталов. — М.: «Мир», 1993.
3. Федер Е. Фракталы. — М: «Мир», 1991.
4. Фоменко А. Т. Наглядная геометрия и топология. — М.: изд-во МГУ, 1993.
5. Фракталы в физике. Труды 6-го международного симпозиума по фракталам в физике, 1985. — М.: «Мир», 1988.
6. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. — Ижевск: «РХД», 2001.

См. также

• Квазифрактал
• Мультифрактал
• wikibooks: ru: Размер и размерность
• Алгоритм фрактального сжатия
• Бесконечная вложенность материи

Ссылки

Программы для генерации фрактальных изображений

• Ultra Fractal — пожалуй, самая мощная программа, предназначенная для создания и анимации изображений по фрактальному алгоритму;
• Fractal Explorer — одна из лучших на сегодняшний день программ для создания изображений фракталов;
• XaoS — многоплатформенный генератор фракталов, позволяет приближать и удалять картинку в реальном времени;
• Fractint — очень мощная многоплатформенная программа, развитие которой, к сожалению, давно остановилось;
• Chaoscope — программа трёхмерной визуализации странных аттракторов;
• Apophysis — программа для создания fractal flames. Fractal flames является расширением IFS фракталов;
• RPS/Fract — несложный бесплатный генератор фракталов для платформы Pocket PC (PDA);
• P.Fract — несложный бесплатный генератор фракталов для платформы Palm (PDA);
• EyeFract
• Mfract
• Gnofract 4D
• IFS Illusions — Искусственное искусство программа и галереи

Сайты о фракталах

• Геометрические фракталы
• Фрактальные множества Очень подробная и качественная статья, начиная с комплексных чисел (Санкт-Петербургский государственный университет: ПМ-ПУ)
• Fractal World — сайт, на котором представлена широкая подборка видов фракталов с текстами программ для их построения;
• Архивохранилище Фрактал опубликовало на USENET
• Фракталы и теория хаоса
• Поверь алгебру гармонией Руководство к программе FractalExplorer на русском
• Введение во фракталы
• Доступно о фракталах
• Фракталы в НГУ: описания, форум, программа IFS Builder 3d
• Фракталы от OCo
• Фракталы и знание
• Всё о фракталах
• Красивая жизнь комплексных чисел
• Fractals of aramin (eng)
• Электронная библиотека по нелинейной динамике - книги о фракталах
• Программка, чтобы попробовать фракталы руками
• Фракталы, мультифракталы и не только
• Каталог сайтов о фракталах
• Фракталы в литературе: в поисках утраченного оригинала

Первоисточник этой статьи был признан «избранной статьёй» в русском разделе Википедии

eo:Fraktalo hu:Fraktál ia:Fractal ka:ფრაქტალი lt:Fraktalas ur:Fractal