преобразование н^о):

XI = ЩО) (Хо)

Таким образом, алгоритм строит последовательность

-*0> *1> *2> •••

где

*п = ™Кп){хпЛ\ п = 1,2,...

где на каждом шаге /(и) б выбирается с вероятно-

стью ркпу Заметим, что

хпеА„=\У°"{\)

для некоторого начального множества А0. Какое множество выбрано в качестве А0 - не имеет значения, так как теорема о сжимающих отображениях гарантирует сходимость итераЦИ" онного процесса для любого начального множества. Единен венное, что нам известно о множестве Ао, - это то, что еМУ принадлежит точка хо. Последовательность точек хп образу^ так называемую орбиту, или траекторию динамическое системы. Программа, реализующая вероятностный алгоритм? представленная в листинге 2.4.3, строит эту орбиту. Заметим* что первые 10 или около того (это число произвольно) точек являются «скрытыми» (не строятся).

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

59

Вероятностный алгоритм создает изображения-аттракторы высокого качества намного быстрее, чем детерминистический алгоритм. Это происходит не только благодаря тому, что этот алгоритм выполняет на каждой итерации меньшую работу, чем детерминистический алгоритм, но и сама выполняемая им работа дает лучший результат. Детерминистический алгоритм строит на каждом п-ом шаге итерации все множество Ап. Рассмотрим изображения на Рис. 2.4.4 (d) и 2.4.5 (Ь). Все точки этих изображений представляют множество Азо, то есть множество, полученное после 30 итераций (с различными начальными изображениями). Вероятностный же алгоритм строит на п-ом шаге итерации только одну точку хп и поэтому может выполнять буквально тысячи итераций за время, которое требуется детерминистическому алгоритму на выполнение одной итерации. Кроме того, есть и еще одно дополнительное преимущество. Как показывает уравнение (2.4.4), точка хп принадлежит множеству Ап. Так, если, например, п = 30 ООО, то хп принадлежит Азоооо. Это множество Азо ооо значительно ближе к аттрактору IFS, чем множество Азо. В совокупности точки jCn-i, jcn, jc„+i,... создают изображение более близкое к истинному аттрактору IFS. На Рис. 2.4.6 показан результат работы вероятностного алгоритма с той же IFS папоротника, с помощью которой были получены изображения на Рис. 2.4.4-2.4.5. Это изображение было создано в результате около 31 ООО итераций, которые заняли всего несколько секунд на персональном компьютере класса Pentium.