Глава 4. Системы итерированных функций

Мы обратимся теперь к одному из наиболее замечательных и глубоких достижений в построении фракталов — системам итерированных функций. Математические аспекты были разработаны Джоном Хатчинсоном [23], а сам метод стал широко известен благодаря Майклу Барнсли [4] и другим. Подход на основе систем итерированных функций предоставляет хорошую теоретическую базу для математического исследования многих классических фракталов, а также их обобщений. Разработанная теория будет непосредственно использована при переходе к исследованию хаоса, связанного с фракталами (глава 7).

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

4.1. Системы итерированных функций

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

Рис. 4.1. Ковер Серпинского: детерминированный алгоритм (уровни 0, 1, 2, 3, 4, 5)

В п. 3.4 для построения использовались следующие три аффинных преобразования (рис. 3.8):

Если S — замкнутое множество в виде треугольника с вершинами (0,0), (1,0) и , то образы суть три меньшие треугольные области, изображенные на рисунке справа.

В детерминированном алгоритме рассматривают следующую последовательность множеств:

Рис. 4.2. Ковер Серпинского: рандомизированный алгоритм (построено 10000 точек)

Если в качестве выбрать замкнутую треугольную область S, то множества построенные указанным способом, будут в точности те же, что и при выкидывании центральных треугольных частей.

В рандомизированном алгоритме, который часто называют игрой «Хаос» (см. упр. 1 в конце параграфа), в качестве начального множества выбирают одну точку:

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

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

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

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

действующих на . Эти отображений используются для построения одного сжимающего отображения Т в пространстве К, всех непустых компактов из Преобразование Хатчинсона , определяется следующим образом:

Это преобразование ставит в соответствие «точкам» из К, также «точки» из причем под точками здесь понимаются компактные множества.

Таким образом, системой итерированных функций (СИФ) называют совокупность введенных выше отображений вместе с итерационной схемой:

Основная задача теории СИФ — выяснить, когда СИФ порождает предельное множество Е:

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

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

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

Теорема 4.1.1. Преобразование Т, определенное формулой (4-1), является сжимающим отображением на К. с хаусдорфовой метрикой. Его коэффициент сжатия равен:

Доказательство. Я благодарен Ричарду Найдингеру за предложенное доказательство. Во-первых, заметим, что для любого компакта F выполняется тогда и только тогда, когда существует такой элемент , что Следовательно, если , то для каждого отображения Г. По определению, неравенство эквивалентно следующей записи на языке множеств: . Положим . Тогда, если , то:

Следовательно,

Если поменять местами А я В, получим:

Таким образом,

Следующая теорема суммирует основные результаты о сходимости систем итерированных функций.

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

где Т — преобразование Хатчинсона (4-1), сходится в метрике Хаусдорфа к единственному множеству . Множество Е называют аттрактором СИФ. Обратно, множество Е можно представить в виде:

Вопрос о сходимости рандомизированного алгоритма для системы итерированных функций рассматривается в п. 7.6.