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

- 14 -

СОДЕРЖАНИЕ

1. ВВЕДЕНИЕ………………………………………………………2

2. КЛАССИЧЕСКИЕ ФРАКТАЛЫ……………………………..3

2.1. Самоподобие………………………………………………….3

2.2. Снежинка Коха………………………………………………3

2.3. Ковер Серпинского …………………………………………5

3. L-СИСТЕМЫ…………………………………………………....6

4. ХАОТИЧЕСКАЯ ДИНАМИКА………………………………10

4.1. Аттрактор Лоренца…………………………………………10

4.2. Множества Мандельброта и Жюлиа……………………..11

5. ЗАКЛЮЧЕНИЕ………………………………………………...13

6. СПИСОК ЛИТЕРАТУРЫ…………………………………….14

1.ВВЕДЕНИЕ

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

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

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

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

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

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

Многие замечательные свойства фракталов и хаоса открываются при изучении итерированных отображений. При этом начинают с некоторой функции y = f(x) и рассматривают поведение последовательности f(x), f(f(x)), f(f(f(x))),... В комплексной плоскости работы такого рода восходят, по всей видимости, к имени Кэли, который исследовал метод Ньютона нахождения корня в приложении к комплексным, а не только к вещественным, функциям (1879). Замечательного прогресса в изучении итерированных комплексных отображений добились Гастон Жюлиа и Пьер Фату (1919). Естественно, все было сделано без помощи компьютерной графики. В наши дни, многие уже видели красочные постеры с изображением множеств Жюлиа и множества Мандельброта, тесно с ними связанного. Освоение математической теории хаоса естественно начать именно с итерированных отображений.

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

2.КЛАСИЧЕСКИЕ ФРАКТАЛЫ

2.1. Самоподобие.

Разделим отрезок прямой на N равных частей. Тогда каждую часть можно считать копией всего отрезка, уменьшенного в 1/r раз. Очевидно, N и r связаны отношением Nr = 1 Если квадрат разбить на N равных квадратов (с площадью, в 1/r² раз меньше площади исходного), то соотношение запишется как Nr² = 1. Соответственно, общая формула соотношения запишется в виде:

Nr^d = 1. (2.1)

Множества, построенные выше, обладают целой размерностью. Зададимся вопросом, возможно ли такое построение, при котором показатель d в равенстве (2.1) НЕ является целым, то есть такое, что при разбиении исходного множества на N непересекающихся подмножеств, полученных масштабированием оригинала с коэффициентом r, значение d не будет выражаться целым числом. Ответ --- решительное да! Такое множество называется самоподобным фракталом. Величину d называют фрактальной (дробной) размерностью или размерностью подобия. Явное выражение для d через N и r находится логарифмированием обеих частей (2.1):

_logN

d = --------- (2.2)

log 1/r

Логарифм можно взять по любому основанию, отличному от единицы, например по основанию 10 или по основанию е ~ 2,7183.

2.2. Снежинка Коха.

Граница снежинки, придуманной Гельгом фон Кохом в 1904 году (рис.2.2.1), описывается кривой, составленной их трех одинаковых фракталов размерности d ~ 1,2618. Каждая треть снежинки строится итеративно, начиная с одной из сторон равностороннего треугольника. Пусть K_o --- начальный отрезок. Уберем среднюю треть и добавим два новых отрезка такой же длины, как показано на рис. 2.2.2. Назовем полученное множество K₁ . Повторим данную процедуру многократно, на каждом шаге заменяя среднюю треть двумя новыми отрезками. Обозначим через K_n фигуру, полученную после n-го шага.

Интуитивно ясно, что последовательность кривых K_n при n стремящемся к бесконечности сходится к некоторой предельной кривой К. Рассмотрим некоторые свойства этой кривой.

Если взять копию К, уменьшенную в три раза (r = 1/3), То всё множество К можно составить из N = 4 таких копий. Следовательно, отношение самоподобия (2.1) выполняется при указанных N и r, а размерность фрактала будет:

d = log(4)/log(3) ~ 1,2618

Рис 2.2.1. Снежинка Коха.

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

Рис. 2.2.2. Построение снежинки Коха.

- 14 -

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

Доказательство приводится в [1].

2.3. Ковер Серпинского.

Еще один пример простого самоподобного фрактала --- ковер Серпинского (рис. 2.3.1), придуманный польским математиком Вацлавом Серпинским в 1915 году. Сам термин ковер (gasket) принадлежит Мандельброту. В способе построения, следующем ниже, мы начинаем с некоторой области и последовательно выбрасываем внутренние подобласти. Позднее мы рассмотрим и другие способы, в частности с использованием L-систем, а также на основе итерированных функций.

Рис 2.3.1. Ковер Серпинского

Пусть начальное множество S₀ --- равносторонний треугольник вместе с областью, которую он замыкает. Разобьем S₀ на четыре меньшие треугольные области, соединив отрезками середины сторон исходного треугольника. Удалим внутренность маленькой центральной треугольной области. Назовем оставшееся множество S₁ (рис. 2.3.2). Затем повторим процесс для каждого из трех оставшихся маленьких треугольников и получим следующее приближение S₂. Продолжая таким образом, получим последовательность вложенных множеств S_n, чье пересечение образует ковер S.

Из построения видно, что весь ковер представляет собой объединение N = 3 существенно не пересекающихся уменьшенных в два раза копий; коэффициент подобия r = Ѕ (как по горизонтали, так и по вертикали). Следовательно, S --- самоподобный фрактал с размерностью:

d = log(3)/log(2) ~ 1,5850.

Рис. 2.3.2. Построение ковра Серпинского

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

1/4 + 3_*(1/4²) + 3²_*(1/4³) + … + 3^n-1_*(1/4ⁿ) + … .

Эта сумма равна 1 (доказательство в [1]). Следовательно, мы можем утверждать, что оставшееся множество S, то есть ковер, имеет площадь меры нуль. Это выделяет множество S в разряд «совершенного», в том смысле, что оно разбивает свое дополнение на бесконечное число треугольных областей, обладая при этом нулевой толщиной.

3. L-системы.

Понятие L-систем, тесно связанное с самоподобными фракталами, появилось только в 1968 году благодаря Аристриду Линденмайеру. Изначально L-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и ковер Серпинского. Некоторые другие классические построения, например кривые Пеано (работы Пеано, Гильберта, Серпинского), также укладываются в эту схему. И конечно, L-системы открывают путь к бесконечному разнообразию новых фракталов, что и послужило причиной их широкого применения в компьютерной графике для построения фрактальных деревьев и растений. Рассмотренные в данной курсовой работе L-системы ограничиваются случаем детерминированных L-систем и графикой на плоскости.

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

F --- переместиться вперед на один шаг, прорисовывая след.

b --- переместиться вперед на один шаг, НЕ прорисовывая след.

[ --- открыть ветвь (подробнее см. ниже)

] --- закрыть ветвь (подробнее см. ниже)

+ --- увеличить угол a на величину q

- --- уменьшить угол a на величину q

Размер шага и величина приращения по углу q задаются заранее и остаются неизменными для всех перемещений черепашки. Если начальное направление движения а (угол, отсчитываемый от положительного направления оси Х) не указано, то полагаем а равным нулю.

Несколько примеров иллюстрируют применение команд ветвления (обозначаются ],[) и вспомогательных переменных (обозначаются X, Y, и т.д.). Команды ветвления используются для построения деревьев растений, а вспомогательные переменные заметно облегчают построение некоторых L-систем.

Формально, детерминированная L-система состоит из алфавита, слова инициализации, называемого аксиомой или инициатором, и набора порождающих правил, указывающих, как следует преобразовывать слово при переходе от уровня к уровню (от итерации к итерации). К примеру, можно заменять букву F при помощи порождающего правила newf = F-F++F-F, что соответствует L-системе для снежинки Коха, рассматриваемой ниже. Символы +, -, ], [ не обновляются, а просто остаются на тех местах, где они встретились. Обновление букв в данном слове предполагается одновременным, то есть буквы слова одного уровня обновляются раньше любой буквы следующего уровня.

L-система, соответствующая снежинке Коха (рис. 2.2.1), задается следующим образом:

p = /3

Аксиома: F++F++F

Порождающее правило: newf = F-F++F-F

Графическое представление аксиомы F++F++F --- равносторонний треугольник. Черепашка делает один шаг вперед, затем угол а увеличивается на 2/3 и черепашка делает еще один шаг.

На первом шаге каждая буква F в слове-инициаторе F++F++F заменяется на F-F++F-F:

(F-F++F-F)+(F-F++F-F)+(F-F++F-F)

Повторяя этот процесс, на втором шаге получим:

F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F+F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F+ F-F++F-F- F-F++F-F++F-F++F-F-F-F++F-F

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

Вот еще некоторые фракталы, построенные с использованием L-системы:

Рис. 3.1. Дракон Хартера-Хатвея после 12-ти итераций

и его L-система:

p = /4

Аксиома: FX

Порождающее правило: newf = F

newx = X+YF+

newy = -FX-Y

Рис 3.2. Дерево после 5-ти итераций

и его L-система:

p = /7

Аксиома: F

Порождающее правило: newf = F[+F]F[-F]F

Рис. 3.3. Квадрат Госпера после 2-х итераций [2]

и его L-система:

p = /2

Аксиома: -FX

Порождающее правило: newf = F

newx=+FYFY-FX-FX+FY+FYFX+FY-FXFX-FY-FX+FYFXFX-FY-FXFY+FY+FX-FX-FY+FY+FXFX

newy=FYFY-FX-FX+FY+FY-FX-FXFY+FX+FYFYFX-FY+FX+FYFY+FX-FYFX-FX-FY+FY+FXFX-

4. ХАОТИЧЕСКАЯ ДИНАМИКА

4.1. Аттрактор Лоренца

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

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

Рассмотрим знаменитый пример, весьма наглядно демонстрирующий, что стоит за термином «хаотическая динамика». Эдвард Лоренц из Массачусетского технологического института в 1961 году занимался численными исследованиями метеосистем, в частности моделированием конвекционных токов в атмосфере Исследование аттрактора Лоренца включается сейчас в любой

математический пакет, например, Mathematica, Maple.. Он написал программу для решения следующей системы дифференциальных уравнений:

dx/dt = (-x + y),

dy/dt = rx - y - xz,

dz/dt = -bz + xy.

В дальнейших расчетах параметры , r и b постоянны и принимают значения = -10, r = 28 и b = 8/3.

Согласно описанию эксперимента, принадлежащему самому Лоренцу, он вычислял значения решения в течение длительного времени, а затем остановил счет. Его заинтересовала некоторая особенность решения, которая возникала где-то в середине интервала счета, и поэтому он повторил вычисления с этого момента. Результаты повторного счета, очевидно, совпали бы с результатами первоначального счета, если бы начальные значения для повторного счета в точности были равны полученным ранее значениям для этого момента времени. Лоренц слегка изменил эти значения, уменьшив число верных десятичных знаков. Ошибки, введенные таким образом, были крайне невелики. Но самое неожиданное было впереди. Вновь сосчитанное решение некоторое время хорошо согласовывалось со старым. Однако, по мере счета расхождение возрастало, и постепенно стало ясно, что новое решение вовсе не напоминает старое (рисунки приведены в [1], стр. 149).

Лоренц вновь повторял и проверял вычисления (вероятно, не доверяя компьютеру), прежде чем осознал важность эксперимента. То, что он наблюдал, теперь называется существенной зависимостью от начальных условий --- основной чертой, присущей хаотической динамике. Существенную зависимость иногда называют эффектом бабочки. Такое название относится к невозможности делать долгосрочные прогнозы погоды. Сам Лоренц разъяснил это понятие в статье «Предсказуемость: может ли взмах крылышек бабочки в Бразилии привести к образованию торнадо в Техасе?», опубликованной в 1979 году [3, стр. 322].

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

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

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

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

Множество Мандельброта и множество Жюлиа определяется как граница множества точек z, стремящихся к бесконечности при итерировании

f(z) = z²+c,

где с - комплексная константа. При этом множества Жюлиа (см. рис. 4.2.2) при разных с могут представляться как угодно сложно и красиво, но все они распределяются на два типа: связные или несвязные. Множество Мандельброта (см. рис. 4.2.1) служит индикатором для двух типов множеств Жюлиа функции z²+c. Каждая точка в множестве Мандельброта представляет значение с, для которого множество Жюлиа вполне связно и каждая точка из дополнения к множеству Мандельброта представляет значение с, для которого множество Жюлиа вполне несвязно.

Построение данных множеств сводится к построению орбит f(z), проверяемых на ограниченность. То есть на рисунок попадает только та точка на комплексной плоскости (представляемая плоским экраном монитора), которая при итерировании функции f(z₀), последняя не стремится к бесконечности, а остается ограниченной на каком-то уровне. Проверка идет для каждой точки (x,y).

Несложно написать программу для построения множества Мандельброта. Единственная проблема, которая может возникнуть при использовании этой программы на маломощных ЭВМ --- большой объем вычислений. Для того, чтобы получить приемлемое изображение множества, желательно отображать по меньшей мере 256x256 пикселов. Более удачные визуализации получаются при использовании окна 400x400 пикселов и более. При этом количество итераций достаточно 20-ти. Для получения более качественного построения множества можно увеличить количество итераций до 50, 70, 100 и более.

Рис 4.2.1 Область 3-периодичности множества Мандельброта

Рис. 4.2.2. Множество Жюлиа.

5. ЗАКЛЮЧЕНИЕ.

Данная курсовая работа является введением в мир фракталов. Мы рассмотрели только самую малую часть того, какие бывают фракталы, на основе каких принципов они строятся. Например в книгу [1] включено рассмотрение СИФ (систем итерированных функций), случайных фракталов, и многое другое из теории фракталов.

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

1. Сжатие изображений и информации

2. Сокрытие информации на изображении, в звуке,…

3. Шифрование данных с помощью фрактальных алгоритмов

4. Создание фрактальной музыки

5. Моделирование систем

6. СПИСОК ЛИТЕРАТУРЫ

1. Фракталы и хаос в динамических системах. Основы теории. Москва: Постмаркет, 2000. - 352 с.

2. Программа FractInt © 1990 Soup Group Company.

3. James Gleick, Chaos: Making a New Science, Viking, New York, 1987.