Zajmiemy się najprostszą metodą konstruowania i obrazowania fraktali, za pomocą układów iterowanych przekształceń (ang. iterated function systems, w skrócie IFS). U podstaw tej metody leży kilka twierdzeń. Choć twierdzenia te są niebanalne, ich dowody są niezbyt trudne, a komputerowe algorytmy generowania fraktali za pomocą IFS-ów są jeszcze prostsze.

Zacznijmy od ustalenia, co uważamy za fraktal. Przyjmiemy, że jest nim dowolny niepusty, domknięty i ograniczony zbiór punktów płaszczyzny euklidesowej  Zwróćmy uwagę, że w ten sposób za fraktale uznaliśmy także bardzo „porządne” figury, takie jak wielokąty, których wymiar nie jest ułamkiem. Odrzucenie takich figur (przez kogoś, komu zależy tylko na „prawdziwych” fraktalach) bardzo (i niepotrzebnie) skomplikowałoby teorię, a poza tym w grafice zwykłe wielokąty też się przydadzą, prawda?

Niech  oznacza ciągłe przekształcenie płaszczyzny w siebie. Jeśli zatem  oznacza dowolny punkt płaszczyzny, to  jest również jej punktem. Od razu zauważamy, że funkcja  wyznacza również przekształcenie zbioru wszystkich figur w płaszczyźnie w ten sam zbiór; jeśli  jest figurą (tj. dowolnym zbiorem punktów płaszczyzny), to  też jest figurą, która składa się z punktów  dla wszystkich punktów   Zauważmy też, że jeśli figura  jest fraktalem (zgodnie z przyjętą definicją), to figura  również nim jest.

Oznaczymy literą  zbiór wszystkich fraktali na płaszczyźnie i zajmiemy się problemem mierzenia odległości między fraktalami. W tym celu określmy epsilonowe rozszerzenie figury. Niech  Dla dowolnego  możemy każdy punkt figury  nakryć kołem o promieniu  (biorąc koło o środku w nakrywanym punkcie). Epsilonowe rozszerzenie figury  które oznaczymy  jest sumą tych wszystkich kół. Dla  przyjmujemy  Dla dowolnych dwóch fraktali,  i  istnieje takie nieujemne  że  oraz  Najmniejsze takie  przyjmiemy za odległość figur  i  W ten sposób w zbiorze  określiliśmy metrykę (tzw.  metrykę Hausdorffa), którą oznaczymy symbolem  Łatwo jest zauważyć, do czego są tu potrzebne założenia, że fraktale są niepuste i ograniczone. Założenie, iż są one domknięte, jest potrzebne m.in. po to, aby z równości  wynikało, że  i abyśmy mieli w zbiorze  wszystkie zbiory jednopunktowe.

Mamy zatem dwie różne przestrzenie metryczne: płaszczyznę  w której odległość (punktów) mierzymy w zwykły sposób (tę metrykę oznaczymy ), i przestrzeń  z metryką  Zauważmy, że dla dowolnych punktów  jest  Możemy wybrać dowolne przekształcenia ciągłe  płaszczyzny  w siebie; przekształceniom tym odpowiadają przekształcenia  przestrzeni  w siebie. Użyjemy ich do określenia kolejnego przekształcenia  przyjmując, że dla dowolnej figury  jest

Udowodnimy

Dowód. Przypuśćmy, że przekształcenia  są zwężające. Zatem istnieje taka liczba  że dla dowolnych punktów  i  oraz dla  jest  Niech  i niech  Stąd dla każdego punktu  istnieje taki punkt  że  (na przykład, należący do  środek koła o promieniu  w którym leży punkt ). Ale wtedy dla każdego  mamy  skąd wynika, że figura  jest zawarta w epsilonowym rozszerzeniu  dla   Możemy więc napisać

i podobnie dowodzimy, że  Stąd

co kończy dowód.

---

Drugie z najważniejszych twierdzeń leżących u podstaw układów iterowanych przekształceń to

Nie będziemy dowodzili tu tego twierdzenia, podobnie jak faktu, że zbiór  z metryką  jest zupełną przestrzenią metryczną (choć nie są to trudne dowody). Punkt stały przekształcenia  określonego zgodnie z opisem podanym wyżej, jest fraktalem, tj. pewną figurą niepustą, domkniętą i ograniczoną; oznaczmy ją literą  Z jakich punktów składa się ta figura? Przekształcenia  są zwężające, a zatem każde z nich ma jeden punkt stały w płaszczyźnie  Punkty te, oczywiście, należą do figury  Weźmy dowolne (skończone) złożenie naszych przekształceń,  Ono też jest przekształceniem zwężającym płaszczyzny  i jego punkt stały również należy do  Można dowieść, że figura  jest domknięciem zbioru punktów stałych wszystkich takich złożeń.

Poza ciągłością, a potem własnością zwężania, nie nakładaliśmy żadnych warunków na przekształcenia  Najczęściej w praktyce IFS-y są budowane z przekształceń afinicznych. Każde afiniczne przekształcenie płaszczyzny może być reprezentowane za pomocą sześciu (czyli niewielu) liczb i obliczenia z nim związane zabierają bardzo mało czasu. Ma miejsce jeszcze jeden istotny fakt, którego ścisły dowód jest, niestety, dosyć żmudny: figura  zależy od liczb reprezentujących przekształcenia  w sposób ciągły. Bardzo małe zaburzenia tych liczb powodują zatem niewielkie zmiany otrzymanych obrazów.

Przejdźmy do praktyki: aby określić IFS, wybieramy na płaszczyźnie jeden duży trójkąt i  mniejszych; te mniejsze trójkąty przyjmujemy za obrazy trójkąta dużego, co określa poszczególne przekształcenia afiniczne.

Istnieje kilka metod tworzenia obrazu figury ; wszystkie one polegają na iterowaniu przekształceń  czyli stosowaniu ich do pewnej figury, a potem do jej obrazów w przekształceniach wykonanych wcześniej. Możemy zacząć od figury jednopunktowej. Najlepiej jest przyjąć, że składa się ona z punktu stałego dowolnego z przekształceń  – punkt ten łatwo jest znaleźć, rozwiązując układ dwóch równań liniowych, a jeśli zaczniemy od niego, to wszystkie kolejno otrzymane punkty będą należeć do figury

Zobaczmy kilka przykładowych obrazków.

Rys. 1

Na rysunku 1  mamy dwa fraktale otrzymane za pomocą układów pięciu przekształceń. Każde przekształcenie jest złożeniem jednokładności o skali  i przesunięcia, przemieszczającego pewien punkt na jeden z pięciu punktów rozmieszczonych równomiernie na okręgu. Z lewej strony mamy  a z prawej  Zwiększając dalej  otrzymalibyśmy pięciokąt foremny.

Najbardziej znanymi fraktalami, które można otrzymać, iterując przekształcenia afiniczne, są paprocie Barnsleya, generowane przez układy czterech przekształceń, ale można też „hodować” w ten sposób inne rośliny; już dla  można uzyskać ciekawe efekty (Rys. 2).

Figury o skomplikowanym kształcie można zatem reprezentować przy użyciu bardzo niewielkiej ilości danych. Obrazek na rysunku 3  przedstawia figury wygenerowane za pomocą pewnej liczby IFS-ów, których opis składa się z dwustu kilkudziesięciu liczb rzeczywistych.

Rys. 2

Rys. 3

Rys. 4

Rys. 5

Rozwinięciem układów iterowanych przekształceń są algorytmy fraktalnej kompresji obrazów – są to jedne z najskuteczniejszych stosowanych obecnie technik kompresji. Umożliwiają one zapisywanie reprezentacji obrazów w małej ilości miejsca, a potem odtwarzanie tych obrazów z małym błędem. Oczywistą różnicą wobec IFS-ów jest przejście od określonych na płaszczyźnie funkcji przyjmujących tylko dwie wartości (punkt albo należy, albo nie należy do ustalonej figury) do funkcji przyjmujących wartości rzeczywiste. Tak samo, jak w przypadku fraktali generowanych przez IFS-y, gdzie krótki ciąg liczb reprezentujących poszczególne przekształcenia afiniczne umożliwia wygenerowanie obrazu figury o skomplikowanym kształcie, zapisane przez procedurę kompresji dane reprezentują pewne przekształcenie zwężające zbioru funkcji (obrazów) w siebie. Punktem stałym tego przekształcenia jest przybliżenie obrazu poddanego kompresji. Odtwarzanie obrazu polega na wykonaniu kilku lub kilkunastu iteracji tego przekształcenia.