Sistem iterirane funkcije

U matematici, sistem iterirane funkcije ili IFS (od engl. iterated function system) je postupak konstruisanja fraktala, pri čemu su dobijene konstrukcije uvek samoslične.

Trougao Serpinskog kreiran putem IFS

IFS fraktalnog plamena dizajniran od strane Krisa Ursitija

IFS fraktali, kako se obično zovu, mogu biti bilo koje dimenzije, iako se obično računaju i crtaju u 2D. Fraktal je načinjen od unija nekoliko kopija samog sebe, pri čemu je svaka kopija transformirana funkcijom (otuda i sistem funkcije). Kanonski primer je trougao Serpinskog. Funkcije su obično kontraktivne, što znači da zbližavaju tačke i smanjivaju oblike. Stoga je oblik IFS fraktala načinjen od nekoliko manjih kopija samog sebe koje se moguće preklapiti, svaki od kojih je načinjen od kopija samog sebe, i tako ad infinitum. Ovo je ishodište samoslične fraktalne naravi.

Definicija

Formalno,

$S=\bigcup _{i}^{N}f_{i}(S),\,$

gde su

$S\subset \mathbb {R} ^{n}\,$

i

$f_{i}:\mathbb {R} ^{n}\to \mathbb {R} ^{n}.$

funkcija koja se iterira. S je fiksna tačka Hutčinsonovog operatora, koji je unija funkcija $f_{i}$.

Svojstva

Kolekcija funkcija $f_{i}$ skupa s kompozicijom oblikuje monoid. Ako postoje samo dve takve funkcije, monoid je diadički monoid. Kompozicija može biti vizualizirana kao beskonačno binarno stablo u kojem se na svakom čvoru može obaviti kompozicija s jednom ili drugom funkcijom (tj., traversirati levom ili desnom granom). U opštem slučaju, ako postoji p funkcija, tada se kompozicija može vizualizovati kao p-adično stablo.

Budući da kompozicija funkcije uzima ovaj oblik, elementi monoida se mogu shvatiti kao izomorfni s p-adičnim brojevima, tj. svaka cifra p-adičnog broja označava funkciju s kojom se komponira.

Grupa automorfizama diadičkog monoida je modularna grupa - ovo se može shvatiti za opis fraktalne samosličnosti mnogih fraktala, uključujući Kantorov skup i de Ramove krive.

Primeri

Za svaku od funkcija $f_{i}$ se zahteva da bude linearna, ili tačnije afina tronsformacija i stoga može biti predstavljena matricom. Međutim, IFS-ovi takođe mogu da bugu izgrađeni od nelinearnih funkcija, uključujući projektivne transformacije i Mobiusove transformacije. Fraktalni plamen je primer IFS-a sa nelinearnim funkcijama.

Najuobičajeniji algoritam za računanje IFS fraktala je igra haosa. Sastoji se od odabira slučajne tačke na ravni, te iterativne primene jedne od slučajno odabranih funkcija iz sistema funkcija te iscrtavanja tačke. Alternativni algoritam je generiranje svih mogućih sledova funkcija do date razdaljine, te iscrtavanja rezultata primene svakog od ovih sledova funkcija na inicijalnu tačku ili oblik.

Svaki od ovih algoritama pruža globalnu konstrukciju koja generiše tačke raspodeljene duž celog fraktala. Ako se crta malo područje fraktala, mnoge će od ovih tačaka padati izvan granica zaslona, što čini zumiranje unutar IFS konstrukcija nepraktičnim. Tamo gde se zahteva visok stupanj detaljnosti na malom području faktala, metode lokalne konstrukcije zasnovane na proračunu unaprednih orbita i sudbine pojedinih tačaka bi mogle biti delotvorne (iako nijedna programska podrška za rješavanje IFS-eva to ne čini).

Primer: fraktalna "paprat"

Fraktalna paprat

Sledi primer slike paprati izračunate koristeći sistem iterirane funkcije.

Prva iscrtana tačka je ishodište (x₀ = 0, y₀ = 0) te su potom nove tačke iterativno izračunate slučajnom primenom jedne od sledećih koordinatnih transformacija:

x_{n + 1} = 0

y_{n + 1} = 0.16 y_n

Ova je koordinatna transformacija odabrana 1% vremena i preslikava svaku tačku u tačku u linijskom segmentu prikazanim zeleno na slici.

x_{n + 1} = 0.2 x_n − 0.26 y_n

y_{n + 1} = 0.23 x_n + 0.22 y_n + 1.6

Ova koordinatna transformacija je odabrana 7% vremena i preslikava svaku tačku unutar crnog pravougaonika u tačku unutar crvenog pravougaonika na slici.

x_{n + 1} = −0.15 x_n + 0.28 y_n

y_{n + 1} = 0.26 x_n + 0.24 y_n + 0.44

Ova koordinatna transformacija je odabrana 7% vremena i preslikava svaku tačku unutar crnog pravougaonika u tačku unutar tamnoplavog pravougaonika na slici.

x_{n + 1} = 0.85 x_n + 0.04 y_n

y_{n + 1} = −0.04 x_n + 0.85 y_n + 1.6

Ova koordinatna transformacija je odabrana 85% vremena i preslikava svaku tačku unutar crnog pravougaonika u tačku unutar svijetloplavog pravougaonika na slici.

Prva koordinatna transformacija iscrtava stabljiku. Druga iscrtava donji list paprati nalevo. Treća iscrtava donji list nadesno. Četvrta generira sukcesivne kopije stabljike i donjih listova kako bi upotpunila paprat. Rekurzivna narav IFS-a jamči da je celina replika svakog od listova. Napomena: Paprat je unutar opsega -5 <= x <= 5 i 0 <= y <= 10.

Mengerov sunđer, 3-dimenzionalni IFS.

Istorija

IFS-eve je u današnjeg obliku zamislio Džon Hutčinson 1981. i popularisao Majkl Barnsli u svojoj knjizi Fraktali Svuda. Uopštenu ideju de Ramove krive, samoslične krive je opisao Džordž de Ram 1957. Još se ranije pojavio Kantorov skup, prvotno opisan 1884.

Literatura

• Draves, Scott; Reckase, Erik (2007). „The Fractal Flame Algorithm” (PDF). Архивирано из оригинала (pdf) 09. 05. 2008. г. Приступљено 17. 7. 2008. 
• Falconer, Kenneth (1990). Fractal geometry: Mathematical foundations and applications. John Wiley and Sons. стр. 113–117, 136. ISBN 0-471-92287-0. 

Vidi još

• L-sastav
• Fraktalna kompresija
• Fraktalni plamen

Spoljašnje veze

• IFS-a i Java ilustracija s nekoliko ugrađenih primera
• The Algoritam fraktalnog plamena