Информатика программирование : Статья: Красота повтора
Статья: Красота повтора
Евгений
Епифанов
Фракталы известны уже почти век, хорошо
изучены и имеют многочисленные приложения в жизни. Однако в основе этого явления
лежит очень простая идея: бесконечное по красоте и разнообразию множество фигур
можно получить из относительно простых конструкций при помощи всего двух
операций - копирования и масштабирования
Что общего у дерева, берега моря, облака
или кровеносных сосудов у нас в руке? На первый взгляд может показаться, что
все эти объекты ничто не объединяет. Однако на самом деле существует одно
свойство структуры, присущее всем перечисленным предметам: они самоподобны. От
ветки, как и от ствола дерева, отходят отростки поменьше, от них - еще меньшие,
и т.д., то есть ветка подобна всему дереву. Подобным же образом устроена и
кровеносная система: от артерий отходят артериолы, а от них - мельчайшие
капилляры, по которым кислород поступает в органы и ткани. Посмотрим на
космические снимки морского побережья: мы увидим заливы и полуострова; взглянем
на него же, но с высоты птичьего полета: нам будут видны бухты и мысы; теперь
представим себе, что мы стоим на пляже и смотрим себе под ноги: всегда найдутся
камешки, которые дальше выдаются в воду, чем остальные. То есть береговая линия
при увеличении масштаба остается похожей на саму себя. Это свойство объектов
американский (правда, выросший во Франции) математик Бенуа Мандельброт назвал
фрактальностью, а сами такие объекты - фракталами (от латинского fractus -
изломанный).
ГЕОМЕТРИЯ И АЛГЕБРА
Изучение фракталов на рубеже XIX и XX
веков носило скорее эпизодический, нежели систематический характер, потому что
раньше математики в основном изучали "хорошие" объекты, которые поддавались
исследованию при помощи общих методов и теорий. В 1872 году немецкий математик
Карл Вейерштрасс строит пример непрерывной функции, которая нигде не
дифференцируема. Однако его построение было целиком абстрактно и трудно для
восприятия. Поэтому в 1904 году швед Хельге фон Кох придумал непрерывную
кривую, которая нигде не имеет касательной, причем ее довольно просто
нарисовать. Оказалось, что она обладает свойствами фрактала. Один из вариантов
этой кривой носит название "снежинка Коха".
Идеи самоподобия фигур подхватил француз
Поль Пьер Леви, будущий наставник Бенуа Мандельброта. В 1938 году вышла его
статья "Плоские и пространственные кривые и поверхности, состоящие из
частей, подобных целому", в которой описан еще один фрактал -С-кривая
Леви. Все эти вышеперечисленные фракталы можно условно отнести к одному классу
конструктивных (геометрических) фракталов.
Другой класс - динамические
(алгебраические) фракталы, к которым относится и множество Мандельброта. Первые
исследования в этом направлении начались в начале XX века и связаны с именами
французских математиков Гастона Жулиа и Пьера Фату. В 1918 году вышел почти
двухсотстраничный мемуар Жулиа, посвященный итерациям комплексных рациональных
функций, в котором описаны множества Жулиа - целое семейство фракталов, близко
связанных с множеством Мандельброта. Этот труд был удостоен приза Французской
академии, однако в нем не содержалось ни одной иллюстрации, так что оценить
красоту открытых объектов было невозможно. Несмотря на то что это работа
прославила Жулиа среди математиков того времени, о ней довольно быстро забыли.
Вновь внимание к ней обратилось лишь полвека спустя с появлением компьютеров:
именно они сделали видимыми богатство и красоту мира фракталов.
ЧТО ТАКОЕ ФРАКТАЛ?
У этого понятия нет строгого определения.
Поэтому слово "фрактал" не является математическим термином. Обычно
так называют геометрическую фигуру, которая удовлетворяет одному или нескольким
из следующих свойств:
• обладает сложной структурой при любом
увеличении;
• является (приближенно) самоподобной;
• обладает дробной хаусдорфовой
(фрактальной) размерностью, которая больше топологической;
• может быть построена рекурсивными
процедурами.
НАУКА И ИСКУССТВО
В 1982 году вышла книга Мандельброта
"Фрактальная геометрия природы", в которой автор собрал и
систематизировал практически всю имевшуюся на тот момент информацию о фракталах
и в легкой и доступной манере изложил ее. Основной упор в своем изложении
Мандельброт сделал не на тяжеловесные формулы и математические конструкции, а
на геометрическую интуицию читателей. Благодаря иллюстрациям, полученным при
помощи компьютера, и историческим байкам, которыми автор умело разбавил научную
составляющую монографии, книга стала бестселлером, а фракталы стали известны
широкой публике. Их успех среди нематематиков во многом обусловлен тем, что с
помощью весьма простых конструкций и формул, которые способен понять и
старшеклассник, получаются удивительные по сложности и красоте изображения.
Когда персональные компьютеры стали достаточно мощными то появилось даже целое
направление в искусстве – фрактальная живопись, причем заниматься ею мог
практически любой владелец компьютера. Сейчас в интернете можно легко найти
множество сайтов, посвященных этой теме.
ВОЙНА И МИР
Как уже отмечалось выше, один из
природных объектов, имеющих фрактальные свойства, – это береговая линия. С ним,
а точнее, с попыткой измерить его длину, связана одна интересная история,
которая легла в основу научной статьи Мандельброта, а также описана в его книге
"Фрактальная геометрия природы". Речь идет об эксперименте, который
поставил Льюис Ричардсон – весьма талантливый и эксцентричный математик, физик
и метеоролог. Одним из направлений его исследований была попытка найти
математическое описание причин и вероятности возникновения вооруженного
конфликта между двумя странами. В числе параметров, которые он учитывал, была
протяженность общей границы двух враждующих стран. Когда он собирал данные для
численных экспериментов, то обнаружил, что в разных источниках данные об общей
границе Испании и Португалии сильно отличаются. Это натолкнуло его на следующее
открытие: длина границ страны зависит от линейки, которой мы их измеряем. Чем
меньше масштаб, тем длиннее получается граница. Это происходит из-за того, что
при большем увеличении становится возможным учитывать все новые и новые изгибы
берега, которые раньше игнорировались из-за грубости измерений. И если при
каждом увеличении масштаба будут открываться ранее не учтенные изгибы линий, то
получится, что длина границ бесконечна! Правда, на самом деле этого не
происходит – у точности наших измерений есть конечный предел. Этот парадокс
называется эффектом Ричардсона.
КОНСТРУКТИВНЫЕ (ГЕОМЕТРИЧЕСКИЕ) ФРАКТАЛЫ
Алгоритм построения конструктивного
фрактала в общем случае таков. Прежде всего нам нужны две подходящие
геометрические фигуры, назовем их основой и фрагментом. На первом этапе
изображается основа будущего фрактала. Затем некоторые ее части заменяются
фрагментом, взятым в подходящем масштабе, – это первая итерация построения.
Затем у полученной фигуры снова некоторые части меняются на фигуры, подобные
фрагменту, и т.д. Если продолжить этот процесс до бесконечности, то в пределе
получится фрактал.
Рассмотрим этот процесс на примере кривой
Коха (см. врезку на предыдущей странице). За основу кривой Коха можно взять
любую кривую (для "снежинки Коха" это треугольник). Но мы ограничимся
простейшим случаем – отрезком. Фрагмент – ломаная, изображенная сверху на
рисунке. После первой итерации алгоритма в данном случае исходный отрезок совпадет
с фрагментом, затем каждый из составляющих его отрезков сам заменится на
ломаную, подобную фрагменту, и т.д. На рисунке показаны первые четыре шага
этого процесса.
ЯЗЫКОМ МАТЕМАТИКИ: ДИНАМИЧЕСКИЕ
(АЛГЕБРАИЧЕСКИЕ) ФРАКТАЛЫ
Фракталы этого типа возникают при исследовании
нелинейных динамических систем (отсюда и название). Поведение такой системы
можно описать комплексной нелинейной функцией (многочленом) f(z). Возьмем
какую-нибудь начальную точку z0 на комплексной плоскости (см. врезку). Теперь
рассмотрим такую бесконечную последовательность чисел на комплексной плоскости,
каждое следующее из которых получается из предыдущего: z0, z1=f(z0), z2=f(z1),
... zn+1=f(zn). В зависимости от начальной точки z0 такая последовательность
может вести себя по-разному: стремиться к бесконечности при n→∞;
сходиться к какой-то конечной точке; циклически принимать ряд фиксированных
значений; возможны и более сложные варианты.
Таким образом, любая точка z комплексной
плоскости имеет свой характер поведения при итерациях функции f(z), а вся
плоскость делится на части. При этом точки, лежащие на границах этих частей,
обладают таким свойством: при сколь угодно малом смещении характер их поведения
резко меняется (такие точки называют точками бифуркации). Так вот, оказывается,
что множества точек, имеющих один конкретный тип поведения, а также множества
бифуркационных точек часто имеют фрактальные свойства. Это и есть множества
Жулиа для функции f(z).
Множество Мандельброта строится несколько
иначе. Рассмотрим функцию fc(z) = z2+с, где c – комплексное число. Построим
последовательность этой функции с z0=0, в зависимости от параметра с она может
расходиться к бесконечности или оставаться ограниченной. При этом все значения
с, при которых эта последовательность ограничена, как раз и образуют множество
Мандельброта. Оно было детально изучено самим Мандельбротом и другими
математиками, которые открыли немало интересных свойств этого множества.
Видно, что определения множеств Жулиа и
Мандельброта похожи друг на друга. На самом деле эти два множества тесно
связаны. А именно, множество Мандельброта - это все значения комплексного
параметра с, при которых множество Жулиа fc(z) связно (множество называется
связным, если его нельзя разбить на две непересекающиеся части, с некоторыми
дополнительными условиями).
ФРАКТАЛЫ И ЖИЗНЬ
В наши дни теория фракталов находит
широкое применение в различных областях человеческой деятельности. Помимо чисто
научного объекта для исследований и уже упоминавшейся фрактальной живописи,
фракталы используются в теории информации для сжатия графических данных (здесь
в основном применяется свойство самоподобия фракталов - ведь чтобы запомнить
небольшой фрагмент рисунка и преобразования, с помощью которых можно получить
остальные части, требуется гораздо меньше памяти, чем для хранения всего
файла). Добавляя в формулы, задающие фрактал, случайные возмущения, можно
получить стохастические фракталы, которые весьма правдоподобно передают
некоторые реальные объекты - элементы рельефа, поверхность водоемов, некоторые
растения, что с успехом применяется в физике, географии и компьютерной графике
для достижения большего сходства моделируемых предметов с настоящими. В
радиоэлектронике в последнее десятилетие начали выпускать антенны, имеющие
фрактальную форму. Занимая мало места, они обеспечивают вполне качественный
прием сигнала. Экономисты используют фракталы для описания кривых колебания
курсов валют (это свойство было открыто Мандельбротом более 30 лет назад). На
этом мы завершим эту небольшую экскурсию в удивительный по красоте и разнообразию
мир фракталов.
ФРАКТАЛЬНЫЕ РАЗМЕРНОСТИ
Как известно, размерность (число
измерений) геометрической фигуры - это число координат, необходимых для
определения положения лежащей на этой фигуре точки
Например, положение точки на кривой
определяется одной координатой, на поверхности (не обязательно плоскости) -
двумя координатами, в трехмерном пространстве - тремя координатами.
С БОЛЕЕ ОБЩЕЙ МАТЕМАТИЧЕСКОЙ ТОЧКИ ЗРЕНИЯ
МОЖНО ОПРЕДЕЛИТЬ РАЗМЕРНОСТЬ ТАКИМ ОБРАЗОМ: увеличение линейных размеров,
скажем, в два раза для одномерных с топологической точки зрения) объектов
(отрезок) приводит к увеличению размера (длины) в два раза, для двухмерных
(квадрат) такое же увеличение линейных размеров приводит к увеличению размера
(площади) в четыре раза, для трехмерных (куб) - в восемь раз.
"Реальную" (т.н. Хаусдорфову) размерность можно подсчитать в виде
отношения логарифма объекта к логарифму увеличения его линейного размера. То
есть для отрезка D=log(2)/log(2)=l, для плоскости D=log(4)/ log(2)=2, для
объема D=log(8)/log(2)=3. Подсчитаем теперь размерность кривой Коха, для
построения которой единичный отрезок делят на три равные части и заменяют
средний интервал равносторонним треугольником без этого сегмента. При
увеличении линейных размеров минимального отрезка в три раза длина кривой Коха
возрастает в log(4)/log(3)~l,26. То есть размерность кривой Коха - дробная!
СНЕЖИНКА КОХА
Вверху - схема получения кривой Коха;
внизу - одна из разновидностей этой кривой, снежинка Коха
Комплексные числа
Комплексное число - это число, состоящее
из двух частей, действительной и мнимой, то есть формальная сумма х + iy (х и у
здесь - вещественные числа, i - так называемая мнимая единица, число,
удовлетворяющее уравнению i2 = -1). Над комплексными числами определены
основные математические операции - сложение, умножение, деление, вычитание Сне
определена только операция сравнения). Для изображения комплексных чисел часто
используется геометрическое представление - на плоскости (ее называют
комплексной) по оси абсцисс откладывают действительную часть, а по оси ординат
- мнимую, при этом комплексному числу будет соответствовать точка с декартовыми
координатами х и у.
Семейство драконов
Варьируя основу и фрагмент, можно
получить потрясающее разнообразие конструктивных фракталов
Более того, подобные операции можно
производить и в трехмерном пространстве. Примерами объемных фракталов могут
служить "губка Менгера", "пирамида Серпинского" и другие.
К КОНСТРУКТИВНЫМ ФРАКТАЛАМ ОТНОСЯТ И
СЕМЕЙСТВО ДРАКОНОВ. Иногда их называют по имени первооткрывателей драконами
Хейвея-Хартера (своей формой они напоминают китайских драконов). Существует
несколько способов построения этой кривой. Вот самый простой и наглядный: нужно
взять достаточно длинную полоску бумаги (чем тоньше бумага, тем лучше) и
согнуть ее пополам. Затем снова согнуть ее вдвое в том же направлении, что и в
первый раз. После нескольких повторений (обычно через пять-шесть складываний
полоска становится слишком толстой, чтобы ее можно было аккуратно гнуть дальше)
нужно разогнуть полоску обратно, причем стараться, чтобы в местах сгибов
образовались углы в 90°. Тогда в профиль получится кривая дракона. Разумеется,
это будет лишь приближение, как и все наши попытки изобразить фрактальные
объекты. Компьютер позволяет произвести гораздо больше шагов этого процесса, и
в результате получается очень красивая фигура.
ПО ОБРАЗУ И ПОДОБИЮ
Эти фракталы получили свое имя за
сходство с китайскими драконами. Не правда ли, похоже?
МНОЖЕСТВА МАНДЕЛЬБРОТА
На этом развороте вы видите фрактал,
изображающий множество Мандельброта - то есть множество точек c на комплексной
плоскости, для которых последовательность zn, определяемая итерациями z0=0,
z1=z02+с, ... zn+1=zn2+c, конечна (то есть не уходит в бесконечность).
Визуально множество Мандельброта выглядит как набор бесконечного количества
различных фигур, самая большая из которых называется кардиоидой (она похожа на
стилизованное изображение сердца и получила свое название от двух греческих
слов - "сердце" и "вид"). Кардиоида окружена все
уменьшающимися кругами, каждый из которых окружен еще меньшими кругами, и т.д.
до бесконечности. При любом увеличении этого фрактала будут выявляться все
более и более мелкие детали изображения, дополнительные ветки с более мелкими
кардиоидами, кругами. И этот процесс можно продолжать бесконечно.
СБЕЖАВШИЕ ЧИСЛА
Для построения графического изображения
множества Мандельброта можно использовать алгоритм, называемый escape-time.
Суть его такова. Доказано, что все множество целиком расположено внутри круга
радиуса 2 на плоскости. Поэтому будем считать, что если для точки c
последовательность итераций функции f (0) после некоторого большого их числа N
(скажем, 100) не вышла за пределы этого круга, то точка принадлежит множеству и
красится в черный цвет. Соответственно, если на каком-то этапе, меньшем N,
элемент последовательности по модулю стал больше 2, то точка множеству не
принадлежит и остается белой. Таким образом, можно получить черно-белое
изображение множества, которое и было получено Мандельбротом. Чтобы сделать его
цветным, можно, например, каждую точку не из множества красить в цвет,
соответствующий номеру итерации, на котором ее последовательность вышла за
пределы круга.
ФРАКТАЛЫ НЬЮТОНА (СЛЕВА)
Еще один тип динамических фракталов
составляют фракталы (так называемые бассейны) Ньютона. Формулы для их
построения основаны на методе решения нелинейных уравнений, который был
придуман великим математиком еще в XVII веке. Применяя общую формулу метода
Ньютона z , = z - f(z )/f'(z ),
n+1 n=0, 1, 2... для решения уравнения
f(x)=0 к многочлену zk-a, получим последовательность точек: z 1 = (k-1)z k/kz
k-1, n=0, 1, 2.. Выбирая в качестве начальных приближений различные комплексные
числа z0, будем получать последовательности, которые сходятся к корням этого
многочлена. Поскольку корней у него ровно k, то вся плоскость разбивается на k
частей - областей притяжения корней. Границы этих частей имеют фрактальную
структуру. (Заметим в скобках, что если в последней формуле подставить k=2, а в
качестве начального приближения взять z0=a, то получится формула, которую
реально используют для вычисления корня квадратного из a в компьютерах.)
МНОЖЕСТВА ЖУЛИА
Любая точка z комплексной плоскости имеет
свой характер поведения (остается конечной, стремится к бесконечности,
принимает фиксированные значения) при итерациях функции f(z), а вся плоскость
делится на части. При этом точки, лежащие на границах этих частей, обладают
таким свойством: при сколь угодно малом смещении характер их поведения резко
меняется (такие точки называют точками бифуркации). При этом множества точек,
имеющих один конкретный тип поведения, а также множества бифуркационных точек
часто имеют фрактальные свойства. Это и есть множества Жулиа для функции f(z).
На рисунке изображены множества Жулиа для функции f(z)=z2-(0,12+0,76i).
Список литературы
Популярная механика № 3 (77)март 2009
|