19. Системы итерируемых функций

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

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

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

Рис. 4.1. Построение ковра Серпинского с помощью детерминорованной СИФ

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

и преобразование компактного множества записывается в виде

После выполнения таких преобразований, получаем изображение соответствующее ковру Серпинского:

Заметим, что все множество возможных построений определяется набором аффинных преобразований ,…, .

Обычно коэффициенты аффинного преобразования записываются в матрицу размером элементов:

которая полностью описывает фрактальное множество.

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

- начальная точка (с произвольными координатами)

или или

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

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

Для равномерного распределения точек по экрану в рандомизированном алгоритме аффинные преобразования следует выбирать с вероятностью

где - матрица соответствующего аффинного преобразования. Очевидно, что .

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

- с коэффициентом сжатия ,

- с коэффициентом сжатия .

Эти отображений используются для построения одного сжимающего отображения .

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

- компактное множество (произвольное)

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

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

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

<< Предыдущая

Оглавление

Следующая >>