Фрактал

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

Содержание

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм построения достаточно прост и основан на итеративном выражении:

zi + 1 = F(zi),

где F(z) — какая-либо функция комплексной переменной.

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

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

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

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

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

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

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

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

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

Плазма

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

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

Рандомизированный фрактал

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

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

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

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

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

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

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

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

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

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

Биология

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

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

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

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

С помощью фракталов можно сжимать большие растровые изображения с существенным коэфциентом сжатия. Это утверждение следует из теоремы Банаха о сжимающих преобразованиях (также известной как 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.

См. также

Ссылки

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

  • Ultra Fractal - пожалуй, самая мощная программа, предназначенная для создания и анимации изображений по фрактальному алгоритму;
  • Fractal Explorer — одна из лучших на сегодняшний день программ для создания изображений фракталов;
  • XaoS — многоплатформенный генератор фракталов, позволяет приближать и удалять картинку в реальном времени;
  • Fracint — очень мощная многоплатформенная программа, но, к сожалению, развитие которой давно остановилось;
  • Chaoscope — программа трёхмерной визуализации странных аттракторов;
  • Apophysis - программа для создания fractal flames. Fractal flames является расширением IFS фракталов;
  • EyeFract
  • Mfract
  • Gnofract 4D

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


Эта статья входит в число избранных.
Она была признана участниками проекта
одной из лучших статей русского раздела Википедии.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home