Sustav iterirane funkcije

U matematici, sustav iterirane funkcije ili IFS (od engl. iterated function system) je postupak konstruiranja fraktala, pri čemu su dobivene konstrukcije uvijek samoslične.

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 sustav funkcije). Kanonski je primjer trokut Sierpińskog. Funkcije su obično kontraktivne, što znači da zbližavaju točke i smanjivaju oblike. Stoga je oblik IFS fraktala načinjen od nekoliko manjih kopija samog sebe koje se moguće preklapaju, od kojih je svaka načinjena od kopija samog sebe, i tako ad infinitum. Ovo je ishodište samoslične fraktalne naravi.

Formalno,

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

gdje su

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

i

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

funkcija koja se iterira. S je fiksna točka Hutchinsonovog operatora, koji je unija funkcija ${\displaystyle f_{i}}$.

Kolekcija funkcija ${\displaystyle f_{i}}$ skupa s kompozicijom oblikuje monoid. Ako postoje samo dvije 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 lijevom ili desnom granom). Općenito, ako postoji p funkcija, tada se kompozicija može vizualizirati 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 znamenka p-adičnog broja naznačuje 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 Cantorov skup i de Rhamove krivulje.

Gdjegdje se za svaku od funkcija ${\displaystyle f_{i}}$ zahtijeva da bude linearna, ili točnije afina tronsformacija i stoga može biti predstavljena matricom. Međutim, IFS-ovi također mogu biti izgrađeni od nelinearnih funkcija, uključujući projektivne transformacije i Möbiusove transformacije. Fraktalni plamen je primjer IFS-a s nelinearnim funkcijama.

Najuobičajeniji algoritam za računanje IFS fraktala je igra kaosa. Sastoji se od odabira slučajne točke na ravnini, te iterativne primjene jedne od slučajno odabranih funkcija iz sustava funkcija te iscrtavanja točke. Alternativni algoritam jest generiranje svih mogućih slijedova funkcija do na danu duljinu, te iscrtavanja rezultata primjene svakog od ovih slijedova funkcija na inicijalnu točku ili oblik.

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

Slijedi primjer papratolike slike izračunate rabeći sustav iterirane funkcije.

Prva iscrtana točka jest ishodište (x₀ = 0, y₀ = 0) te su potom nove točke iterativno izračunate slučajnom primjenom jedne od sljedećih koordinatnih transformacija:

x_{n + 1} = 0

y_{n + 1} = 0.16 y_n

Ova je koordinatna transformacija odabrana 1% vremena i preslikava svaku točku u toč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 točku unutar crnog pravokutnika u točku unutar crvenog pravokutnika 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 točku unutar crnog pravokutnika u točku unutar tamnoplavog pravokutnika 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 točku unutar crnog pravokutnika u točku unutar svijetloplavog pravokutnika na slici.

Prva koordinatna transformacija iscrtava stabljiku. Druga iscrtava donji list paprati nalijevo. 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 cjelina replika svakog od listova. Bilješka: Paprat je unutar opsega -5 <= x <= 5 i 0 <= y <= 10.

IFS-eve je u današnjeg obliku zamislio John Hutchinson 1981. i popularizirao Michael Barnsley u svojoj knjizi Fractals Everywhere. Poopćuju ideju de Rhamove krivulje, samoslične krivulje koju je opisao Georges de Rham 1957. Još se ranije pojavio Cantorov skup, prvotno opisan 1884.

• L-sustav
• Fraktalna kompresija
• Fraktalni plamen

• IFS-a i Java ilustracija s nekoliko ugrađenih primjera^{[neaktivna poveznica]}
• The Algoritam fraktalnog plamena