Реферат - Теория фракталов
Подождите немного. Документ загружается.
Оглавление
Введение……………………………………………………… 3
Глава 1. Основные понятия теории фракталов……………………… 5
Глава 2. Применение теории фракталов в информатике…………… 12
Заключение……………………………………………………. 19
Библиография………………………………………………… 20
Введение
В последние десятилетия популярность теории фракталов достаточно
высока, в значительной мере это обуславливается потребностями общества в
эффективных алгоритмах кодирования и сжатия информации с целью ее
распространения в компьютерных сетях, особенно в Интернет. Возникает
необходимость уменьшения объема данных с целью их компактного
хранения на диске и более высокой скорости передачи. С другой стороны,
развитие мощностей компьютеров позволяет проводить масштабные
исследования в данном направлении. Возможности компьютерного
моделирования позволяют создавать и изучать модели важных физических,
химических, биологических нелинейных процессов с помощью
математического аппарата теории фракталов. Отдельной строкой в
определении актуальности темы, на наш взгляд, можно выделить
компьютерную графику, где наглядное представление фракталов находит
широкое применение.
Целью исследования является краткое изложение основ теории
фракталов.
Задачи исследования:
1. Изучить и проанализировать основные понятия теории фракталов.
2. Рассмотреть вопросы применения теории фракталов в информатике.
Для решения поставленных задач была использована научная
литература, а также Интернет-источники и сведения из популярной
Интернет-энциклопедии Википедии, имеющие ссылки на источники. За
основу были взяты издания Института компьютерных исследований в
Ижевске. В первую очередь это классический труд Б. Мандельброта
«Фрактальная геометрия природы» (1975), который положил начало
исследованиям в области теории фракталов. Не менее важен для нас труд
отечественного ученого А.Д. Морозова «Введение в теорию фракталов», в
котором в доступной форме изложен математический аппарат, приведены
2
примеры и иллюстрации создания классических фракталов. В книгу
включены новые результаты по гиперкомплексной динамике.
В трудах Шредера и Кроновера, в сетевом проекте «Фракталы и теория
бифуркации» теория фракталов рассмотрена в связи с поведением
синергетических систем, параллельно с теорией хаоса.
Интересна статья Шестопалова и его коллег: здесь внимание
акцентируется не на фрактальных объектах, а на фрактальных процессах, что
позволяет сделать вывод об универсальности теории фракталов в
мировоззренческом смысле. Надо отметить, что А.В. Шестопаловым
написано несколько работ на эту тему.
Практическое применение теории фракталов для сжатия изображений в
информатике достаточно подробно описано в книге «Фракталы и вейвлеты
для сжатия изображений в действии» С. Уэлстида. Программы составлены на
языках С, С++. Даны листинги и их подробное объяснение. К книге
прилагается диск.
Использование материалов Википедии осуществлялось при условии
наличия ссылок на объективные источники.
3
Глава 1. Основные понятия теории фракталов
Теория фракталов как наука опирается на геометрию и теорию
размерности [2]. Фрактальная геометрия связана с изучением нерегулярных
множеств, т.е. обладающих хаотичной, нетривиальной структурой на всех
масштабах. Наглядно отличие нерегулярных структур от регулярных
проявляется в процессе их масштабирования: «если мы рассмотрим
небольшой фрагмент регулярной фигуры в очень крупном масштабе, он
будет похож на фрагмент прямой. Для фрактала увеличение масштаба не
ведёт к упрощению структуры, на всех шкалах мы увидим одинаково
сложную картину» [7]. Математически нерегулярные функции являются
недифференцируемыми, апериодическими, нелинейными и представляют
собой детерминированный хаос.
В основе фрактальной геометрии лежит понятие самоподобия,
подразумевающее инвариантность при мультипликативном изменении
масштабов или размеров. Если речь идет более, чем об одном масштабном
(скейлинговом) факторе, такую инвариантность называют самоаффинностью
[9]. Интересно, что «самоподобие - ...это единственная из всех симметрий,
которая порождает саму антитезу симметрии – хаос, состояние полного
беспорядка и отсутствие какой бы то ни было соразмерности», как отмечает
М. Шредер [8, с. 18].
Говоря о размерности фрактала, необходимо определить такие понятия
как топологическая размерность и фрактальная размерность. В данном
случае для нас важны не точные математические определения, а различение
данных понятий в контексте исследования. Топологическая размерность, или
размерность Лебега, связывается со свойством непрерывности пространства,
а т.к. фрактальные функции не являются непрерывными и
дифференцируемыми (см. выше), то топологическая размерность
определяемых ими фрактальных множеств равна нулю. Так, например,
нулевую топологическую размерность имеет множество Кантора (рис. 1).
4
Рис. 1. Конструкция фрактала Кантора
Фрактальная размерность, под которой обычно понимается
размерность Хаусдорфа (реже – Минковского), определяется для
метрических пространств (множеств точек с фиксированной функцией
расстояния – метрикой) и связывается с нестрого возрастающей функцией и,
таким образом, учитывает нелинейность фрактального множества.
Фрактальное множество обладает дробной метрической размерностью или
метрической размерностью, превосходящей топологическую [7]. Так,
хаусдорфова размерность множества Кантора в вышеприведенном примере
равна 0.6309...
1
[4].
Нерегулярность, самоподобие и размерность – это свойства, которые
характеризуют объект как фрактал. Фрактальными свойствами могут
обладать не только математические объекты, такие как множества и
функции, но и процессы, например, фрактально подобные геометрические
преобразования [5].
Примерами фрактальных структур в природе могут служить кроны
деревьев и горные хребты, система кровообращения и легкие человека,
каскадные водопады и турбулентные процессы в атмосфере и т.д. [2].
В настоящее время не существует однозначного определения фрактала.
Как сообщает открытый источник, «слово «фрактал» не является
математическим термином и не имеет общепринятого строгого
1
Математически фрактальная размерность d представляет собой степень r в соотношении между N, числом
равных подобъектов, и коэффициентом подобия r, а именно:
1
d
Nr
. Явное выражение для d через N и r
находится логарифмированием обеих частей указанного соотношения:
r
N
d
/1log
log
. Логарифм берется по
любому положительному основанию, отличному от единицы, например, 10 или
7183,2e
[1, с. 15].
5
математического определения. Оно может употребляться, когда
рассматриваемая фигура обладает какими-либо из перечисленных ниже
свойств» (имеются ввиду фрактальные свойства) [7].
Этимология понятия «фрактал» связывается с латинским «fractus», что
означает «изломанный», с одной стороны, и с английским «fractional» -
«дробный», с другой. В первом случае имеет место определение, данное Х.
Лаверье в 1991 году в книге «Фракталы – изображения хаоса», приведенное
А.Д. Морозовым в следующем варианте: «…фрактал – это геометрическая
фигура, в которой один и тот же фрагмент повторяется при каждом
уменьшении масштаба» [4, с. 7]. Такие фракталы порождаются простой
рекурсивной процедурой – комбинацией линейных (аффинных) сжимающих
отображений подобия – и называются конструктивными фракталами.
Результирующее отображение обладает устойчивой неподвижной «точкой» -
фракталом. Во втором случае, по мнению А.Д. Морозова, справедливо
определение по Б. Мандельброту (1975): фракталы – это «множества точек в
евклидовом пространстве, имеющие дробную метрическую размерность (в
смысле Минковского или Хаусдорфа), либо метрическую размерность,
строго большую топологической» [7]. Такие множества возникают в
синергетических системах, их построение не так просто, как в случае
конструктивных фракталов, они могут обладать масштабной
инвариантностью лишь приближенно и носят название динамических
фракталов. Надо отметить, что привязка фрактала Мандельброта к переводу
«дробный» английского слова «fractional» – авторская интерпретация, данная
А.Д. Морозовым. Сам Мандельброт так же, как и Лаверье, ссылается на
латинское причастие «fractus», образованное от глагола «frangere» - «ломать,
разламывать, т.е. создавать фрагменты неправильной формы», и ассоциирует
новый термин с такими значениями, как «фрагментированный»,
«неправильный по форме» в словах «фракция», «рефракция», «фрагмент», но
не «дробный» [3].
6
Для того чтобы уточнить определения конструктивных и динамических
фракталов, приведем основные свойства фрактального множества F по
К.`Фальконеру [4, с. 10]:
«1. F имеет тонкую структуру, то есть содержит произвольно малые
масштабы;
2. F слишком нерегулярное, чтобы быть описанным на традиционном
геометрическом языке;
3. F имеет некоторую форму самоподобия, допуская приближенную
или статистическую;
4. Обычно «фрактальная размерность» множества F больше чем его
топологическая размерность;
5. В большинстве интересных случаев F определяется очень просто,
например, рекурсивно».
Для того чтобы представить все многообразие фракталов, удобно
прибегнуть к их общепринятой классификации [8]. Существует три класса
фракталов.
1. Геометрические фракталы.
Фракталы этого класса самые наглядные. В двухмерном случае их
получают с помощью ломаной (или поверхности в трехмерном случае),
называемой генератором. За один шаг алгоритма каждый из отрезков,
составляющих ломаную, заменяется на ломаную-генератор в
соответствующем масштабе. В результате бесконечного повторения этой
процедуры получается геометрический фрактал. В классификации
отечественного ученого А.Д. Морозова геометрические фракталы
соответствуют категории структурных фракталов. Примеры геометрических
фракталов приведены на рисунке 2.
7
а) б)
Рис. 2. Примеры геометрических фракталов. а) Кривая Коха, б) Кривая «Дракона»
2.Алгебраические фракталы
Это самая крупная группа фракталов. В классификации Морозова
фракталы этой группы соответствуют динамическим фракталам. Получают
их с помощью нелинейных процессов в n-мерных пространствах. Наиболее
изучены двухмерные процессы. Интерпретируя нелинейный итерационный
процесс, как дискретную динамическую систему, можно пользоваться
терминологией теории этих систем: фазовый портрет, установившийся
процесс, аттрактор и т.д. Некоторые распространенные алгебраические
фракталы присутствуют на рисунке 3.
а) б)
Рис. 3. Примеры алгебраических фракталов. а) Фрактал Жюлиа, б) Множество Мандельброта
3.Стохастические фракталы
Еще одним известным классом фракталов являются стохастические
фракталы, которые получаются в том случае, если в итерационном процессе
8
хаотически менять какие-либо его параметры. При этом получаются объекты
очень похожие на природные - несимметричные деревья, изрезанные
береговые линии и т.д. Двумерные стохастические фракталы используются
при моделировании рельефа местности и поверхности моря.
Существуют и другие классификации фракталов, например, деление
фракталов на детерминированные (алгебраические и геометрические) и
недетерминированные (стохастические) [8].
Изучение классификации фракталов показывает, что разные типы
фракталов строятся при помощи различных математических и программных
процедур. Рассмотрим кратко суть некоторых итерационных алгоритмов в
терминах языка Pascal, предложенных авторами Интернет-проекта
«Фракталы и теория бифуркации» [8].
1. Метод последовательных приближений, или детерминистический.
Пусть имеется некоторая IFS-система, т.е. система сжимающих
отображений S={S1,...,Sm} Si:Rn->Rn (например, для пирамиды
Серпинского, являющейся трехмерной моделью фрактального треугольника
Серпинского (рис. 4), отображения имеют вид Si(x)=1/2*x+oi, где oi -
вершины тетраэдра, i=1,..,4). Затем выбираем
некоторое компактное множество A1 в Rn (в
нашем случае выбираем тетраэдр). И
определяем по индукции последовательность
множеств Ak:Ak+1=S1(Ak) U...U Sm(Ak).
Известно, что множества Ak с ростом k, всё
лучше приближают искомый аттрактор
системы S.
Рис. 4. Пирамида Серпинского Каждая из этих итераций является аттрактором
рекуррентной системы итерированных функций (английский термин Digraph
IFS, RIFS и также Graph-directed IFS) и поэтому их легко построить с
помощью нашей программы. Использование данного метода для сжатия
изображений будет рассмотрено во 2 главе.
9
2. Построение по точкам, или вероятностный метод.
Это наиболее лёгкий для реализации на компьютере метод. Для
простоты рассмотрим случай плоского самоаффинного множества. Итак,
пусть {S1,..,Sm} - некоторая система аффинных сжатий. Отображения Si
представимые в виде: Si(x)=Ai( x-oi )+oi, где Ai - фиксированная матрица
размера 2x2 и oi - двумерный вектор столбец.
Возьмем неподвижную точку первого отображения S1 в качестве
начальной точки:
x := o1;
Здесь мы пользуемся тем, что все неподвижные точки сжатий S1,..,Sm
принадлежат фракталу. В качестве начальной точки можно выбрать
произвольную точку и порожденная ею последовательность точек стянется к
фракталу, но тогда на экране появятся несколько лишних точек.
Отметим текущую точку x=(x1,x2) на экране:
putpixel(x1,x2,15);
Выберем случайным образом число j от 1 до m и пересчитаем
координаты точки x:
j:=Random(m)+1;
x:=Sj(x);
Переходим на шаг 2, либо, если сделали достаточно большое число
итераций, то останавливаемся.
Следует отметить, что если коэффициенты сжатия отображений Si
разные, то фрактал будет заполняться точками неравномерно. В случае, если
отображения Si являются подобиями, этого можно избежать небольшим
усложнением алгоритма. Для этого на 3-ем шаге алгоритма число j от 1 до m
надо выбирать с вероятностями p1=r1s,..,pm=rms, где ri обозначают
коэффициенты сжатия отображений Si, а число s (называемое размерностью
подобия) находится из уравнения r1s+...+rms=1. Решение этого уравнения
можно найти, например, методом Ньютона.
10