IFS (geometria fraktalna)

IFS (z ang. iterated function system, 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 ang. fractal interpolation function).

Paproć Barnsleya wygenerowana za pomocą systemu IFS

Definicja formalna

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

$|F_{i}(x)-F_{i}(y)|\leqslant 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. ISBN 0-12-079061-0.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Barnsley's Fern, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).