IFS (geometria fraktalna)

Paproć Barnsleya wygenerowana za pomocą systemu IFS

IFS (z Szablon:Ang., zwany też systemem funkcji iterowanych, systemem iterowanych kontrakcji albo przekształceń zwężających) – rodzina funkcji, za pomocą których konstruuje się fraktale samopodobne. W matematyce terminu tego używa się także na określenie samej metody konstrukcji (przedstawionej poniżej). Opis w obecnej postaci został podany przez Hutchinsona (1981). IFS znajduje zastosowanie w zagadnieniach kompresji danych, zwłaszcza graficznych (grafika fraktalna) oraz interpolacji krzywych i powierzchni (FIF Szablon:Ang.).

Definicja formalna

Załóżmy dla pewnego ustalonego $m\in \mathbb{N},$ $m⩾2,$ że mamy rodzinę funkcji $F_i,i=1,2,\dots ,m,$ określoną na pewnym podzbiorze $X\subset {ℝ}^d.$ Załóżmy ponadto że każda funkcja jest kontrakcją o skali $r_i<1,$ tzn.

$|F_i(x)-F_i(y)|⩽r_i|x-y|.$

Istnieje wówczas dokładnie jeden niepusty zbiór zwarty $K$ taki, że

$K=\bigcup _{i=1}^m{F}_i(K).$

Zbiór ten nazywamy atraktorem danego IFS, często – choć nie zawsze – jest to interesujący fraktal.

Powyższe zaś twierdzenie dostarczające metody konstrukcji fraktali określa się ogólnie jako IFS. W żargonie IFS oznacza często także samą rodzinę funkcji $F_i.$ Twierdzenie to obowiązuje w istocie na dowolnej przestrzeni metrycznej zupełnej, aczkolwiek z punktu widzenia zastosowań najważniejszy zdaje się być przypadek euklidesowy (w szczególnosci, gdy $X$ jest prostokątem na płaszczyźnie).

Metoda iteracji

Jeżeli zdefiniujemy teraz przekształcenie $F,$ które dany zbiór $A$ zmienia w sumę obrazów przez $F_i,$ tzn.

$F(A)=\bigcup _{i=1}^m{F}_i(A),$

to wówczas kolejne obrazy $F(A),F(F(A)),F(F(F(A))\dots )$ będą coraz bardziej przypominać atraktor, niezależnie od tego od jakiego ograniczonego zbioru początkowego $A$ zaczniemy. Dokładniej,

$F^k(A)\to K$

w metryce Hausdorffa. Metryka ta jest zdefiniowana następująco. Dla dwu zbiorów $A$ i $B$ określamy

$d(A,B)=\inf \{\delta :A\subset B_{\delta }\text{ oraz }B\subset A_{\delta }\},$

gdzie $A_{\delta },B_{\delta }$ oznaczają $\delta$-otoczki zbiorów (otoczki „grubości” $\delta$).

Własność ta jest podstawą wizualizacji fraktali otrzymywanych przez IFS. W zastosowaniach ważną rolę odgrywa algorytm iteracji losowej zwany grą chaosu. Zamiast iterować obraz całego zbioru poprzez operator Hutchinsona $F$ iteruje się obraz punku poprzez losowo wybierane odwzorowania $F_i.$ Zbiór punktów skupienia tak utworzonej orbity z prawdopodobieństwem 1 pokrywa się z atraktorem $K.$

Warunek zbioru otwartego i wymiar Hausdorffa

Mówimy, że IFS spełnia warunek zbioru otwartego, jeżeli istnieje (niepusty) otwarty zbiór $U$ taki, że

$\bigcup _{i=1}^m{F}_i(U)\subset U.$

Jeżeli IFS spełnia warunek zbioru otwartego to wymiar Hausdorffa atraktora jest jedynym rozwiązaniem równania (z niewiadomą $s$)

$\sum _{i=1}^m{r}_i^s=1.$

Przykłady

• dywan Sierpińskiego
• kostka Mengera
• krzywa Kocha
• paproć Barnsleya
• piramida Sierpińskiego
• smok Heighwaya
• trójkąt Sierpińskiego
• zbiór Cantora

Literatura

• Barnsley, Michael F., and Hawley Rising. Fractals Everywhere. Boston: Academic Press Professional, 1993. Szablon:ISBN.

Linki zewnętrzne

• Szablon:MathWorld