Материал: Создание фракталов

Создание фракталов

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Кафедра информатики и вычислительной математики

Курсовая работа

Создание фракталов

Научный руководитель:

2010 г.

Введение

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

Х. О. Пайген и П. Х. Рихтер

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

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

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

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

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

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

·        Обладает нетривиальной структурой на всех шкалах. В этом отличие от регулярных фигур (таких, как окружность, эллипс <#"786118.files/image001.gif">

Рис.1. Кривая Пеано

На первом шаге он брал прямую линию и заменял ее на 9 отрезков длинной в 3 раза меньшей, чем длинна исходной линии (Часть 1 и 2 рис.1). Далее он делал то же самое с каждым отрезком получившейся линии. И так до бесконечности. Ее уникальность в том, что она заполняет всю плоскость. Доказано, что для каждой точки на плоскости можно найти точку, принадлежащую линии Пеано. Кривая Пеано и пыль Кантора выходили за рамки обычных геометрических объектов. Они не имели четкой размерности. Пыль Кантора строилась вроде бы на основании одномерной прямой, но состояла из точек (размерность 0). А кривая Пеано строилась на основании одномерной линии, а в результате получалась плоскость. Во многих других областях науки появлялись задачи, решение которых приводило к странным результатам, на подобие описанных выше (Броуновское движение, цены на акции).

Эти удивительные фигуры стали широко известны в 70-х годах прошлого века благодаря Бенуа Мандельброту, работавшему тогда математическим аналитиком в фирме IBM. Сопоставляя факты, он пришел к открытию нового направления в математике - фрактальной геометрии. Он придумал и само слово «фрактал», которое образовано от латинского fractus - дробный».

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

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

фрактал кох серпинский

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

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

·              Детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).

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

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

·      Они имеют тонкую структуру, т.е. содержат произвольно малые масштабы.

·        Они слишком нерегулярны, чтобы быть описанными на традиционном геометрическом языке.

·        Они имеют некоторую форму самоподобия, допуская приближенную.

·        Они имеют дробную «фрактальную» размерность, называемую также размерностью Минковского. (для самоподобных множеств, типа канторового множества)

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

История фракталов началась с геометрических фракталов, которые исследовались математиками в XIX веке.

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

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

·              кривая дракона;

·              кривая Коха - несамопересекающаяся непрерывная кривая бесконечной длины, не имеющая касательной ни в одной точке;

·              кривая Леви;

·              кривая Минковского;

·              кривая Пеано - непрерывная кривая, проходящая через все точки квадрата.

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

·              множество Кантора - нигде не плотное несчётное совершенное множество. Модифицировав процедуру, можно также получить нигде не плотное множество положительной длины.

·              треугольник Серпинского - аналог множества Кантора на плоскости.

·              коврик Серпинского - аналог множества Кантора на плоскости.

·              губка Менгера - аналог множества Кантора в трёхмерном пространстве.

·              дерево Пифагора.

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

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

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

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

Рис. 3. Треугольник Серпинского

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

Рис. 4. Драконова ломаная

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

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

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

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

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

Наиболее изучен случай, когда динамическая система задаётся итерациями многочлена или голоморфной функции комплексной переменной на плоскости. Первые исследования в этой области относятся к началу XX века и связаны с именами Фату и Жюлиа.

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

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

·              множество Мандельброта;

·              множество Жюлиа;

·              бассейны Ньютона;

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

·              С течением времени | z | стремится к бесконечности;

·              | z | стремится к 0;

·              | z | принимает несколько фиксированных значений и не выходит за их пределы;

·              Поведение | z | хаотично, без каких-либо тенденций.

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

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

Другой вариант получения фрактальных множеств - введение параметра в многочлен F(z) и рассмотрение множества тех значений параметра, при которых последовательность zn демонстрирует определённое поведение при фиксированном z0. Так, множество Мандельброта - это множество всех , при которых zn для F(z) = z2 + c и z0 = 0 не стремится к бесконечности.

Ещё один известный пример такого рода - бассейны Ньютона.

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

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

·              Действительная часть z меньше определённого числа;

·              Мнимая часть z меньше определённого числа;

·              И мнимая и действительная части z меньше какого-либо числа;

·              Другие способы.

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

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

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

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

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

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