Gra w chaos

Gra w chaos – algorytm komputerowego generowania obrazów pewnych fraktali. Generuje on przybliżony obraz atraktora lub punktu stałego dowolnego systemu funkcji iterowanych.

Algorytm

Zaczynając od pewnego punktu ${\displaystyle x_{0},}$ kolejne iteracje są dane przy pomocy wzoru ${\displaystyle x_{n+1}=f_{i}(x_{n}),}$ gdzie ${\displaystyle f_{i}(x)}$ jest jedną z funkcji iterowanych wybieraną niezależnie i losowo dla każdej iteracji. Iteracje zbiegają się do punktu stałego systemu funkcji iterowanych. Jeżeli wartość początkowa ${\displaystyle x_{0}}$ należy do atraktora systemu funkcji iterowanych, wówczas wszystkie punkty ${\displaystyle x_{n}}$ również należą do tego atraktora i z prawdopodobieństwem 1 tworzą w nim zbiór gęsty. Prawdziwy jest znacznie ogólniejszy rezultat.

Twierdzenie o grze w chaos (zob.^[1]): Niech ${\displaystyle X}$ będzie przestrzenią metryczną zupełną, zaś ${\displaystyle {\mathcal {F}}=\{f_{i}\}_{i=1}^{m}}$ iterowanym układem funkcyjnym (IFS) złożonym z przekształceń zwężających ${\displaystyle f_{i}\colon X\to X.}$ Niech ${\displaystyle x_{n+1}=f_{i_{n}}(x_{n})}$ będzie orbitą startującą w dowolnym punkcie ${\displaystyle x_{0}\in X.}$ Wówczas atraktor ${\displaystyle A}$ układu ${\displaystyle {\mathcal {F}}}$ (który istnieje w myśl twierdzenia Hutchinsona) odtwarzany jest przez zbiór punktów skupienia ${\displaystyle \omega ((x_{n}))=\bigcap _{k=1}^{\infty }{\overline {\{x_{n}:n\geqslant k\}}}}$ orbity ${\displaystyle x_{n}{:}}$

• (wersja probabilistyczna) ${\displaystyle A=\omega ((x_{n}))}$ z prawdopodobieństwem 1, jeśli tylko ciąg ${\displaystyle i_{n},n=1,2,\dots ,}$ sterujący wyborem funkcji w n-tym kroku iteracji, jest losowany z użyciem schematu Bernoulliego na zbiorze ${\displaystyle \{1,\dots ,m\};}$
• (wersja zderandomizowana) ${\displaystyle A=\omega ((x_{n})),}$ jeśli tylko ciąg ${\displaystyle i_{n},n=1,2,\dots ,}$ jest dyzjunktywny nad alfabetem ${\displaystyle \{1,\dots ,m\},}$ tzn. dowolny łańcuch skończony nad ${\displaystyle \{1,\dots ,m\}}$ pojawia się w ${\displaystyle i_{n}.}$

W przypadku układów kontrakcji wariant probabilistyczny twierdzenia o grze w chaos (używający schematu Bernoulliego) wynika z wariantu dyzjunktywnego. Dzieje się tak, gdyż schemat Bernoulliego generuje ciągi dyzjunktywne prawie na pewno.

Przykład dla trójkąta Sierpińskiego

Na początku stawia się na płaszczyźnie 3 dowolne punkty (powinny być niewspółliniowe, gdyż inaczej fraktal zdegeneruje się do odcinka), po czym wybiera sobie kolejny punkt płaszczyzny, zwany punktem gry (game point). Następnie wybiera się dowolny z trzech punktów obranych na samym początku (można je oznaczyć 1, 2 i 3, po czym korzystając z generatora liczb losowych, wybierać je) i stawia punkt w połowie odległości między czwartym punktem a tym wybranym. Powtarza się ten krok, za każdym razem oznaczając punkt leżący dokładnie w połowie odległości między ostatnio postawionym a jednym z trzech pierwszych.

Efektem algorytmu – zakładając, że punkty były losowane z mniej więcej takim samym prawdopodobieństwem – jest pewien wariant trójkąta Sierpińskiego. Jego wierzchołkami są trzy punkty wybrane na samym początku gry.

Zobacz też

• dywan Sierpińskiego
• kostka Mengera

Przypisy