IFS (geometria fraktalna)

Paproć Barnsleya wygenerowana za pomocą systemu IFS

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).

Definicja formalna

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

${\displaystyle |F_{i}(x)-F_{i}(y)|\leqslant r_{i}|x-y|.}$

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle X}$ jest prostokątem na płaszczyźnie).

Metoda iteracji

Jeżeli zdefiniujemy teraz przekształcenie ${\displaystyle F,}$ które dany zbiór ${\displaystyle A}$ zmienia w sumę obrazów przez ${\displaystyle F_{i},}$ tzn.

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

to wówczas kolejne obrazy ${\displaystyle 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 ${\displaystyle A}$ zaczniemy. Dokładniej,

${\displaystyle F^{k}(A)\to K}$

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

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

gdzie ${\displaystyle A_{\delta },B_{\delta }}$ oznaczają ${\displaystyle \delta }$-otoczki zbiorów (otoczki „grubości” ${\displaystyle \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 ${\displaystyle F}$ iteruje się obraz punku poprzez losowo wybierane odwzorowania ${\displaystyle F_{i}.}$ Zbiór punktów skupienia tak utworzonej orbity z prawdopodobieństwem 1 pokrywa się z atraktorem ${\displaystyle K.}$

Warunek zbioru otwartego i wymiar Hausdorffa

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

${\displaystyle \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ą ${\displaystyle s}$)

${\displaystyle \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 [online], Wolfram Research [dostęp 2020-12-12]  (ang.).