Kranover R M - Fraktaly i khaos v din sist
.pdf3.5 Аффинные преобразования • 9 1
Доказать, что любое аффинное преобразование плоскости можно записать в следующей комплексной форме:
L(z) = az + bz + с,
где а, Ьи с — комплексные числа. Указание: представить L(z) в виде линейной комбинации L(\) и L(i).
а) Доказать, что вращение, отражение и сдвиг в R2 являются изометриями.
б) Доказать, что любую изометрию на плоскости можно представить в виде:
Г(х) = Де х + Ь
или
Т(х) - ReRxx + Ь,
где Re — матрица вращения из упр. 2, a Rx — матрица отражения из упр. 3.
Пусть 5 задает преобразование подобия на R 2 с коэффициентом подобия г > 0. Показать, что S можно представить в виде:
5(х) = rRex + Ь
или
5(х) = rReRxx + Ь,
где Rff — матрица вращения из упр. 2, a Rx — матрица отражения из упр. 3.
Проверить формулу (3.21) для замены координат.
Найти преобразования, соответствующие отображениям, указанным на рис. 3.12. Каждое преобразование может состоять из сжатия, вращения и отражения. Записать ответ как в комплексной форме T{z) = az + bz + с, так и в матричной:
92 • Глава 3 / Множества и отображения
1 « 1 \f
начальное множество |
результат (а) |
|
\/ \f
результат (б) |
результат (в) |
Рис. 3.12.Отображения к упр. 8
3.5. Метрика Хаусдорфа I
Одним изосновных математических аспектов теории фракталов является вопрос о сходимости некоторой последовательности множеств к фракталу. К примеру, для того чтобы построить ковер Серпинского, мыначинаем с замкнутой треугольной области и, выкидывая на каждом шаге внутренние треугольники, получаем аппроксимирующие множества. Кажется вполне правдоподобным (см. рис. 2.5), что предельное множество в действительности является фракталом.
Наша первая задача — разобраться с понятием предела последовательности множеств. Дляэтого необходимо определить подходящую метрику на интересующих насмножествах. Метрика, которой мы будем пользоваться, называется метрикой Хаусдорфа.
Метрика Хаусдорфа определяется на множестве /Свсех непустых компактных подмножеств пространства Rn . Таким образом, «точки» К, суть компакты. «Точками» могут быть фигуры, изображенные на рис. 2.5, или даже само предельное множество (ковер
3.5 Метрика Хаусдорфа I • 93
Серпинского). Требование компактности не ограничивает применимости дальнейших результатов, так как в наших построениях мы всегда будем использовать только компактные множества; более того, оказывается, что и предельные множества — фракталы — всегда компактны.
Обозначим через Е и F два непустых компактных подмножества Rn . Хаусдорфово расстояние между Е и F можно задать несколькими способами. В этом параграфе мы придерживаемся интуитивного определения. Вопрос о том, является ли расстояние Хаусдорфа метрикой, вынесен в прил. А.З, в котором дается другое определение и доказывается, что расстояние Хаусдорфа действительно обладает всеми свойствами метрики. Там же доказывается эквивалентность двух определений.
Для произвольного множества Е из пространства R n и радиуса г > 0 дилатацией3 Е радиуса г (обозначается Е + г), называется векторная сумма Е +ВГ(О) (рис. 3.2). Здесь Вг(0) — замкнутый шар радиуса г с центром в начале координат. Формально:
Замечание: в некоторых источниках дилатация определяется с использованием открытого шара, в то время как мы используем замкнутый шар. Нашвыбор обусловлен тем, что в случае замкнутого шара доказательства теорем из прил. А.З несколько упрощаются.
Определение. Пусть Е и F — непустые компактные подмножества Rn . Расстояние Хаусдорфа между Е и F:
Н ( Е , F) = m i n { e >0: EcF + enFcE |
+ e}. |
(3.25) |
Пример. Пусть А и В — эллипсы (рис. 3.13):
2 |
2 |
^ - + V = 1 |
и 4(а;- 2)2 + j - 1, |
Видно, что наименьшее е, при котором А С В + е и В С А + е, составляет е = 3,5. Поэтому Н(А, В) = 3,5.
Доказательство следующей теоремы вынесено в прил. А.З.
В литературе часто используется эквивалентный термин расширение.
94 • Глава 3 / Множества и отображения
Рис. 3.13.Определение расстояния Хаусдорфа через дилатации
Теорема 3.5.8. Пусть Еп, п = 1,2,3,..., и Е — компактные множества. Для того чтобы limn-K» Е„ == Е в метрикеХаусдорфа, необходимо и достаточно, чтобы для каждого е нашелся такой номер N, что из п> N следует Еп С Е + е и Е С Еп + £•
Следствие 3.5.1. Пусть Еп, п = 1,2,3,... —последовательность компактных множеств, вложенных друг в друга:
Э Е2 D Е3 D • • •.
Введем
Е=()Еп.
п=\
Тогда Е — непустой компакт, и последовательностьмножеств Еп сходится к Е в хаусдорфовой метрике:
lim Еп = Е.
п о
3.5 Метрика Хаусдорфа I • 9 5
Это следствие непосредственно применимо к фракталам, при построении которых последовательно удаляются открытые подмножества. Примерами могут служить классическое множество Кантора (рис. 2.20) и ковер Серпинского (рис. 2.5). И в том, и в другом случае аппроксимирующие множества сходятся к соответствующим фракталам в метрике Хаусдорфа.
Упражнения 3.5.
1.Обозначим через 5 периметр квадрата с вершинами (0,0), (1,0), (1,1), (0,1). Построить дилатацию S +0,25.
2.Найти расстояние Хаусдорфа Н(А,В):
А = {(х,х) : - 1 <х< 1},
В= {(х,0) : - 1 < ж < 1}.
3.Пусть Со, С\, С2, ... — аппроксимирующие множества классического множества Кантора С (рис. 2.20).
а) Найти расстояние Хаусдорфа Н(Со,С). б) Найти расстояние Хаусдорфа Н(С\,С).
в) Найти расстояние Хаусдорфа Н(Сп,С), п = 2,3,...
4.Пусть С — классическое множество Кантора.
а) Построить дилатацию С + 1/27.
б) Сколько связных компонент образуют дилатацию С + 1/3"?
Глава 4.
Системы итерированных функций
Мы обратимся теперь к одному из наиболее замечательных и глубоких достижений в построении фракталов — системам итерированных функций. Математические аспекты были разработаны Джоном Хатчинсоном [23], а самметод стал широко известен благодаря Майклу Барнсли [4] и другим. Подход на основе систем итерированных функций предоставляет хорошую теоретическую базу для математического исследования многих классических фракталов, а также их обобщений. Разработанная теория будет непосредственно использована припереходе к исследованию хаоса, связанного с фракталами (глава 7).
Следует иметь в виду с самого начала, что результат применения системы итерированных функций, называемый аттрактором, не всегда является фракталом. Это может быть любой компакт, включая интервал или квадрат. Темнеменее, изучение системитерированных функций важно для фрактальной теории, так как с их помощью можно получить удивительное множество фракталов. Теория итерированных функций замечательна сама по себе и служит составной частью общей теории динамических систем, важного раздела математики.
4.1. Системы итерированных функций
Прежде чем углубиться в теорию систем итерированных функций, рассмотрим пример, а именно ковер Серпинского, которыймы уже строили прежде. Для построения мы выбирали в качестве исходного множества треугольник и накаждом шаге выкидывали центральную треугольную часть (невключая границу) образующихся треугольников. Ниже мы рассмотрим два других метода: детерминированный (рис. 4.1) и рандомизированный(рис. 4.2).
4-1 Системы итерированныхфункций • 97
Рис. 4.1. Ковер Серпинского: детерминированный алгоритм (уровни 0, 1, 2, 3, 4, 5)
В п. 3.4 для построения использовались следующие три аффинных преобразования (рис.3.8):
\ |
1/2 |
0 |
Xl |
О |
X2 _ |
0 |
1/2 |
X2 |
О |
|
Xl ' \ |
|
1/2 |
0 |
Xl ' |
1/2] |
||
|
X2 |
J |
- |
0 |
1/2 |
X2 |
+ |
О ] |
Ы |
' Xl 'л |
|
1/2 |
0 |
Xl |
|
1/4 |
|
X2 |
) |
— |
0 |
1/2 |
X2 |
+ |
|
|
Если 5 — замкнутое множество в виде треугольника с вершинами (0,0), (1,0) и (1/2,л/3/2), то образы Ti(S), T2(S) и T3(S) суть три меньшие треугольные области, изображенные на рисунке справа.
В детерминированном алгоритме рассматривают следующую последовательность множеств:
£Ь = компактное множество (произвольное)
Ei = Ti(E0)UT2(E0)UT3(E0)
Еп =
98 • Глава 4 I Системы итерированных функций
Рис. 4.2. Ковер Серпинского: рандомизированный алгоритм (построено 10000 точек)
Если в качестве EQ выбрать замкнутую треугольную область 5, то множества Еп, построенные указанным способом, будут в точности те же, что и при выкидывании центральных треугольных частей.
В рандомизированномалгоритме,который часто называют игрой «Хаос» (си. упр. 1 в конце параграфа), в качестве начального множества выбирают одну точку:
хо |
= |
начальная точка (произвольная) |
xi |
= |
Ti(x0) или Тг(хо) или |
xn |
= |
Ti(xn_i) или X2(xn_i) или T3(xn_i) |
На каждом шаге, вместо того чтобы применять сразу три преобразования T\(S), Тг(5), Тз(5), мы применяем только одно, выбранное случайным образом. Таким образом, на каждом шаге мы получаем ровно одну точку. Оказывается, что после некоторого переходного
4-1 Системы итерированных функций • 99
этапа точки, сгенерированные в рандомизированном алгоритме, заполняют в точности ковер Серпинского.
Замечательным свойством алгоритмов, основанных на теории систем итерированных функций, является то, что их результат (аттрактор) совершенно не зависит от выбора начального множества EQ или начальной точки XQ. В случае детерминированного алгоритма это означает, что в качестве EQ можно взять любое компактное множество на плоскости: предельное множество попрежнему будет совпадать с ковром Серпинского. В случае рандомизированного алгоритма, вне зависимости от выбора начальной точки хо, после нескольких итераций точки начинают заполнять ковер Серпинского.
Рандомизированный алгоритм часто используется на компьютерах, в которых предусмотрена возможность вывода графического изображения на экран в режиме 1 пиксел за раз. Для детерминированного алгоритма требуется большой объем памяти. Стоит отметить, что для вывода на печать необходим принтер, способный работать с большими изображениями.
В общем случае, для чтобы построить систему итерированных функций введем в рассмотрение совокупность сжимающих отображений:
Т\, с коэффициентом сжатия «i < 1, Гг, с коэффициентом сжатия «2 < 1,
Tmi с коэффициентом сжатия sm < 1,
действующих на Rn . Эти т отображений используются для построения одного сжимающего отображения Т в пространстве К. всех непустых компактов из Rn . ПреобразованиеХатчинсона Т : /С —> /С определяется следующим образом:
T(E)=T1(E)UT2{E)U---UTm(E), |
E € 1С. (4.1) |
Это преобразование ставит в соответствие «точкам» из 1С также «точки» из JC,причем под точками здесь понимаются компактные множества.
100 • Глава 4 I Системы итерированных функций
Таким образом, системой итерированных функций (СИФ)называют совокупность введенных выше отображений вместе с итерационной схемой:
EQ = компактное множество (произвольное) Ег = Т(£Ь),
Еп =
Основная задача теории СИФ— выяснить, когда СИФ порождает предельное множество Е:
Е = lim En,
п—>оо
в смысле сходимости в метрике Хаусдорфа. Если предел существует, то множество Е называют аттрактором системы итерированных функций. Причем аттрактор часто (но не всегда!) оказывается фрактальным множеством. Очевидно, для того чтобы обеспечить сходимость, требуется наложить определенные ограничения на введенные выше преобразования, к примеру запретить точкам уходить на бесконечность.
Основные математические идеи, необходимые для установления условий сходимости, уже были представлены. Если нам удастся показать, что Т является сжимающим отображением на метрическом пространстве (К, Н), то мы сможем применить теорию сжимающих отображений1. В этом случае аттрактор Е есть не что иное, как неподвижная точка отображения Т.
Таким образом, необходимо показать, что метрическое пространство (/С,Н) является полным. Теорема 4.3.3 дает положительный ответ на этот вопрос. Затем надо убедиться в том, что множество Т(К), где К € 1С — произвольный компакт, также компактно. Это утверждение следует из известных теорем о непрерывных функциях (см. упр. 4 в прил. А.2). Остается последний шаг: доказать, что Т — сжимающее отображение на (/С, Н).
1 Н — метрика Хаусдорфа.