Фракталы!


Введение во фракталы


1. Понятие "фрактал"

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

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

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

Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому" [3].


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

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

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

Рис 1. Построение триадной кривой Кох.

Рассмотрим один из таких фрактальных объектов - триадную кривую Кох [3]. Построение кривой начинается с отрезка единичной длины (рис.1) - это 0-е поколение кривой Кох. Далее каждое звено (в нулевом поколении один отрезок) заменяется на образующий элемент, обозначенный на рис.1 через n=1. В результате такой замены получается следующее поколение кривой Кох. В 1-ом поколении - это кривая из четырех прямолинейных звеньев, каждое длиной по 1/3. Для получения 3-го поколения проделываются те же действия - каждое звено заменяется на уменьшенный образующий элемент. Итак, для получения каждого последующего поколения, все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. На рис.1 представлены пять поколений кривой. При n стремящемся к бесконечности кривая Кох становится фрактальным обьектом [3].

Рис 2. Построение "дракона" Хартера-Хейтуэя

Для получения другого фрактального объекта нужно изменить правила построения. Пусть образующим элементом будут два равных отрезка, соединенных под прямым углом. В нулевом поколении заменим единичный отрезок на этот образующий элемент так, чтобы угол был сверху. Можно сказать, что при такой замене происходит смещение середины звена. При построении следующих поколений выполняется правило: самое первое слева звено заменяется на образующий элемент так, чтобы середина звена смещалась влево от направления движения, а при замене следующих звеньев, направления смещения середин отрезков должны чередоваться. На рис.2 представлены несколько первых поколений и 11-е поколение кривой, построенной по вышеописанному принципу. Предельная фрактальная кривая (при n стремящемся к бесконечности) называется драконом Хартера-Хейтуэя [3].

В машинной графике использование геометрических фракталов необходимо при получении изображений деревьев, кустов, береговой линии. Двухмерные геометрические фракталы используются для создания объемных текстур (рисунка на поверхности обьекта) [2,3].



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

Год выпуска: 2008
Страна: США
Жанр: документальный, научно-популярный
Продолжительность: 00:53:13
Перевод: Профессиональный (одноголосый)
Режиссер: Билл Джерси / Bill Jersey, Майкл Шварц / Michael

продолжение следует

Комментарии (62)

Всего: 62 комментария
  
#1 | Anatoly »» | 31.05.2013 17:56
  
3
2.2 Алгебраические фракталы

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

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

Рис 3. Множество Мандельброта.


В качестве примера рассмотрим множество Мандельброта (см. pис.3 и рис.4). Алгоритм его построения достаточно прост и основан на простом итеративном выражении:

Z[i+1] = Z[i] * Z[i] + C,

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

Рис 4. Участок границы множества Мандельброта, увеличенный в 200 pаз.

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

2.3 Стохастические фракталы
Еще одним известным классом фракталов являются стохастические фракталы, которые получаются в том случае, если в итерационном процессе случайным образом менять какие-либо его параметры. При этом получаются объекты очень похожие на природные - несимметричные деревья, изрезанные береговые линии и т.д. Двумерные стохастические фракталы используются при моделировании рельефа местности и поверхности моря [2].

Существуют и другие классификации фракталов, например деление фракталов на детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).
  
#2 | Анатолий »» | 01.06.2013 17:47
  
4
3. Системы итерируемых функций

Метод "Систем Итерируемых Функций" (Iterated Functions System - IFS) появился в середине 80-х годов как простое средство получения фрактальных структур.

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

X' = A*X + B*Y + C
Y' = D*X + E*Y + F


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

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

Например, закодировав какое-то изображение двумя аффинными преобразованиями, мы однозначно определяем его с помощью 12-ти коэффициентов. Если теперь задаться какой-либо начальной точкой (например X=0 Y=0) и запустить итерационный процесс, то мы после первой итерации получим две точки, после второй - четыре, после третьей - восемь и т.д. Через несколько десятков итераций совокупность полученных точек будет описывать закодированное изображение. Но проблема состоит в том, что очень трудно найти коэффициенты IFS, которая кодировала бы произвольное изображение.

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

X' = (A1*X + B1*Y + C1) / (D1*X + E1*Y + F1)
Y' = (A2*X + B2*Y + C2) / (D2*X + E2*Y + F2)


или квадратичные:

X' = A1*X*X + B1*X*Y + C1*Y*Y + D1*X + E1*Y + F1
Y' = A2*X*X + B2*X*Y + C2*Y*Y + D2*X + E2*Y + F2


преобразования на плоскости.

В качестве примера использования IFS для построения фрактальных структур, рассмотрим кривую Коха (Рис.1) и "дракона" Хартера-Хейтуэя (Рис.2). Выделим в этих структурах подобные части и, для каждой из них вычислим коэффициенты аффинного преобразования. В аффинный коллаж будет включено столько аффинных преобразований, сколько существует частей подобных целому изображению.

Рис 5. Заготовка для построения IFS "дракона" Хартера-Хейтуэя.

Построим IFS для "дракона" Хартера-Хейтуэя. Для этого расположим первое поколение этого фрактала на сетке координат дисплея 640 x 350 (Рис.5). Обозначим точки получившейся ломаной A, B, C. По правилам построения (раздел 2.1) у этого фрактала две части, подобные целому - на рис.5 это ломаные ADB и BEC. Зная координаты концов этих отрезков, можно вычислить коэффициенты двух аффинных преобразований, переводящих ломаную ABC в ADB и BEC:

X' = -0.5*X -0.5*Y + 490
Y' = 0.5*X -0.5*Y + 120

X' = 0.5*X -0.5*Y + 340
Y' = 0.5*X +0.5*Y - 110


Задавшись начальной стартовой точкой (например X=0 Y=0) и итерационно действуя на нее этой IFS, после десятой итерации на экране получим фрактальную структуру, изображенную на рис.6, которая представляет собой "дракон" Хартера-Хейтуэя. Его кодом (сжатым описанием) является набор коэффициентов двух аффинных преобразований.

Рис 6. "Дракон" Хартера-Хейтуэя, постpоенный с помощью IFS в пpямоугольнике 640x350.

Аналогично можно построить IFS для кривой Кох. Нетрудно видеть, что эта кривая имеет четыре части, подобные целой кривой (раздел 2.1 Рис 1.). Для нахождения IFS опять расположим первое поколение этого фрактала на сетке координат дисплея 640 x 350 (Рис.7).

Рис 7. Заготовка для построения IFS кpивой Кох.

Для ее построения требуется набор аффинных преобразований, состоящий из четырех преобразований:

X' = 0.333*X + 13.333
Y' = 0.333*Y + 200

X' = 0.333*X + 413.333
Y' = 0.333*Y + 200

X' = 0.167*X + 0.289*Y + 130
Y' = -0.289*X + 0.167*Y + 256

X' = 0.167*X - 0.289*Y + 403
Y' = 0.289*X + 0.167*Y + 71


Результат применения этого аффинного коллажа после десятой итерации можно увидеть на рис.8.

Рис 8. Кpивая Кох, постpоенная с помощью IFS в пpямоугольнике 640x350.

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

Шабаршин А.А

Библиографический список

[1] Бондаренко В.А.,Дольников В.Л. Фрактальное
сжатие изображений по Барнсли-Слоану.
// Автоматика и телемеханика.-1994.-N5.-с.12-20.

[2] Ватолин Д. Применение фракталов в машинной графике.
// Computerworld-Россия.-1995.-N15.-с.11.

[3] Федер Е. Фракталы. Пер. с англ.-М.: Мир,1991.-254с.
(Jens Feder, Plenum Press, NewYork, 1988)

[4] Application of fractals and chaos. 1993, Springer-Verlag, Berlin.
  
#3 | Анатолий »» | 02.06.2013 19:58
  
3
Рассмотрим фракталы с другой стороны.

ВВЕДЕНИЕ В ТЕОРИЮ ХАОСА


ЧТО ТАКОЕ ТЕОРИЯ ХАОСА?

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




теория хаоса


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




НЕПРАВИЛЬНЫЕ ПРЕДСТАВЛЕНИЯ О ТЕОРИИ ХАОСА

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


ТЕОРИЯ ХАОСА О БЕСПОРЯДКЕ

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


Это правда, что теория хаоса утверждает, что небольшие изменения могут породить огромные последствия. Но одной из центральных концепций в теории является невозможность точного предсказания состояния системы. В общем, задача моделирования общего поведения системы вполне выполнима, даже проста. Таким образом, теория хаоса сосредотачивает усилия не на беспорядке системы — наследственной непредсказуемости системы — а на унаследованном ей порядке — общем в поведении похожих систем.
Таким образом, было бы неправильным сказать, что теория хаоса о беспорядке. Чтобы пояснить это на примере, возьмем аттрактор Лоренца. Он основан на трех дифференциальных уравнениях, трех константах и трех начальных условиях.

Рис 1. Аттрактор Лоренца

ТЕОРИЯ ХАОСА О БЕСПОРЯДКЕ

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


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


Теория хаоса говорит, что сложные нелинейные системы являются наследственно непредсказуемыми, но, в то же время, теория хаоса утверждает, что способ выражения таких непредсказуемых систем оказывается верным не в точных равенствах, а в представлениях поведения системы — в графиках странных аттракторов или во фракталах. Таким образом, теория хаоса, о которой многие думают как о непредсказуемости, оказывается, в то же время, наукой о предсказуемости даже в наиболее нестабильных системах.
  
#4 | Анатолий »» | 03.06.2013 14:51
  
4
ПРИМЕНЕНИЕ ТЕОРИИ ХАОСА В РЕАЛЬНОМ МИРЕ

При появлении новых теорий, все хотят узнать что же в них хорошего. Итак что хорошего в теории хаоса?


Первое и самое важное — теория хаоса — это теория. А значит, что большая ее часть используется больше как научная основа, нежели как непосредственно применимое знание. Теория хаоса является очень хорошим средством взглянуть на события, происходящие в мире отлично от более традиционного четко детерминистического взгляда, который доминировал в науке со времен Ньютона. Зрители, которые посмотрели Парк Юрского периода, без сомнения боятся, что теория хаоса может очень сильно повлиять на человеческое восприятие мира, и, в действительности, теория хаоса полезна как средство интерпретации научных данных по-новому. Вместо традиционных X-Y графиков, ученые теперь могут интерпретировать фазово-пространственные диаграммы которые — вместо того, чтобы описывать точное положение какой-либо переменной в определенный момент времени — представляют общее поведение системы. Вместо того, чтобы смотреть на точные равенства, основанные на статистических данных, теперь мы можем взглянуть на динамические системы с поведением похожим по своей природе на статические данные — т.е. системы с похожими аттракторами. Теория хаоса обеспечивает прочный каркас для развития научных знаний.


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


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


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


Фракталы находятся везде, наиболее заметны в графических программах как например очень успешная серия продуктов Fractal Design Painter. Техники фрактального сжатия данных все еще разрабатываются, но обещают удивительные результаты как например коэффициента сжатия 600:1. Индустрия специальных эффектов в кино, имела бы горазда менее реалистичные элементы ландшафта (облака, скалы и тени) без технологии фрактальной графики.


И, конечно, теория хаоса дает людям удивительно интересный способ того, как приобрести интерес к математике, одной из наиболее мало-популярной области познания на сегодняшний день.
  
#5 | Анатолий »» | 03.06.2013 14:54
  
3
БРОУНОВСКОЕ ДВИЖЕНИЕ И ЕГО ПРИМЕНЕНИЯ

Рис 2. Частотная диаграмма

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


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


Рис 3.

Кроме применения Броуновского движения для получения фракталов из фракталов, оно может использоваться и для создания ландшафтов. Во многих фантастических фильмах, как например Star Trek техника Броуновского движения была использована для создания инопланетных ландшафтов таких, как холмы и топологические картины высокогорных плато. Эти техники очень эффективны, и их можно найти в книге Мандельброта Фрактальная геометрия природы. Мандельброт использовал Броуновские линии для создания фрактальных линий побережья и карт островов (которые на самом деле были просто в случайном порядке изображенные точки) с высоты птичьего полета.
  
#6 | Анатолий »» | 04.06.2013 17:11
  
3
ДВИЖЕНИЕ БИЛЛИАРДНОГО ШАРИКА

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


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


Насколько долго? Это зависит частично от точности вашего компьютера, но в большей степени от формы стола. Для совершенно круглого стола, можно просчитать приблизительно до 500 положений столкновений с ошибкой около 0.1 процента. Но стоит изменить форму стола так, чтобы она стала хотя бы немножко неправильной (овальной), и непредсказуемость траектории может превышать 90 градусов уже после 10 столкновений! Единственный путь получить картинку общего поведения бильярдного шарика, отскакивающего от чистого стола — это изобразить угол отскока или длину дуги соответствующую каждому удару. Здесь приведены два последовательных увеличения такой фазово-пространственной картины.

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

  
#7 | Анатолий »» | 04.06.2013 17:15
  
3
ИНТЕГРАЦИЯ ДЕТЕРМИНИРОВАННЫХ ФРАКТАЛОВ И ХАОС

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


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


Для начала нужно сгенерировать Дерево Пифагора (слева). Результат напоминает те старые детсадовские рисунки… Так что давайте сделаем ствол толще. На этой стадии Броуновское движение не используется. Вместо этого, каждый отрезок линии теперь стал линией симметрии прямоугольника, который становится стволом, и веток снаружи.

Рис 7.

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

Рис 8.

Теперь можно использовать Броуновское движение для создания некоторой случайной беспорядочности, которая изменяет числа, округляя их до двух разрядов. В оригинале были использованы 39 разрядные десятичные числа. Результат (слева) не выглядит как дерево. Вместо этого, он выглядит как хитроумный рыболовный крючок!

Рис 9.

Может быть округление до 2 разрядов было слишком уж много? Снова применяем Броуновское движение, округленное на этот раз до 7 разрядов. Результат по-прежнему выглядит как рыболовный крючок, но на этот раз в форме логарифмической спирали!

Рис 9.

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

Автор: Иван Тугой
  
#8 | Анатолий »» | 05.06.2013 18:31
  
2
СЛОЖНЫЕ ФРАКТАЛЫ

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

ОБЩАЯ ХАРАКТЕРИСТИКА

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


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

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


Детерминистские фракталы являются линейными, тогда как сложные фракталы таковыми не являются. Будучи нелинейными, эти фракталы генерируются тем, что Мандельброт назвал нелинейными алгебраическими уравнениями. Хороший пример — это процесс Zn+1=ZnІ + C, что является уравнением, используемым для построения множества Мандельброта и Жулии второй степени. Решение этих математических уравнений вовлекает комплексные и мнимые числа. Когда уравнение интерпретируется графически на комплексной плоскости, результатом оказывается странная фигура, в которой прямые линии переходят в кривые, появляются хотя и не без деформаций, эффекты самоподобия на различных масштабных уровнях. При этом вся картина в целом является непредсказуемой и очень хаотичной.


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


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


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


Сложные фракталы отличаются от детерминистских в том смысле, что они бесконечно сложные, но, при этом, могут быть сгенерированы очень простой формулой. Детерминистским фракталам не нужны формулы или уравнения. Просто возьмите чертежную бумагу и вы можете построить решето Серпинского до 3 или 4 итерации без каких-либо затруднений. Попробуйте сделать это с множеством Жулиа! Легче пойти мерить длину береговой линии Англии!
  
#9 | Анатолий »» | 06.06.2013 17:45
  
2
МНОЖЕСТВО МАНДЕЛЬБРОТА


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


Множество Мандельброта, которое чаще всего можно увидеть — это множество Мандельброта 2й степени, то есть а=2. Тот факт, что множество Мандельброта не только Zn+1=ZnІ+C, а фрактал, показатель в формуле которого может быть любым положительным числом ввел в заблуждение многих. На этой странице вы видите пример множества Мандельброта для различных значений показателя а.


Рис 3. Появление пузырьков при a=3.5

Также популярен процесс Z=Z*tg(Z+C). Благодаря включению функции тангенса, получается множество Мандельброта, окруженное областью, напоминающей яблоко. При использовании функции косинуса, получаются эффекты воздушных пузырьков. Короче говоря, существует бесконечное количество способов настройки множества Мандельброта для получения различных красивых картинок
  
#10 | Анатолий »» | 06.06.2013 17:47
  
2
МНОЖЕСТВО ЖУЛИА

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

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

Хотя это нельзя увидеть на картинке, фрактал Мандельброта — это, на самом деле, множество фракталов Жулиа, соединенных вместе. Каждая точка (или координата) множества Мандельброта соответствует фракталу Жулиа. Множества Жулиа можно сгенерировать используя эти точки в качестве начальных значений в уравнении Z=ZІ+C. Но это не значит, что если выбрать точку на фрактале Мандельброта и увеличить ее, можно получить фрактал Жулиа. Эти две точки идентичны, но только в математическом смысле. Если взять эту точку и просчитать ее по данной формуле, можно получить фрактал Жулиа, соответствующий определенной точке фрактала Мандельброта.

Автор: Иван Тугой
  
#11 | Анатолий »» | 07.06.2013 18:29
  
3
БИФУРКАЦИИ В МОДЕЛЯХ ПОПУЛЯЦИЙ


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


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


Новая популяция = скорость роста * старая популяция (1 – старая популяция)


Где популяция нормализована так, что она принимает значения от 0 до 1. Естественно, такая модель является сильно упрощенной и не может достаточно точно описывать динамику развития популяций. При скорости роста меньше 200%, эта модель стабильна, т.к. для любого начального значения, после нескольких поколений, численность популяции устанавливается на стабильном уровне. Но если скорость роста превышает 200%, кривая, графически отображающая уравнение, разделяется или бифурцирует на два дискретных решения, затем на четыре, и вскоре становится хаотической.

ДЕРЕВО ФЕЙГЕНБАУМА

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


f(x) = (1 – x)rx


Простейшая модель — это пропорциональное соотношение численности с прошлым годом. Допустим в прошлом году у нас было x животных. В этом году их должно быть rx животных. Но это не выполняется в реальных условиях. Лучшее соответствие с реальностью получится если добавить фактор, зависящий от того какой потенциал существует у популяции для дальнейшего развития, и пусть x — коэффициент полноты, который меняется от 0 до 1. Потом добавляется фактор 1 – x, так что территория почти полностью заполнена, популяция не возрастет выше верхнего предела.


Расширяя логистическое выражение, получаем:


f(x) = аx – ах2


Формула, использующаяся в программе LT Bifurcator для объяснения сущности фрактала Фейгенбаума — (1 + r)x – rx2 не сильно отличается от формулы, приведенной выше. В принципе, для изучения теории можно было использовать любую формулу, например самую простую из формул данного вида — xІ – r. Единственными различиями являются различия в координатах окон на картинке и несколько измененный внешний вид изображения.

Рис 1.
  
#12 | Анатолий »» | 08.06.2013 18:04
  
3
ПОЧЕМУ СИСТЕМА СТАНОВИТСЯ НЕПРЕДСКАЗУЕМОЙ?

Объяснение этому явлению дать не просто. Для каждой точки параметра r (по оси абсцисс), для функции x возможны следующие варианты. У функции могут быть:
периодическая орбита, т.е. она периодически принимает одно или несколько значений, что происходит с фракталом, приведенным здесь в качестве иллюстрации на сегменте 0 < r < 2.57

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

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

Когда параметр пробегает значения от 0 до 2, период функции равен единице. В этом случае, соответствующее значение функции называется фиксированной точкой. Эта фиксированная точка оказывается решением уравнения

x = (1 + r)x – rx2

(1 + r)x – rx2 – x = 0

Решения этого уравнения:

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


x=(1+r)x - rx2; r=2.1; x0=0.8

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

x = [(1 + r)x – rx2]2 + (1+r)x

В результате получается четыре решения, причем первые два из них являются решениями исходного выражения. Это достаточно очевидно, что они тоже появляются здесь. Но интерес представляют третье и четвертое выражения. Если мы подставим в них 2.1 (значение, использовавшееся при составлении таблицы), то получим соответственно 1,128746121 и 0,823648487, т.е. те же значения, что и в таблице. Чего, собственно говоря, и следовало ожидать. Графическое изображение функции также представляет интерес. Фактически, мы получаем начало фегенбаумова дерева. Установленные факты можно использовать для расчета точек бифуркаций. Третье и четвертое уравнения не определены при значении параметра меньше 2, т.е. там, где линия разветвляется.

ОКНА В ДЕРЕВЕ ФЕЙГЕНБАУМА

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


02 – r = 0
  
#13 | Анатолий »» | 10.06.2013 14:34
  
3
АТТРАКТОР И КОНСТАНТА ФЕЙГЕНБАУМА

АТТРАКТОР ФЕЙГЕНБАУМА

В отличие от константы Фейгенбаума, это число не является универсальным. Значение этого аттрактора зависит от того, какая используется формула. Для формулы, используемой в Lt Bifurcator x = (1 + r)x – rxІ графически можно найти значение приблизительно равное 2.56.


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


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


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



КОНСТАНТА ФЕЙГЕНБАУМА

Если бы от меня требовался короткий ответ, я бы сказал: Это приблизительно 4.669211660910299067185320382047...


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


Знаменитая постоянная появляется, когда вы сравниваете длину одной части дерева, т.е. частей между линией бифуркаций (смотри иллюстрацию). Первая часть от 0 до 2. Ее длина равна 2. Следующая часть — от 2 до 2.448 и ее длина 0,448. Отношение между двумя длинами — 2/0.448 = 4,4642. В общем-то это достаточно близко к значению константы Фейгенбаума, но, согласно теории, результат можно улучшить, если взять предел отношения n+1 длины отрезка к n при n стремящемся к бесконечности (конечно это стремление ограничено аттрактором Фейгенбаума).


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


Важно запомнить, что с каждой бифуркацией требуется просчитать все больше и больше значений, чтобы получить точный результат, т.к. функции требуется больше итераций для стабилизации. Если вы пытаетесь построить дерево Фейгенбаума лишь по нескольким точкам, бифуркации последуют раньше, чем это есть на самом деле. Это становится все более важно при все большем и большем приближении дерева. Я использовал около 1000 итераций для значений, приведенных в таблице.
  
#14 | Анатолий »» | 11.06.2013 19:44
  
2
ГЕНЕРАЦИЯ СЛУЧАЙНЫХ ЧИСЕЛ

Рис 2.

Посмотрите на распределение точек где-нибудь на правом краю дерева Фейгенбаума (Свойства -> Интервал -> Отрезок Псевдохаоса в программе Lt Bifurcator) Видите, они кажутся очень случайными. Так что кажется вполне оправданной идея использования этого для генерации случайных чисел.


Все что для этого может потребоваться — это запустить формулу x = (1 + r)x – rx2 или какую-либо ей подобную и использовать последнее вычисленное значение каждый раз, когда требуется случайное число. Да это сработает: вы получите орбиту, которая никогда не повторяется, так как там хаос, но, к несчастью, я проверил распределение точек и результат не оказался равномерным, т.е. возможно, не равный для всех интервалов.


Числа, вычисленные по формуле всегда лежат между –2 и 2. Это легко растянуть на интервал от 0 до 9 и сделать числа целыми. Я сделал это и посчитал сколько попаданий получилось для каждого числа при проведении многих тысяч итераций. Вот результат:


среднее x: 4.501
стандартное отклонение x: 3.430
Нетрудно увидеть, что это не дает желаемого распределения. Но может быть взять значения, лежащие ближе к 3? Новый тест:


среднее x: 4.489
стандартное отклонение x: 3.425
К сожалению, это дает нам почти такую же кривую распределения.

Примечание

Чтобы дать некоторое представление о среднем и стандартном отклонении: Если бы у нас был результат, который мы хотели получить, частота каждого числа между 0 и 9 была бы равна 5000, среднее значение было бы 4.5 и стандартное отклонение — 2.872.
  
#15 | Анатолий »» | 12.06.2013 22:22
  
2
ДЕРЕВО ФЕЙГЕНБАУМА И МНОЖЕСТВО МАНДЕЛЬБРОТА

Рис 3.

Если вы когда-либо видели формулу множетсва Мандельброта z=z2 + x, вы могли бы заметить схожесть между этой формулой и самой простой из формул для построения дерева Фейгенбаума x2 – r. И это действительно так. Сходство существует. Но фейгенбаумово дерево растет в другую сторону. Измените формулу Фейгенбаума на x2 + r и вы увидите сходство. Что касается множества Мандельброта, вам нужно смотреть вдоль горизонтальной оси, так как это единственная позиция в которой комплексная часть числа Мандельброта равна нулю. Вы увидите, что основное тело фигуры Мандельброта находится там, где функция в дереве Фейгенбаума принимает лишь одно значение. Когда происходит первое разделение линии (бифуркация) появляется новое тело на фигуре Мандельброта и т.д. Обратите также внимание на то, что когда в дереве открывается главное окно, на фигуре Мандельброта появляется дочернее тело.

Иван Тугой
Добавлять комментарии могут только
зарегистрированные пользователи!
 
Имя или номер: Пароль:
Регистрация » Забыли пароль?
 
Выгодно - смартфоны samsung.
© decoder.ru 2003 - 2017, создание портала - Vinchi Group & MySites