wz

Mandelbrotova množina(M-set)

Mandelbrotova množina, stejně jako Juliovy množiny, byla objevena při analýze některých dynamických systémů. Analýza dynamických systémů se zabývá otázkou budoucího stavu systému, pokud iterativně provádíme výpočet s tou samou funkcí (resp. skupinou funkcí).

Některé výsledky z výzkumu těchto systémů byly publikovány již počátkem minulého století (samozřejmě bez pomoci počítačů). Těmito systémy se zabývali především matematikové Gaston Julia (1893-1978) a Pierre Fatou (1878-1929). Na jejich práci navázal v sedmdesátých letech minulého století matematik Benoit Mandelbrot. Jako součást své práce využil Benoit Mandelbrot možností počítačové grafiky. Ve stejné době byly vytvořeny první obrazy fraktálu dnes nazývaného Mandelbrotova množina. První obrázky byly, vzhledem k dané době, pouze černobílé, vzbudily však velký zájem jak mezi odbornou, tak i laickou veřejností.

Mandelbrotova množina je vytvořena pomocí jednoduchého dynamického systému, který je založený na iteraci funkce komplexní paraboly:
zn+1=zn2+c
kde proměnné z a c leží v komplexní rovině. V průběhu výpočtu se hodnota z postupně mění, zatímco hodnota c zůstává konstantní. Celý iterační proces začíná s určitou startovní hodnotou z0, takže systém postupně generuje sekvenci hodnot zk, které nazýváme orbit. Postup si ukážeme na prvních čtyřech iteracích:
z1=(z0)2+c
z2=((z0)2+c)2+c
z3=(((z0)2+c)2+c)2+c
z4=((((z0)2+c)2+c)2+c)2+c



Při práci se systémem popsaným v předchozím textu nás zajímá, zda pro danou startovní hodnotu z0 a konstantu c body zk konvergují či divergují. Ukazuje se, že pro některé počáteční hodnoty nastává také oscilace - hodnoty zk se opakují s určitou periodou, to znamená, že zk=zk+i, kde i je perioda oscilace. Bližším studiem vlivu počátečních podmínek na budoucí stav systému se zabýval také Benoit Mandelbrot.

Mandelbrot se omezil na případ, kdy počáteční hodnota z0 je nulová a mění se pouze konstanta c. Iterativním výpočtem vzniknou pouze orbity nuly. Orbity nuly lze podle jejich vlastností rozdělit do dvou kategorií:

* pro některé hodnoty c je orbit konečný, tzn. všechny hodnoty zk jsou konečné. Do této kategorie spadají také hodnoty, které oscilují.
* pro další hodnoty c je orbit nekonečný, tzn. po určité době rostou hodnoty zk nade všechny meze.

Mandelbrotova množina je definována jako množina všech komplexních čísel c, které produkují konečný orbit nuly, tedy:
kde Pcn(0) znamená hodnotu zn pro danou konstantu c a z0=0.

Na obrázku je ukázán příklad pro dvě počáteční hodnoty c (resp. z0, protože po první iteraci je c rovno z0). První orbit je konečný, zatímco hodnoty druhého orbitu po několika prvních iteracích rostou nade všechny meze.

Test na nekonečnost orbitu

Při testu na nekonečnost orbitu použijeme důkazu, že pro |c|<=|z| a |z|>2 posloupnost diverguje. Využije se přitom trojúhelníkové nerovnosti pro komplexní čísla |a+b|>=|a|-|b|, kde za a dosadíme z*z a za b komplexní konstantu c: |z*z+c|>=|z*z|-|c|=(|z|)2-|c|.

Je nutné najít minimalní hodnotu |z|, při jejímž překročení je |z*z+c|>|z|. Nazvěme tuto hodnotu r. Potom r*r-|c|=r resp. r*r-r-|c|=0 a dále z řešení kvadratické rovnice vyplývá r=(1+(1+4|c|)1/2)/2.

Známe tedy hodnotu r. Jestliže je |z| větší než r, systém diverguje. Pokud iterace začíná s hodnotou z=0, je po první iteraci z=c. V předchozích vzorcích můžeme r nahradit |c| a dostaneme:
|c|*|c|-2|c|=0 tedy |c|=2 resp. |z|=2 protože z=c.

Posloupnost tedy pro |z|>2 skutečně diverguje. V průběhu iteračního výpočtu tedy stačí testovat, zda je velikost |zk|>2.

Podmínka pro divergenci posloupnosti mimo jiné také znamená, že všechny body Mandelbrotovy množiny leží v komplexní rovině uvnitř kružnice o poloměru 2. Je to dáno tím, že pro |c|>2 je po první iteraci také |z|>2 a z podmínek uvedených výše vyplývá, že posloupnost diverguje.

Výpočet bodů ležících v Mandelbrotově množině

Z předchozího textu vyplývá, že všechny body Mandelbrotovy množiny mají absolutní hodnotu menší než 2. Také víme, že jestliže v průběhu iteračního procesu absolutní hodnota z překročí 2, posloupnost diverguje a počítaný bod tudíž neleží v Mandelbrotově množině.

Opačný test, tj. test na konvergenci posloupnosti nelze přímo provést. Používá se proto metoda, při které se zvolí dostatečně velký počet iterací, přičemž v každém kroku je testováno, zda absolutní hodnota z nepřekročí 2. Pokud tato možnost nastane, bod uvnitř Mandelbrotovy množiny neleží. Pokud proběhne výpočet všech iterací aniž by absolutní hodnota z překročila 2, je počítaný bod prohlášen za prvek Mandelbrotovy množiny. Tato metoda je sice nepřesná, ale lze ji v podstatě libovolně zpřesňovat zvyšováním maximálního počtu iterací. Hodnota 2 použitá v testu se v literatuře nazývá bailout.

Postup při výpočtu bodů ležících v Mandelbrotově množině lze zapsat pomocí jednoduchého algoritmu. Vstupem algoritmu je komplexní číslo c a konstanta určující maximální počet iterací MaxIter.

1. nastav iter:=0
2. nastav z:=0
3. pokud iter < MaxIter prováděj smyčku:
4. nastav z:=z2+c
5. jestliže |z|>2 bod neleží v Mandelbrotově množině; konec
6. nastav iter:=iter+1
7. konec smyčky
8. bod leží uvnitř Mandelbrotovy množiny; konec

Tento algoritmus lze velmi jednoduše implementovat s tím, že proměnné z a c jsou komplexní čísla. Protože ve většině programovacích jazyků nejsou komplexní čísla zavedena jako základní datové typy, pomůžeme si tím, že každé komplexní číslo reprezentujeme jeho reálnou a imaginární složkou. Proto např. z bude reprezentováno dvojicí zx a zy a c bude reprezentováno dvojicí cx a cy.

Absolutní hodnotu |z| lze rozepsat jako sqrt(zx*zx+zy*zy), kde sqrt() je funkce odmocniny. V reálných programech není použit přímo výpočet absolutní hodnoty, protože vyčíslení odmocniny je časově velmi náročné. Podmínku sqrt(zx*zx+zy*zy)>2 lze umocnit a použít novou podmínku, kde není potřeba provádět výpočet odmocniny: zx*zx+zy*zy>4. Hodnoty zx*zx a zy*zy je vhodné předpočítat do nových proměnných, protože se v jednou iteračním kroku používají na dvou místech a není nutné počítat stejný výraz dvakrát.

Výraz z:=z2+c lze rozepsat na reálnou a imaginární část:
zx'=zx*zx-zy*zy+cx
zy'=2*zx*zy+cy
Aby nebylo nutné používat dvou nových proměnných zx' a zy', použijí se již předpočítané mocniny reálné a imaginární složky z. Také je vhodné prohodit oba výrazy, aby nebylo nutné zavádět nové pomocné proměnné:
zx2=zx*zx
zy2=zy*zy
zy=2*zx*zy+cy
zx=zx2-zy2+cx
Hodnoty v proměnných zx2 a zy2 budou použity při testu zx2+zy2>4.

Nyní můžeme celý algoritmus pro výpočet bodů Mandelbrotovy množiny přepsat do programovacího jazyka. Jako příklad je uveden zápis v jazyce C.

/*
* parametry teto funkce je komplexni cislo "c" pro ktere probiha test
*/
int MandelbrotTest(double cx, double cy)
{
double zx,zy,zx2,zy2,cx,cy; // komplexni promenna "z"
int iter; // pocet iteraci

zx=0; // vynulovat komplexni promennou "c"
zy=0;

iter=0; // vynulovat pocitadlo iteraci

do { // iteracni smycka
zx2=zx*zx; // zx^2
zy2=zy*zy; // zy^2
zy=2.0*zx*zy+cy;
zx=zx2-zy2+cx; // z:=z^2+c
iter++; // zvysit pocet iteraci
} while (iter<maxiter && (zx2+zy2)<4.0);// test na poc. iteraci a bailout

if (iter==maxiter) // bod je uvnitr Mandelbrotovy mnoziny
return LEZI_UVNITR;
else // bod je vne Mandelbotovy mnoziny
return LEZI_VNE;
}
Výše uvedený algoritmus lze přímo použít pro vykreslení Mandelbrotovy množiny. Bílé pixely reprezentují body v komplexní rovině, jež neleží v Mandelbrotově množině, černé pixely naopak reprezentují body v Mandelbrotově množině ležící. Symetrie Mandelbrotovy množiny okolo reálné osy je způsobena tím, že změna znaménka cy způsobí pouze změnu znaménka proměnné zy nikoliv zx. Na výpočet absolutní hodnoty |z| nemají znaménka reálné a imaginární složky žádný vliv. Funkce MandelbrotTest je volaná pro každý počítaný (resp. zobrazovaný) pixel. Při větších velikostech pixelů může dojít ke znatelnému prodloužení výpočtu z důvodu častého volání této funkce. Proto je výhodnější vložit tělo funkce MandelbrotTest přímo do hlavní výpočetní smyčky programu, kde se provádí nastavení jednotlivých pixelů.

Vykreslení Mandelbrotovy množiny

Mandelbrotovu množinu lze vykreslit velmi jednoduše pomocí vztahů uvedených výše.Stačí provést převod pozice pixelu na obrazovce na hodnotu komplexní konstany c. Pro každý pixel se tedy vypočte, zda jemu příslušející konstanta c způsobí růst orbitu nuly nade všechny meze. Pokud tomu tak je, pixel neleží uvnitř Mandelbrotovy množiny, v opačném případě v ní leží.

Pokud pixel neleží uvnitř Mandelbrotovy množiny, je možné ho obarvit v závislosti na počtu iterací, které proběhnou, dokud hodnota |zn| nepřekročí hodnotu 2. Vzniknou tak izoplochy, tj. souvislé plochy v obrázku, jejichž barva odpovídá počtu iterací nutných pro zjištění, že pixel neleží uvnitř Mandelbrotovy množiny.

Celý postup vykreslování Mandelbrotovy množiny je ukázán na jednoduchém programu, který počítá body Mandelbrotovy množiny v obdélníku daném dvěma krajními body v komplexní rovině: -2-1.5i a 2+1.5i. Program nejdříve ohodnotí každý pixel dle toho, zda leží uvnitř či vně Mandelbrotovy množiny, popřípadě pixel obarví podle počtu iterací nutných k rozhodnutí testu. Potom program výsledný obrázek uloží ve formátu BMP na disk.

Zdrojový text programu je dostupný zde, popř. jako HTML soubor s obarvením syntaxe. Program byl otestován překladačem Borland C++ verze 5.5. Níže je vidět výstup tohoto programu.


Vykreslení detailů Mandelbrotovy množiny

Jestliže chceme podrobněji vykreslit detaily z Mandelbrotovy množiny, stačí vhodně nastavit dva krajní body (např. levý horní a pravý dolní roh) v komplexní rovině, které ohraničují obrazec, který bude vykreslen. Další možností, která je pro uživatele názornější, je zvolit střed vykreslování a měřítko zvětšení popř. zmenšení oproti celé množině. Mandelbrotova množina je většinou vykreslována jako množina bodů ležících v obdélníku s krajními body -2-1.5i, -2+1.5i, 2-1.5i a 2+1.5i. Funkce pro přepočet krajních bodů při zadání středu zobrazení a měřítka může vypadat např. takto:
/*
* funkce pro vypocet pozice rohu vykreslovaneho obrazku ze zadaneho stredu
* a meritka
*/
void CalcCorner(double xpos, double ypos, double scale,
        double *x1, double *y1, double *x2, double *y2)
{
*x1=xpos-2.0*scale;
*y1=ypos-1.5*scale;
*x2=xpos+2.0*scale;
*y2=ypos+1.5*scale;
}

Parametry xpos a ypos určují, jaké souřadnice v komplexní rovině bude mít střed vykreslovaného obrázku. Parametr scale určuje měřítko vykreslení. Pokud bude hodnota měřítka větší než 1, výsledný obrazec bude oproti původnímu obrázku zmenšený, protože se zvětší vzdálenost mezi souřadnicemi okrajových bodů v komplexní rovině. Pokud bude naopak parametr scale menší než 1, dojde k přiblížení výsledného obrazce. Výsledkem výpočtu jsou hodnoty v proměnných x1, x2, y1, y2, které určují hranici obdélníku v komplexní rovině, ve které se nachází počítaný obrazec.

Výsledné bitmapy jsou zobrazeny na následujících obrázcích.

Animace "průletu" Mandelbrotovou množinou

Předcházející program můžeme upravit tak, že se bude hodnota měřítka popř. střed vykreslovaného obrazce kontinuálně měnit. Tímto způsobem lze vytvořit působivou animaci "průletu" kamery Mandelbrotovou množinou. Výsledná animace se vytvoří tak, že se postupně spočítá množství obrázků Mandelbrotovy množiny, přičemž každý obrazec bude mít nastavené jiné parametry výpočtu. Obrázky se následně seřadí do sekvence a vytvoří se z nich animace, tj. postupný přechod mezi obrázky. Animaci lze uložit např. ve formátu Video for Windows (AVI), nebo MPEG.

Jako ukázka jsou připraveny dvě animace ve formátu MPEG 1. Pro vytvoření výsledných animací z jednotlivých snímků byl použit program cmpeg, což je softwarový kodek pro MPEG 1 soubory. Výsledné animace lze přehrát např. pomocí Windows Media Playeru, nebo ovládacího prvku Active Movie. Velikost jednotlivých snímků v animaci je 320x240 pixelů a rychlost přehrávání je nastavena na 25 snímků za sekundu.

# první animace (velikost souboru je 347 404 byte)
# druhá animace (velikost souboru je 1 334 763 byte)

Více informací získáte ze skvělých článků Pavla Tišnovského například na této URL: http://www.root.cz/clanky/fraktaly-v-pocitacove-grafice-xiii


Nahoru


Michal Hladik © 2006