Фракталы и хаос.

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

Хорошо проиллюстрировать хаотичное поведение можно с помощью так называемого logistic equation x=c*x(1-x). Пришло это выражение из биологии, т.к. это грубая модель популяции животных. Так вот при исследовании поведения этой функции выяснилась интересная ее особенность. Если с - фактор роста популяции находится в пределах от 1 до 3, то через некоторое количество итераций популяция стабилизируется.

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

При с=3.45 она раздваивается снова и у нас уже имеется четырехлетний цикл.

Далее при росте с функция раздваивается все быстрее и быстрее: при с=3.54, с=3.564, с=3.569...

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

Ну и на закуску интересный пример. Вы ведь доверяете своему компьютеру? Я имею в виду вы считаете, что он очень точная и быстрая машина. Тогда запустите Microsoft Excel. Введите в ячейки А1 и B1 значение 4. В ячейки A2 и B2 одинаковые значения между 0 и 1. В ячейку A3 введите формулу "=$A$1*A2*(1-A2)", а в ячейку B3 введем ту же формулу, только раскроем скобки "=$B$1*(B2-B2*B2)", а в ячейку С3 поместим формулу разности "=A3-B3". Как и следовало ожидать результаты в ячейках A3 и B3, а разница равна 0. Теперь выделяем диапазон A3:C3 и копируем его в нижние 100 строк и смотрим что у нас происходит. Начиная с 5-7 строки мы видим, что появилась небольшая разница в результате 2 формул. Эта разница довольно быстро возрастает и на 50 шагу эта разница уже по величине равна нашим числам. Более того разные процессоры будут давать разные результаты. Возникает закономерный вопрос: какое же значение верно? Правильный ответ: "Никакое!". Начиная с определенного места ВСЕ современные компьютеры дают неверный результат. Вот такой простой задачкой мы поставили нашего "мистера-точность" в тупик:(.

Еще раз вспомните про прогноз погоды и самолеты. А ведь это только цветочки...

Вот и подошла к концу наша экскурсия в мир фракталов. Надеюсь она Вам понравилась. Я только немного приоткрыл Вам завесу в мир фракталов.

Если хотите изучить фракталы поподробнее зайдите на страничку http://www.eclectasy.com/fractovia/. Вы найдете там десятки программ рисования фракталов, некоторые с хорошими объяснениями.

Если Вы неплохо знаете английский, то лучше документации, чем та которая распространяется с программой Fractint не найти.

Вопросы можете задавать лично по адресу mailto:[e-mail]

На рисунках — кривые Гильберта порядка с 4 по 7. Каждая кривая — как будто нитка, аккуратно уложенная в единичном квадрате, то есть квадрате со стороной, равной единице.

Как «устроены» эти кривые, и чем замечательны?

Сначала разберемся, как построить такую кривую. Возьмем квадрат со стороной ½, уберем одну из его сторон, и поместим его точно в середину единичного квадрата, вот так:

Получилась Гильбертова кривая порядка 1. Теперь уменьшим ее ровно вдвое, и сделаем с нее 4 копии. Две передвинем, а две другие тоже передвинем и еще повернем на четверть оборота в противоположные стороны. Соединим концы линий тремя одинаковыми отрезками, длиной равной стороне нового, уменьшенного квадрата. На рисунке каждая копия окрашена своим цветом, а соединительные отрезки черные.

У нас получилась кривая порядка 2. Теперь повторим нашу процедуру, но уже с получившейся ломаной линией: уменьшим вдвое, сделаем четыре копии, две из которых повернуты, и вновь соединим отрезками, которые тоже укоротим вдвое:

Повторять этот алгоритм можно до бесконечности. Вот следующие четыре шага, с кривыми порядка от 4 до 7 включительно:

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

Разумеется, повторить алгоритм бесконечное число раз нельзя; говоря о бесконечностях, следует оперировать пределами, ε-окрестностями и прочими понятиями матанализа.

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

Возьмем кусочек бесконечно растяжимой резинки и нанесем на нее шкалу от 0 до 1. Разные участки резинки могут быть растянуты по-разному. Натянем ее по форме кривой первого порядка так, что концы будут соответствовать 0 и 1, а середины каждой из трех сторон — 1/4, 2/4 и 3/4 соответственно. Теперь возьмем еще одну такую же резинку, и растянем ее вдоль кривой второго порядка. Концы кривой опять прикрепим в точках 0 и 1, а к серединам каждого из 15 отрезков, составляющих кривую, прикрепим точки начиная с 1/16 и заканчивая 15/16. Легко видеть, что расстояние между соответствующими одному и тому же числу точках на двух резинках не превышает диагонали квадрата со стороной, равной длине каждого из отрезков кривой второго порядка.

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

По теореме Коши, поскольку разница между любыми двумя функциями стремится к нулю (транзитивность тут доказывается разложением в геометрический ряд, см. [3]), то и предельная функция существует и непрерывна. Интуитивно это понятно из рисунка: с каждой итерацией расстояние между кривыми порядка n +1 и n, первой «обвивающей» последнюю, делается все меньше и меньше.

Далее следует доказать, что кривая проходит через любую точку квадрата. Рассуждение здесь такое. Кривая порядка 1 проходит на расстоянии не далее 1/4 от любой точки внутри квадрата. Поэтому любая из четырех ее уменьшенных копий в кривой второго порядка оказывается не далее 1/8 от любой точки каждой из четырех четвертей квадрата, а, значит, любая точка всего квадрата удалена от кривой не более, чем на 1/8. Кривая третьего порядка лежит не далее, чем в 1/16 от любой точки в квадрате, и так далее. Таким образом, в предельном случае кривая будет проходить в ε-окрестности любой точки внутри квадрата. Тогда для некоей последовательности аргументов функции, последовательность соответствующих значений непременно сойдется в данную точку; иными словами, кривая проходит через все точки квадрата. Строго можно доказать, что кривая не только проходит через все точки квадрата, но и «не влезает» в квадрат — через почти все некоторые точки она проходит более одного раза! (Это следует, например, из неизоморфности отрезка [0;1] единичному квадрату: на отрезке удаление почти любой точки рассекает его на два несвязных подмножества, а в квадрате такой точки нет) [Возможно, это ошибка. Ссылка в обсуждение — прочитайте!].

Интересен вопрос, можно ли говорить о фрактальности этой кривой. С одной стороны, кривая, безусловно, самоподобна, за исключением соединительных отрезков, в силу построения. С другой стороны, под Мандельбротово определение фрактала она не попадает[4]: поскольку кривая заполняет весь квадрат, то ее Хаусдорфова размерность совпадает с топологической, и равна 2. Так что ответ зависит от решения о том, что следует считать фракталом. В некотором смысле, кривая Гильберта находится на границе между фрактальными и не фрактальными объектами.

Алгоритмически Гильбертова кривая удобно строится с помощью переписывающей символьной системы Линденмайера (L-System) [5], конечный результат преобразования в которой интерпретируется как «черепашья» графика[6]. Если интересно, то об этом можно будет поговорить отдельно. А здесь пока приведу только код для Mathematica 6.0, с помощью которого были построены все иллюстрации:

LIterate[omega_, rules_, n_]:= Nest[StringReplace[#, rules]&, omega, n]; QuadPart[list_]:= With[{m = Length[list]/4}, Flatten[ Partition[#, m, m-1, {1,2}, {}]& /@ Partition[list, m+1, m, {1,m}, {}], 1] /; IntegerQ[m] && m > 1]; HilbertCurve[r_, s_]:= Module[{ omega = "L", rules = {"L" -> "+RF-LFL-FR+", "R" -> "-LF+RFR+FL-"}, colority = 0.8, ttl, pts}, ttl[{p_, d_}, "F"]:= {p + d, d}; ttl[{p_, d_}, "+"]:= {p, I*d}; ttl[{p_, d_}, "-"]:= {p, -I*d}; ttl[pd_, _]:= pd; pts = 2^(s-r) * {Re[#], Im[#]}& /@ First /@ Split[ First /@ FoldList[ttl, {0,1}, Characters @ LIterate["L", rules, r]]]; Graphics[Style[{ Thickness[1.5^(-r-8)], If[r > 1, MapThread[ {#1, Line @ #2} &, { Riffle[Hue[#, 1, colority]& /@ (0.25 * Range[0, 3]), Black], QuadPart[pts]}], Line[pts]]}, Antialiasing -> False], { ImageSize -> 2^s * {1,1}, ImagePadding -> None, PlotRangePadding -> 2^(s-r-1) * {1,1} }] ]; Table[HilbertCurve[i, 8], {i, 1, 7}]

Полезная литература

1. M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman and Co.: NY, 1989.

2. E. W. Weisstein. Plane-Filling Function in MathWorld—A Wolfram Web Resource.

3. A. Bogomolny, Plane Filling Curves in Interactive Mathematics Miscellany and Puzzles.

4. B. Mandelbrot. The Fractal Geometry of Nature, W. H. Freeman and Co.: NY, 1982. Русское изд.: Б. Мандельброт. Фрактальная геометрия природы. Институт компьютерных исследований: M., 2002.

5. L-system in Wikipedia.

6. Web Turtle by Bill Kendrick.

Дата добавления: 2015-07-11