Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
Глава 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 точек) Если в качестве В рандомизированном алгоритме, который часто называют игрой «Хаос» (см. упр. 1 в конце параграфа), в качестве начального множества выбирают одну точку:
На каждом шаге, вместо того чтобы применять сразу три преобразования Замечательным свойством алгоритмов, основанных на теории систем итерированных функций, является то, что их результат (аттрактор) совершенно не зависит от выбора начального множества Рандомизированный алгоритм часто используется на компьютерах, в которых предусмотрена возможность вывода графического изображения на экран в режиме 1 пиксел за раз. Для детерминированного алгоритма требуется большой объем памяти. Стоит отметить, что для вывода на печать необходим принтер, способный работать с большими изображениями. В общем случае, для чтобы построить систему итерированных функций введем в рассмотрение совокупность сжимающих отображений:
действующих на
Это преобразование ставит в соответствие «точкам» из К, также «точки» из Таким образом, системой итерированных функций (СИФ) называют совокупность введенных выше отображений вместе с итерационной схемой:
Основная задача теории СИФ — выяснить, когда СИФ порождает предельное множество Е:
в смысле сходимости в метрике Хаусдорфа. Если предел существует, то множество Е называют аттрактором системы итерированных функций. Причем аттрактор часто (но не всегда!) оказывается фрактальным множеством. Очевидно, для того чтобы обеспечить сходимость, требуется наложить определенные ограничения на введенные выше преобразования, к примеру запретить точкам уходить на бесконечность. Основные математические идеи, необходимые для установления условий сходимости, уже были представлены. Если нам удастся показать, что Т является сжимающим отображением на метрическом пространстве Таким образом, необходимо показать, что метрическое пространство Теорема 4.1.1. Преобразование Т, определенное формулой (4-1), является сжимающим отображением на К. с хаусдорфовой метрикой. Его коэффициент сжатия равен:
Доказательство. Я благодарен Ричарду Найдингеру за предложенное доказательство. Во-первых, заметим, что для любого компакта F выполняется
Следовательно,
Если поменять местами А я В, получим:
Таким образом,
Следующая теорема суммирует основные результаты о сходимости систем итерированных функций. Теорема 4.1.2. Пусть
где Т — преобразование Хатчинсона (4-1), сходится в метрике Хаусдорфа к единственному множеству
Вопрос о сходимости рандомизированного алгоритма для системы итерированных функций рассматривается в п. 7.6.
|
1 |
Оглавление
|