CCF20140608010

2.4. Układ iterowanych odwzorowań 33

Przykład 2.3. Niech przestrzeń X będzie odcinkiem [0, lj i niech operacja W będzie określona przez układ dwóch odwzorowań

(2.22)

Dla Aq — X na rysunku 1.2 pokazano pięć kolejnych wyrazów ciągu określonego rekurencyjnie A_n+\ = W(A_n) i zbieżnego do zbioru Cantora.

Współczynnik zwężania A = 1/3, a więc odległość zbioru Cantora Aoo od jego n-tego przybliżenia wynosi h(A_n,Aoo) 1,5 • 3~”/z(Ao, Aj) = 0,25 • 3~ⁿ.

Jeżeli zamiast odcinka X = [0,1] weźmiemy płaszczyznę zmiennej zespolonej i te same odwzorowania Wi(z) = z/3,    = (z + 2)/3, to atrakto-

rem układu będzie ten sam zbiór Cantora leżący na odcinku 0 ^ Re (z) ^ 1,

Im(z) — 0.

□

Przykład 2.4. Załóżmy, że układ iterowanych odwzorowań jest określony przez cztery przekształcenia afiniczne (2.1) ze współczynnikami zebranymi w tablicy 2.1. Każde z tych przekształceń spełnia warunek Lipschitza z odpowiadającą mu stałą s. Operacja W jest więc zwężająca ze współczynnikiem A = 0,8530. Dla dowolnego zwartego podzbioru płaszczyzny Aq ciąg Ao, Ai, Ai, ■ ■ . określony rekurencyjnie A_n+\ = W(A_n) jest zbieżny do granicy Aoo, którą jest „choinka" pokazana na rysunku 2.1. Odległość h(A_n, Aoo) między n-tym wyrazem ciągu i jego granicą dąży do zera tak szybko jak Aⁿ.    □

Konstruowanie obrazów metodą opisaną powyżej jest w praktyce mało wygodne, ponieważ wymaga zapamiętywania bardzo dużej liczby punktów. Przypuśćmy, że chcemy narysować równoboczny trójkąt Sierpińskiego, którego podstawą jest odcinek [0,1], startując z jednego punktu, na przykład z początku układu współrzędnych. Załóżmy, że błąd w rysunku ma być nie większy niż 10~³ (jeden milimetr na długości jednego metra albo jeden piksel na ekranie 1000 x 1000 pikseli). Wystarczy wówczas wyznaczyć A_n dla n — 10, gdyż /z(Aio,Aco) < 2^-10 « 0,00098. Wyznaczenie A\q wymaga jednakże zapamiętania A9, które zawiera 3⁹ = 19 683 punkty. Każde dwukrotne zwiększenie dokładności wymaga zapamiętania trzykrotnie większej liczby punktów. Sytuacja jest znacznie gorsza, jeśli mamy układ IFS z większą liczbą odwzorowań o większych współczynnikach zwężania. Aby uniknąć kłopotów związanych z koniecznością zapamiętywania dużej liczby punktów podzbiorów A_n, korzysta się z probabilistycznego algorytmu układu IFS, którego uzasadnieniem zajmiemy się w następnym rozdziale.