Фрактал
 Материал из Википедии — свободной энциклопедии
множество Мандельброта — классический образец фрактала
Фрактал (лат. fractus — дробленый) — это бесконечно самоподобная геометрическая фигура, каждый фрагмент которой повторяется при уменьшении масштаба. Масштабная инвариантность, наблюдаемая во фракталах, может быть либо точной, либо приближённой.
Термин «фрактал» введён Бенуа Мандельбротом в 1975 году. В его работах использованы результаты других учёных, работавших в той же области (Пуанкаре, Жюлиа, Кантор, Хаусдорф).
Ещё один вариант определения: Фрактал — самоподобное множество нецелой размерности. Самоподобное множество — множество, представимое в виде объединения одинаковых непересекающихся подмножеств подобных исходному множеству.
Основные свойства фрактала:
Он имеет тонкую структуру, то есть содержит произвольно малые масштабы. Он слишком нерегулярен, чтобы быть описанными на традиционном геометрическом языке.
Он имеет некоторую форму самоподобия (по крайней мере приближённую или стохастическую).
Он имеет дробную «фрактальную» размерность, называемую также размерностью Минковского, которая больше, чем его топологическая размерность (несмотря на то, что это условие не выполняется в случае кривых Пеано). Он имеет простое и рекурсивное определение.
История Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «Фрактальная геометрия природы». Фрактальная геометрия — это один из разделов теории хаоса.
Области возникновения и применения фракталов Фрактальные множества часто возникают в качестве аттракторов или бассейнов притяжений динамических систем даже в самых, казалось бы, простейших ситуациях (см. Множество Жюлиа). В компьютерной графике это используется при создании изображений сложных, похожих на природные, объектов: например, облаков, снега, мусорных куч, береговых линий и др.
Классификации фракталов
В основном фракталы делят на геометрические, алгебраические и стохастические. Однако существуют и другие классификации:
Рукотворные и природные. К рукотворным относятся те фракталы, которые были придуманы учёными, они при любом масштабе обладают фрактальными свойствами. На природные фракталы накладывается ограничение на область существования — то есть максимальный и минимальный размер, при которых у объекта наблюдаются фрактальные свойства.
Детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).
Геометрические фракталы
Кривая Коха История фракталов началась с геометрических фракталов, которые исследовались математиками в XIX веке. Фракталы этого класса — самые наглядные, потому что в них сразу видна самоподобность.
В двухмерном случае такие фракталы можно получить, задав некоторую ломаную, называемую генератором. За один шаг алгоритма каждый из отрезков, составляющих ломаную, заменяется на ломаную-генератор, в соответствующем масштабе. В результате бесконечного повторения этой процедуры (а точнее, при переходе к пределу) получается фрактальная кривая. При видимой сложности полученной кривой, её общий вид задаётся только формой генератора.
Примерами таких кривых служат:
кривая дракона
кривая Коха 
кривая Леви 
кривая Минковского 
кривая Пеано
К геометрическим фракталам также относят фракталы, получаемые похожими процедурами, например: 
множество Кантора 
треугольник Серпинского 
ковер Серпинского
кладбище Серпинского;
губка Менгера;
дерево Пифагора.
Алгебраические фракталы
 Множество Жюлиа́
Для построения алгебраических фракталов используются итерации нелинейных отображений, задаваемых простыми алгебраическими формулами.
Наиболее изучен двухмерный случай. Нелинейные динамические системы могут обладать несколькими устойчивыми состояниями. Каждое устойчивое состояние (аттрактор) обладает некоторой областью начальных состояний, при которых система обязательно в него перейдёт. Таким образом, фазовое пространство разбивается на области притяжения аттракторов.
Если фазовым является двухмерное пространство, то, окрашивая области притяжения различными цветами, можно получить цветовой фазовый портрет этой системы (итерационного процесса). Меняя алгоритм выбора цвета, можно получить сложные фрактальные картины с причудливыми многоцветными узорами. Неожиданностью для математиков стала возможность с помощью примитивных алгоритмов порождать очень сложные нетривиальные структуры.
Алгоритм построения достаточно прост и основан на итеративном выражении:
zi + 1 = F(zi),
где F(z) — какая-либо функция комплексной переменной.
Для всех точек прямоугольной или квадратной области на комплексной плоскости вычисляем достаточно большое количество раз zi + 1 = F(zi), каждый раз находя абсолютное значение z. При этом значения функции для разных точек комплексной плоскости могут иметь разное поведение:
С течением времени | z | стремится к бесконечности;
| z | стремится к 0;
| z | принимает несколько фиксированных значений и не выходит за их пределы;
Поведение | z | хаотично, без каких-либо тенденций.
Одним из самых распространённых способов раскрашивания точек будет сравнение | z | с заранее выбранным числом, которое считается «бесконечным», т. е. цвет точки равен номеру итерации, на которой | z | достиг «бесконечности», или чёрному в противном случае.
Фрактальная форма подвида цветной капусты (Brassica cauliflora) Также можно изменить вид фрактала, если контроль значения z вести другим образом, например:
Действительная часть z меньше определённого числа;
Мнимая часть z меньше определённого числа;
И мнимая и действительная части z меньше какого-либо числа;
Другие способы.
И, наконец, ещё один интересный эффект — изменение палитры. После того, как изображение построено, можно циклически изменять цвета закрашенных областей, и тогда и без того удивительное изображение «оживёт» на экране.
Примеры алгебраических фракталов:
множество Мандельброта;
множество Жюлиа;
бассейны Ньютона;
биоморфы.
Стохастические фракталы
Кривая Коха, как бы ни была похожа на границу берега, не может выступать в качестве её модели из-за того, что она всюду одинакова, самоподобна, слишком «правильна». Все природные объекты создаются по капризу природы, в этом процессе всегда есть случайность. Фракталы, при построении которых в итеративной системе случайным образом изменяются какие-либо параметры, называются стохастическими. К этому классу фракталов относится и фрактальная монотипия, или стохатипия. Термин «стохастичность» происходит от греческого слова, обозначающего «предположение».
Плазма
 Плазма
Для построения плазмы необходимо использовать шаблон черно-белого изображения. Рекурсивный алгоритм для построения следующий
присвоить значение оттенка для 4х углов прямоугольника.
высчитать средние значения оттенков для середин сторон и центра используя среднее арифметическое.
случайно изменить центральный оттенок. Величина изменения должна зависеть от размеров прямоугольника.
разделить прямоугольник на 4 равные части, в углах которых будут полученные средние значения.
Пример тогда верхний левый прямоугольник будет иметь значения
рекурсивно вызываем функцию для 4х маленьких прямоугольников.
Если мы теперь скажем, что оттенок точки — это высота над уровнем моря, то вместо плазмы получим горный массив. Именно на этом принципе моделируются горы в большинстве программ. С помощью алгоритма, похожего на плазму, строится карта высот, к ней применяются различные фильтры, накладывается текстура и т. д.
Рандомизированный (стохастический) фрактал
 Рандомизированный фрактал на основе множества Жюлиа
Рандомизованный фрактал строится по обычному алгоритму, за исключением того, что при вычислении на каждой итерации добавляются случайные величины.
Размерность фрактала
В евклидовой геометрии есть понятие размерности: размерность отрезка — единица, размерность круга — два, шара — три (или: прямая — 1, плоскость — 2, …). Например, если мы будем измерять длину отрезка, то, например, метровых отрезков в нём будет N, полуметровых 2N, дециметровых — 10N и так далее. В данном случае наблюдается прямая пропорциональная зависимость. В случае измерения площади мы уже получим следующие значения: 4N, 100N, то есть здесь зависимость уже квадратичная. Объём трёхмерных фигур пропорционален кубу их линейных размеров.
Если попытаться применить эти правила к фрактальным объектам, возникает парадоксальная ситуация — их размерность окажется дробным числом. Так как фрактал состоит из бесконечного числа повторяющихся элементов, невозможно точно измерить его длину. Это означает, что чем более точным инструментом мы будем его измерять, тем большей окажется его длина. В то время как гладкая евклидова линия заполняет в точности одномерное пространство, фрактальная линия выходит за пределы одномерного пространства, вторгаясь в двумерное. Таким образом, фрактальная размерность кривой Коха или «колбасы» Минковского будет находиться между 1 и 2.
Размерность фрактала можно вычислить, пользуясь размерностью Хаусдорфа-Безиковича, определение которой исходит из простого факта. Если мы приблизим отрезок так, что его длина увеличится в 2 раза, его размер увеличится в 2 раза. Если мы приблизим квадрат таким же образом (так, чтобы его линейные размеры выросли в 2 раза), его размер увеличится в 4 раза. При аналогичном приближении куба, его размер вырастет в 8 раз.
Тогда для вычисления размерности Хаусдорфа-Безиковича можно воспользоваться следующей формулой: размерность = log(s) / log(z), где s — изменение размера, z — изменение приближения
Для отрезка размерность будет равна log2 / log2 = 1, для квадрата: log4 / log2 = 2, для куба: log8 / log2 = 3.
Теперь, если вычислить размерность Хаусдорфа-Безиковича для снежинки Коха, она и вправду окажется дробной. Снежинка Коха строится путём последовательного разбиения отрезка на 4 новых, причём каждый из них будет в 3 раза меньше исходного. Получается, что приблизив какую-либо часть фигуры так, что длина отрезка увеличится в 3 раза, размер фигуры вырастет в 4 раза. Подставив эти числа в формулу, получим: log4 / log3 = 1.261.
Самым удивительным оказывается то, что и многие природные объекты обладают как бы дробной размерностью, хотя, строго говоря, для природных объектов такую размерность вычислить невозможно. Правильнее сказать, что в определённых диапазонах наблюдения природные объекты, возникшие в результате долгой диффузии и абсорбции, похожи на фрактальные множества. Например, размерность побережья лежит между 1,01 и 1,6. А фрактальная размерность кровеносной системы человека может быть рассчитана как приблизительно 3,4. Это не противоречит факту трехмерной топологической размерности пространства, в которое она вписана.
Применение фракталов
Генерация изображений природных объектов
Фрактальное дерево
Геометрические фракталы применяются для получения изображений деревьев, кустов, береговых линий и т. д. Алгебраические и стохастические — при построении ландшафтов, поверхности морей, карт раскраски, моделей биологических объектов и др.
Механика жидкостей
Фракталами хорошо описываются следующие процессы, относящиеся к механике жидкостей и газов:
динамика и турбулентность сложных потоков;
моделирование пламени;
изучение пористых материалов, в том числе в нефтехимии.
Биология
Моделирование популяций;
биосенсорные взаимодействия;
процессы внутри организма, например, биение сердца.
Литература
Среди литературных произведений находят такие, которые обладают текстуальной, структурной или семантической фрактальной природой. В текстуальных фракталах потенциально бесконечно повторяются элементы текста
неразветвляющееся бесконечное дерево, тождественные самим себе с любой итерации («У попа была собака…», «Притча о философе, которому снится, что он бабочка, которой снится, что она философ, которому снится…», «Ложно утверждение, что истинно утверждение, что ложно утверждение…»)
неразветвляющиеся бесконечные тексты с вариациями («У Пегги был веселый гусь…») и тексты с наращениями («Дом, который построил Джек»)
В структурных фракталах схема текста потенциально фрактальна
венок сонетов (15 стихотворений), венок венков сонетов (211 стихотворений), венок венков венков сонетов (2455 стихотворений)
«рассказы в рассказе» («Книга тысячи и одной ночи», Я.Потоцкий «Рукопись, найденная в Сарагоссе»)
предисловия, скрывающие авторство (У.Эко «Имя розы»)
Т.Стоппард «Розенкранц и Гильденстерн мертвы» (сцена с представлением перед королем)
В семантических и нарративных фракталах автор рассказывает о бесконечном подобии части целому
Х. Л. Борхес «В кругу развалин»
Х.Кортасар «Жёлтый цветок»
Ж.Перек «Кунсткамера»
Фрактальные антенны
Использование фрактальной геометрии при проектировании антенных устройств было впервые применено американским инженером Натаном Коэном, который тогда жил в центре Бостона, где была запрещена установка на зданиях внешних антенн. Натан вырезал из алюминиевой фольги фигуру в форме кривой Коха и наклеил её на лист бумаги, а затем присоединил к приёмнику. Оказалось, что такая антенна работает не хуже обычной. И хотя физические принципы работы такой антенны не изучены до сих пор, это не помешало Коэну основать собственную компанию и наладить их серийный выпуск.
Сжатие изображений
 Ещё одно фрактальное дерево
Существуют алгоритмы для сжатия изображения с помощью фракталов. Они основаны на теореме Банаха о сжимающих преобразованиях (также известной как Collage Theorem) и являются результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли.
Идея заключается в следующем: предположим что исходное изображение является неподвижной точкой некоего сжимающего отображения. Тогда можно вместо самого изображения запомнить каким-либо образом это отображение, а для восстановления достаточно многократно применить это отображение к любому стартовому изображению.
По теореме Банаха, такие итерации всегда приводят к неподвижной точке, то есть к исходному изображению. На практике вся трудность заключается в отыскании по изображению наиболее подходящего сжимающего отображения и в компактном его хранении. Как правило, алгоритмы поиска отображения (то есть алгоритмы сжатия) в значительной степени переборные и требуют больших вычислительных затрат. В то же время, алгоритмы восстановления достаточно эффективны и быстры.
Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), т. е. определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).
Например, изображение кривой Коха можно закодировать четырмя аффинными преобразованиями, мы однозначно определим его с помощью всего 24-х коэффициентов.
Далее, поставив чёрную точку в любой точке картинки мы будем применять наши преобразования в случайном порядке некоторое (достаточно большое) число раз (этот метод ещё называют фрактальный пинг-понг). В результате точка обязательно перейдёт куда-то внутрь чёрной области на исходном изображении. Проделав такую операцию много раз мы заполним все чёрное пространство, тем самым восстановив картинку.
Несмотря на то, что группой Барнсли было создано программное обеспечение, реализующее эти алгоритмы (например, библиотеки фрактального сжатия используются в Microsoft Encarta), осталась проблема скорости сжатия. Достаточно эффективное решение не найдено до сих пор, а сам Майкл Барнсли продолжает упорно работать в выбранном направлении.
Децентрализованные сети
Система назначения IP-адресов в сети Netsukuku использует принцип фрактального сжатия информации для компактного сохранения информации об узлах сети. Каждый узел сети Netsukuku хранит всего 4 Кб информации о состоянии соседних узлов, при этом любой новый узел подключается к общей сети без необходимости в центральном регулировании раздачи IP-адресов, что, например, характерно для сети Интернет. Таким образом, принцип фрактального сжатия информации гарантирует полностью децентрализованную, а следовательно, максимально устойчивую работу всей сети
Галерея
См. также Фрактал на Викискладе?Квазифрактал Мультифрактал Бесконечная вложенность материи 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 Gnofract 4D IFS Illusions — Искусственное искусство программа и галереи Сайты о фракталахФрактальные множества — Очень подробная и качественная статья, начиная с комплексных чисел (Санкт-Петербургский государственный университет: ПМ-ПУ) Архивохранилище Фрактал опубликовало на USENET Фракталы и теория хаосаВведение во фракталыДоступно о фракталахФракталы в НГУ: описания, форум, программа IFS Builder 3d Фракталы от OCoФракталы, как следствие работы алгоритмов в природеКрасивая жизнь комплексных чиселFractals of aramin (англ.) Электронная библиотека по нелинейной динамике — книги о фракталах Фракталы, мультифракталы и не только Фракталы в литературе: в поисках утраченного оригинала Фрактальные системы. Основы теории систем. Фракталы Др. Снейка. Фрактальная корова в 3D (англ.) — пример с наличием сарказма и исходных кодов для фрактализации объектов в Blender ЛитератураМандельброт Б. Фрактальная геометрия природы. — М.: «Институт компьютерных исследований», 2002. Пайтген Х.-О., Рихтер П. Х. Красота фракталов. — М.: «Мир», 1993. Федер Е. Фракталы. — М: «Мир», 1991. Фоменко А. Т. Наглядная геометрия и топология. — М.: изд-во МГУ, 1993. Фракталы в физике. Труды 6-го международного симпозиума по фракталам в физике, 1985. — М.: «Мир», 1988. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. — Ижевск: «РХД», 2001. Мандельброт Бенуа, Ричард Л. Хадсон (Не)послушные рынки: фрактальная революция в финансах = The Misbehavior of Markets. — М.: «Вильямс», 2006. — С. 400. — ISBN 5-8459-0922-8 Эта статья входит в число избранных статей русскоязычного раздела Википедии.
|
