Kranover R M - Fraktaly i khaos v din sist
.pdf4-1 Системы итерированных функций • 101
Теорема 4.1.1. Преобразование Т, определенное формулой Ц.1), является сжимающим отображением на 1С с хаусдорфовой метрикой. Его коэффициентсжатия равен:
s = max{si,...,sm}.
Доказательство. Я благодарен Ричарду Найдингеру за предложенное доказательство. Во-первых, заметим, что для любого компакта F выполняется е € F + г тогда и только тогда, когда существует такой элемент f e F, что d(e,f) < г. Следовательно, если А с В + г, то Ti(A) С Ti(B) + Sir для каждого отображения Т;. По определению, неравенство Н(Е, F) < е эквивалентно следующей записи на языке множеств: Е С F + е и F С Е + е. Положим г = Н(А, В). Тогда, если А С В + г, то:
Тг(А) С ЩВ) |
+ Sir, |
t = l,2,...,ro. |
Следовательно, |
|
|
Т(А) |
С Т(В) |
+ sr. |
Если поменять местами А и В, получим:
Т(В) С Т(А) + sr.
Таким образом,
Н(Т(А), Т(В)) <sr = sH(A, В), ш
Следующая теорема суммирует основные результаты о сходимости систем итерированных функций.
Теорема 4.1.2. Пусть Т\,Т2,... ,Тт — сжимающие отображения на Rn . Для произвольного начального множества EQ € /С,система итерированных функций
где Т — преобразование Хатчинсона (4-1), сходится в метрике Хаусдорфак единственному множеству Е G/С. Множество Е называют аттрактором СИФ. Обратно, множество Е можнопредставить в виде:
Е = lim T( n ) (#o).
п—*оо
Вопрос о сходимости рандомизированного алгоритма для системы итерированных функций рассматривается в п. 7.6.
102 • Глава 4 I Системы итерированных функций
Упражнения 4.1.
1. Игра «Хаос» состоит в следующем. Положим Pi = (0,0), Рг = (1,0) и Рз = (1/2, л/3/2) и установим фишку в произвольной начальной точке XQ. Бросим игральную кость. Если выпало 1 или 2, передвинем фишку на половину расстояния между XQ И P I В направлении Р\. Если выпало 3 или 4, передвинем фишку на половину расстояния между XQ ИР% В направлении P2 . Если выпало 5 или 6, передвинем фишку на половину расстояния между XQ и Рз в направлении Рз. Назовем новую точку Х\. Повторяя описанную процедуру снова и снова, получим последовательность точек Хо, Х\, Лг, Хз, ... на плоскости, каждая из которых находится на полпути до случайно выбранной вершины. Отбросим несколько начальных точек последовательности, допустим первые 100 точек. Оказывается, оставшиеся точки заполняют ковер Серпинского.
Показать, что игра «Хаос» есть не что иное, как рандомизированный алгоритм для получения ковра Серпинского,описанный
вэтом параграфе.
2.Найти аффинные преобразования Т\, Т2, Тз системы итерированных функций, аттрактор которой изображен на рис. 4.3. Смоделировать СИФ на компьютере с помощью детерминированного или рандомизированного алгоритма.
3.Найти аффинные преобразования Т ь Т2, Т3, Т4, Г5, Т6, Т7, Т8 СИФ, аттрактор которой описан в упр. 2(а) п. 2.1.
4.Построить вручную третью итерацию ковра Серпинского (см.
рис. 2.5). Указать, какому из отображений Т\, Т2, Гз соответствует та или иная треугольная область.
4.2. Реализация СИФ
Как было отмечено в п. 4.1, имеется два подхода к реализации СИФ: детерминированный и рандомизированный. Детерминированный алгоритм позволяет получать привлекательные изображения, но требует обработки больших массивов нулей и единиц. Единица означает, что соответствующий пиксел принадлежит изображению,
4-2Реализация СИФ 103
Рис. 4.3.Модифицированный ковер Серпинского
а нуль означает, что соответствующий пиксел не принадлежитизображению. Длякомпьютерной программы детерминированногоСИФ алгоритма лучше всего подходят такие языки программирования, как Си,Паскаль, Фортран илидругие, допускающие компиляцию. Компилированная версия программы (в машинном коде) всегда работает намного быстрее версии с встроенным интерпретатором.
В рандомизированном алгоритме нет необходимости хранить большие массивы данных в памяти. Поэтому им удобно пользоваться на компьютерах с ограниченными ресурсами, вычисляя одну точку на каждом шаге и сразу же отображая ее на экране. С другой стороны, длятого чтобы получить изображение приемлемого качества, требуются тысячи точек, поэтому данный подход нельзя назвать экономным.
Детерминированный алгоритм. Сначала выберем размеры окна т х т для графического вывода. Размеры меньше 200 х 200 используются обычно для прикидки, чтобы посмотреть, как примерно будет выглядеть конечное изображение. Начиная где-то с 256 х 256, качество изображений становится удовлетворительным.
104 • Глава 4 / Системы итерированных функций
Однако если вы хотите получить превосходный результат, размеры окна должны составлять 400 х 400 или более. При этом не стоит забывать, что вычисления производятся для т 2 точек на каждой итерации, и, следовательно, с ростом т объем вычислений может превысить разумные пределы.
Далее, когда размер окна зафиксирован, имеет смысл использовать преобразование мировых координат в экранные, описанное
вп. 3.4, и найти эквиваленты аффинных отображений для окна m х т. Тогда все вычисления можно будет производить в экранных координатах. Далее мы предполагаем, что все отображения заданы
вэкранных координатах.
Программная реализация детерминированного алгоритма не лишена подводных камней. Если какая-нибудь точка выйдет за пределы окна т х т, это приведет к аварийному останову программы с сообщением об ошибке типа «индекс вышел за пределы». Такое может случиться, даже если визуально аттрактор целиком содержится внутри выбранного окна. Обычно подобная проблема возникает на одной из первых итераций. Практическое решение состоит в том, чтобы проверять новые точки сразу же после их нахождения и прекращать вычисления для точек, вышедших за границы окна. Это не должно привести к существенной потере информации в конечном изображении, так как большинство точек в конечном изображении являются результатом итерирования многих различных начальных точек.
Пусть СИФ задана аффинными преобразованиями:
X (тс) — l l v -I- * |
i - 1 9 |
n |
Будем хранить все коэффициенты в одной матрице С размера п х 6:
ах |
Ъ\ с\ d\ |
t\ /i |
||
С = %2 |
^ |
° 2 d2 62 |
/2 |
(4.2) |
а„ |
Ьп |
Сп dn |
en |
fn |
Далее следует детерминированный алгоритм СИФ (ДСИФ).
4-2 Реализация СИФ • 105
Алгоритм 4.2.1. (ДСИФ)
Назначение: детерминированная система итерированных функций. Вход:
С (аффинныекоэффициенты)
п(число аффинных отображений) т (размер квадратного окна)
EQ (матрица т х т начальных значений) level (число итераций)
Выход:
Т (бинарная матрица аттрактора размера т х т)
Инициализация:
S = О(нулевая матрица размера т х т)
ГС1
Шаги:
for к = 1 to level
for i = 1 to m, for j —1 to m ifT(t,j) = l
for I = 1 to n
ii = [C(l,l)i + C(l, 2)j + C(l, 5)] +1 if 1 < ii < m
jj = [C(l,3). + C(/,4)j + C(Z,6)] + 1 if 1 < jj < m
S(ii,jj) = 1 end if
end if end for
end if
end for, end for
T = S
5 = 0 end for
Рандомизированный алгоритм. Укажем два главных отличия рандомизированного алгоритма от детерминированного. Во-первых, начальное множество содержит всего одну точку. Во-вторых, на каждом шаге используется только одно аффинное преобразование
106 • Глава 4 I Системы итерированных функций
из всей совокупности преобразований, задающих СИФ. Это преобразование выбирается случайным образом. Полученное множество также содержит ровно одну точку, которая сразу же выводится на экран и используется для вычисления следующей итерации. Следовательно, отпадает необходимость хранить все точки, кроме текущей.
Аффинное преобразование Г(х) = Ах +а уменьшает (или увеличивает) площади в | det(A)| раз(см. упр. 1 в конце этого параграфа). Для того чтобы в процессе случайного выбора преобразования с малым детерминантом не появлялись слишком часто, имеет смысл производить выбор с вероятностями, пропорциональными детерминантам. Для этого определим веса pi, Р2, •..,рп-
п |
|
р3 = det(Aj)/^2 det(A), |
j = 1,2,..., п, |
где Аг — матрица аффинного преобразования Тг, i = 1,2,...,п. Очевидно, />i+ р2 + • • • +Рп — 1) то есть определенные нами веса суть вероятности. В рандомизированном алгоритме преобразование
Тг выбирается с вероятностью pi. Для этого используется внешняя подпрограмма PICK. Она принимает вектор Р = [pi p% ... рп] в качестве входного параметра и возвращает одно из чисел 1, 2, ..., п, причем число j появляется с вероятностью pj.
Ниже приводится рандомизированный алгоритм (РСИФ), в котором все вычисления и вывод на экран производятся в мировых координатах.
Алгоритм 4.2.2. (РСИФ)
Назначение: рандомизированная система итерированных функций.
Вход:
С(аффинныекоэффициенты)
п(число аффинных отображений)
Р = bi Vi •••Рп](вероятности) a,b,c,d (координаты окна, [a, b] x[c,d\) (ясьЗ/о) (начальная точка)
level (число итераций, порядка тысячи)
Выход:
изображение аттрактора.
4.2 РеализацияСИФ • 107
Инициализация:
графическое окно вывода [a,b] x [с,d].
Шаги: |
|
|
for j = 1 to 100 |
|
|
к = PICK(P) |
(см. ниже) |
|
х = [С(к, 1)х0 |
+ С{к, 2)2/о + С{к, 5)] |
|
у = [С(к, 3)х0 |
+ С(к, 4)г/0 |
+ С(к, 6)] |
хо = х |
|
|
Уо = У |
|
|
end for |
|
|
for j = 1 to /eve/ |
|
|
fc= PICK{P) |
(см. ниже) |
|
x = [C(A, l)x0 |
+ C{k, 2)y0 |
+ C(k, 5)] |
у = [C(k, 3)x0 |
+ C(k, % o + C(k, 6)] |
|
отобразить точку (х, у)
XQ = X
2/0 = 2/ end for
Замечание: команда к = PICK(P) означает, что целое число к выбирается случайным образом с вероятностью рк-
Интересные примеры аттракторов, построенных при помощи СИФ, изображены на рис. 4.4, 4.5, 4.6, 4.7, 4.8 и 4.9. Соответствующие аффинные коэффициенты приведены в табл. 4.1.
Упражнения 4.2.
1. Рассмотрим аффинное преобразование плоскости:
Т(х) = |
а |
Ъ |
е |
|
с |
d |
f |
||
|
Показать, что Т уменьшает (или увеличивает) площади фигур в D раз:
D = det
Указание: рассмотреть сначала маленькие квадраты. Для произвольных фигур определить сетку из маленьких квадратов.
2.(Компьютерный эксперимент.) Запрограммировать алгоритмы ДСИФ и РСИФ для СИФ, заданной тремя аффинными отображениями из упр. 8, п. 3.4.
108 • Глава 4 / Системы итерированных функций
Рис. 4.4. Лист: программа ДСИФ
Р и г . 4.5. ТТРПРВППППГПЯ.ММЯ ГГПИФ
4-2 Реализация СИФ • 109
Рис. 4.6. Ковер А: программа ДСИФ
Рис. 4.7. Кристалл: программа ДСИФ
110 • Глава 4 I Системы итерированных функций
Рис. 4.8. Ковер В: программа ДСИФ
Риг. 4.9. Папоротник: программа ДСИФ