Jak probíhá výpočet Mandelbrotovy množiny

22. 7. 2016 – Tomáš Prokopič

V tomto článku jsem si pro vás připravil takovou hru, během které pochopíte, jak probíhá výpočet Mandelbrotovy množiny. Pokud jste tady od někud přistáli a nevíte, co to Mandelbrotova množina je, přečtěte si prosím předchozí článek:

Pokud už víte, co to Mandelbrotova množina je, můžeme se rovnou pustit do práce! Budete potřebovat čtverečkovaný papír, kružítko, obyčejnou kalkulačku, tužku a gumu. Pokud nemáte čtverečkovaný papír nebo kružítko, stačí vám tiskárna u počítače (přichystal jsem pro vás šablonu v PDF ) a pokud nemáte kalkulačku, můžete použít Excel (nemusíte ho vůbec umět, stačí si opět stáhnout šablonu).

Začněte tak, že si uprostřed čtverečkovaného papíru nakreslete osy X a Y. Na papíře A4 je nejpraktičtější měřítko, kde jeden čtvereček odpovídá jedné osmině – t.j. 0,125. Osm čtverečků tedy bude odpovídat jedné, 16 čtverečků bude číslo dvě. Zaneste si na těch osách hodnoty pro 0, 1, 2, –1 a –2 takto:

Tak a teď si vezměte kružítko, zabodněte ho do středu a nakreslete kružnici s poloměrem 2 (t.j. s poloměrem 16 čtverečků):

Pokud nemáte čtverečkovaný papír nebo kružítko, stáhněte si tady šablonu v PDF a vytiskněte si ji na tiskárně.

Tak a teď si uvnitř této kružnice zvolte libovolný bod a namalujte si tužkou na jeho místě kroužek. V následujícím příkladu jsem zvolil bod se souřadnicemi: 

x = 0,5
y = 0,25.
 

Vy si však můžete zvolit libovolný jiný bod.

Tak a teď vypočítáme nové souřadnice pomocí tohoto vzorečku, který budeme stále opakovat a vkládat do něj hodnoty z přechozího výsledku:

X  = ( X předchozí · X předchozí ) – ( Y předchozí · Y předchozí ) + X výchozí
Y  = ( 2 · X předchozí · Y předchozí ) + Y výchozí

Dovolím si na tomto místě ještě poznámku, že vzoreček je ve skutečnosti ještě jednodušší, ovšem jeho jednodušší forma vyžaduje znalost komplexních čísel. Rozhodl jsem se tedy vzoreček pro začátek upravit tak, aby byl srozumitelnější a ve druhé polovině tohoto článku vám vysvětlím, jak jsem k tomu dospěl a ukážu vám ještě mnohem zjednodušenější verzi stejného výpočtu.

Takže začněme. V našem příkladu jsou naše výchozí hodnoty tyto:

X výchozí = 0,5
Y výchozí = 0,25

Při prvním opakování jsou předchozí hodnoty stejné jako výchozí. Dosadíme tedy hodnoty do vzorečku:

X = (0,5 · 0,5) – (0,25 · 0,25) + 0,5
Y = (2 · 0,5 · 0,25) + 0,25

Zadáme do kalkulačky – nezapomeňte nejprve spočítat součiny v závorkách a pak teprve odčítejte a sčítejte. Dostaneme tento výsledek:

X = 0,6875
Y = 0,5

Tento výsledek si na grafu označíme malým křížkem, nejlépe obyčejnou tužkou, aby šel snadno vygumovat:

A teď ten výsledek, který jsme získali znovu dosadíme do vzorečku, společně se souřadnicemi původního bodu:

X = (0,6875 · 0,6875) – (0,5 · 0,5) + 0,5
Y = (2 · 0,6875 · 0,5) + 0,25

Spočítáme na kaluklačce a dostaneme tento výsledek:

X = 0,72265625
Y = 0,9375

Na grafu si bod opět označíme křížkem :

Výsledné hodnoty znovu vložíme do vzorečku a výpočet opakujeme pořád dokola – tak dlouho, dokud nám křížek nevyskočí mimo kružnici. Už v tuto chvíli je hodnota X zakokrouhlená a jde o to kolik vaše kalkulačka zvládne destinných míst, takže se v posledních destinných místech můžeme mírně rozcházet, ale to nemá pro tuto ukázku velký vliv.

Takže pro další opakování dosadíme do vzorečku:

X = (0,72265625 · 0,72265625) – (0,9375 · 0,9375) + 0,5
Y = (2 · 0,72265625 · 0,9375) + 0,25

Výsledek bude:

X = 0,143325806
Y = 1,604980469

Zakreslíme bod na grafu a zjistíme, že je stále ještě uvnitř kružnice:

Takže to opakujeme ještě jednou a znovu do vzorečku vložíme hodnoty, které nám vyšly:

X = (0,143325806 · 0,143325806) – (1,604980469 · 1,604980469) + 0,5
Y = (2 · 0,143325806 · 1,604980469) + 0,25

Výsledek bude:

X = –2,055420018
Y = 0,710070238

Když teď zakreslíme tento výsledek do grafu, zjistíme, že bod již vyskočil mimo kružnici. Pro výchozí hodnoty X = 0,5 a Y = 0,25 tedy výsledek vyskočí mimo kružnici po 4 opakováních stejného výpočtu:

A zde je pro rekapitulaci ještě tabulka s jednotlivými mezivýsledky:

XY
1. opakování0,68750,5
2. opakování0,722656250,9375
3. opakování0,1433258060,604980469
4. opakování–2,0554200180,710070238

Protože nám bod po několika opakováních vyskočil mimo kružnici, tak necháme kroužek (v místě kde je na grafu námi zvolený výchozí bod) bílý a vygumujeme křížky. A zkusíme si vzít jiný bod uvnitř kružnice a celé to spočítat znovu.

Tentokrát zvolíme jako výchozí bod pro změnu tento:

X výchozí = –0,5
Y výchozí = 0,25

V podstatě jsme jenom u X dali záporné znaménko a výsledky tentokrát vypadají úplně jinak. Po 4 opakováních nám žádný bod nevyskočil mimo kružnici. Radši se ani netrapte s kalkulačkou – bod by nevyskočil ani po 10 opakováních, ani po 1000 opakováních. Pro výchozí hodnoty X = –0,5 a Y = 0,25 můžete výše uvedený výpočet opakovat donekonečna a bod nikdy nevyskočí mimo kružnici. V takovém případě vybarvíme kroužek na černo.

Tady je tabulka s prvními 10ti výsledky:

XY
1. opakování-0,31250
2. opakování-0,402343750,25
3. opakování-0,4006195070,048828125
4. opakování-0,3418881970,210877001
5. opakování-0,4275815710,105807285
6. opakování-0,3283691820,15951751
7. opakování-0,4176195160,145238731
8. opakování-0,3466882290,128690942
9. opakování-0,3963686310,16076873
10. opakování-0,3687384930,122552637

Všimněte si, že křížky zakreslené v grafu pokrývají jenom jednu malou oblast.

Existují prostě dva typy bodů. Jedny při opakování toho výpočtu dříve nebo později vyskočí mimo kružnici o poloměru 2 a jakmile vyskočí, tak s každým dalším opakováním výpočtu se budou více a více vzdalovat středu a pak jsou tu body, které budou donekonečna uvězněny uvnitř kružnice a  nikdy se od středu nevzdálí na větší vzdálenost než 2.

Takže ten výpočet výše (pokud máte dost času) můžete zopakovat pro každý bod na čtverečkové mřížce. Je nutné stanovit si nějaký maximální počet opakování (čím víc, tím je to přesnější). Pro začátek bude bohatě stačit třeba 10 opakování. Pokud bod ani po 10 opakováních nevyskočí mimo kružnici, namalujete ho černě, pokud vyskočí, tak ho ponecháte bílý.

Vzhledem k tomu, že počítat tohle na kalkulačce by bylo šílené, připravil jsem pro vás tuto excelovou šablonu:

Nemusíte s Excelem vůbec umět pracovat. Stačí, když si to stáhnete, otevřete a pak do červeně orámovaných políček vyplníte souřadnice bodu, který chcete zjistit (možná se vás ještě excel zeptá o povolení provádět změny, tak dejte ano). Automaticky se vám dole zobrazí tabulka s prvními 20ti iteracemi (tak se odborně nazývá ono opakování výpočtu) a zároveň se na pravé straně zobrazí graf s výsledky. Hned na první pohled uvidíte, jestli daný bod vyskočil mimo kružnici nebo všech 20 opakování výpočtu odolal a zůstal uvnitř.

Celý tento postup je tedy nutné opakovat postupně pro všechny body v mřížce, pokud výchozí bod po zvoleném počtu opakování výpočtu nevyskočí mimo kružnici, označíte ho černě, pokud vyskočí, pak bíle. Pokud se vám povede postupně si proklepnout všechny body uvnitř kružnice, měli byste dostat takovýhle obrázek:

No a to je Mandelbrotova množina! Správněji řečeno, ty černé body jsou ty, co patří do Mandelbrotovy množiny. Jsou to body, které při opakování výše uvedeného výpočtu nikdy nevyskočí mimo kružnici s poloměrem 2. Výsledný obrázek je ale ve velmi malém rozlišení a pro každý bod byl výpočet opakován 20x. Pokud si ho necháte počítačem spočítat v mnohanásobně větším rozlišení a s větším počtem opakování, bude vypadat takto:

Pro toto zobrazení byl výpočet pro každý bod zopakován 250x. 

A teď přidáme barvy...

Možná si teď říkáte, že tenhle obrázek je jenom černobílý a že na něm nejsou vidět ty nádherné barevné detaily. Nebojte, barvy budou! V přechozím výpočtu jsme postupovali tak, že jsme si zvolili nějaký maximální počet opakování a pokud bod nevyskočí mimo kružnici, namalovali jsme ho černě. Body které vyskočily jsme namalovali bíle – to ale stačí změnit tak, že si zvolíme barevnou škálu pro náš maximální počet opakování.

Takže například pokud bod vyskočí už po jedné iteraci (opakování) výpočtu, vybarvíme ho žlutě. Pokud vyskočí po 25 iteracích namalujeme ho oranžově a pokud až po 99ti, tak modře. Pokud bod nevyskočí ani po 100 opakováních (což jsme si v tomto případě zvolili jako maximální počet opakování), namalujeme ho černě. No a ty hodnoty mezi tím budou mít nějaké přechodové barvy. Nejlépe to právě vypadá, když barvy z té barevné škály plynule přecházejí. Barevnou škálu si však můžeme zvolit vlastní. Můžeme použít všechny barvy duhy nebo jenom určitě odstíny červené. To už je na našem estetickém cítění. Tak jako tak ale platí, že všechny body, které mají stejnou barvu vyskočily po stejném počtu iterací. Černě jsou tedy zobrazeny body, které patří do Mandelbrotovy množiny a barevně body, které do ní nepatří, nicméně jejich barva vyjadřuje vzdálenost těchto bodů od množiny. Je to podobné, jako když barvy na mapě vyjadřují nadmořskou výšku. No a pokud tedy budeme vybarvovat body podle toho po kolika opakováních vypadly, dostaneme takovýhle obrázek:

Tady už jsou vidět mnohem lépe nepatrné detaily na okraji. Pokud si nějakou oblast zvětšíme, detaily budou názornější a barvy dostanou smysl:

Komplexní čísla

Tak teď už chápete, jakým způsobem se vykresluje Mandelbrotova množina a pokud vám to takhle stačí, tak nemusíte číst dál. Pokusím se teď vysvětlit ještě mnohem jednodušší vzoreček, ze kterého ten výpočet, který jsme počítali vychází. K jeho pochopení však budeme potřebovat znát tzv. komplexní čísla.

Asi nikdo nebude protestovat, když budu tvrdit, že dva krát dva jsou čtyři:

2 · 2 = 4

Ovšem jak je to v případě, že násobíme dvě záporná čísla?

–2 · –2 = 4

Ve škole nás učili, že když se vynásobí dvě záporná čísla, vyjde číslo kladné. To je ale jenom polovina pravdy. Pro naprostou většinu potřeb reálného světa se to opravdu hodí, aby to tak bylo. Můžeme si kladná čísla představit jako zisk a záporná jako ztrátu. Pokud získáme zisk (kladné · kladné) dostaneme zisk. Pokud získáme ztrátu (kladné · záporné) máme ztrátu. Pokud ale ztratíme ztrátu (záporné · záporné) máme vlastně zisk. Tento způsob násobení záporných čísel je ale nesymetrický – když násobíme dvě kladná nebo dvě záporná čísla, tak v obou případech dostaneme číslo kladné, jako kdyby záporná čísla byla v nějaké nevýhodě.

To co jsme si tady popsali se týká tzv. reálných čísel, to jsou čísla se kterými počítáme v běžném životě. Existují ale i čísla, tzv. imaginární, pro která platí jiná pravidla násobení a jsou naprosto relevantní pro popis některých jevů, například týkajících se vln. Aby se to nepletlo, tak imaginární čísla se zapisují jako číslo a písmenko i. Pro násobení dvou záporných imaginárních čísel platí následující vztah:

–2i · –2i = –4

To písmenko "i" totiž značí tzv. imaginární jednotku, pro kterou platí:

i 2 = –1

Druhá mocnina znamená, že dané číslo se násobí samo sebou, takže se to zapsat pro lepší názornost i takto:

i · i = –1

Ovšem reálná čísla (ta která běžně používáme) a imaginární čísla se dají zkombinovat. Těmto zkombinovaným číslům se říká komplexní čísla. Každé komplexní číslo se tedy skládá z jednoho čísla reálného a jednoho imaginárního. Komplexní číslo je tedy například:

2 + 4i

Reálná část tohoto čísla je 2 a imaginární složka je 4. Pro komplexní čísla můžeme používat proměnné, ovšem je třeba si uvědomit že pod jednou proměnnou se pak vždy skrývají ty dvě složky – reálná a imaginární. Takže například si můžeme určit komplexní číslo Z:

Z = 2 + 4i

Komplexní čísla jsou tedy něco jako manželství. Každé číslo je složeno ze dvou čísel – reálného a imaginárního. Dají se zakreslit na souřadnicové ose, akorát těm osám neříkáme X a Y, ale označují se R a I. 

Komplexní čísla mají zajímavé vlastnosti, které jsou vidět, když je zakreslíme jako body v grafu se souřadnicemi R a I. Například pokud násobíme dvě komplexní čísla, dochází k rotaci, výsledek je jakoby otočený – sčítají se nejen vzdálenosti od středu, ale i úhly. Komplexní čísla mají velké užití všude tam, kde je potřeba analyzovat vlny – a jak jistě tušíte, vlnovou podstatu má skoro všechno okolo nás. Používají se také při počítání s vektory. Ale to jsem teď trošku odbočil, pojďme zpátky k našemu výpočtu.

Teď už se můžeme konečně dostat k tomu nejjednoduššímu možnému zápisu pro výpočet Mandelbrotovy množiny:

Z n = (Z n-1 ) 2 + C

Nic víc, nic míň! Ovšem pod každou proměnnou je teď pokaždé dvojice čísel, jelikož se jedná o čísla komplexní.

n značí iteraci, kterou právě počítáme (o kolikáte opakování výpočtu se jedná).
Z n je tedy bod, který právě počítáme.
Z n-1 je bod z předchozího opakování výpočtu.
C je výchozí bod.

Dosaďme si tedy do tohoto vzorečku souřadnice, které jsme už počítali na začátku tohoto článku.

Pro připomenutí, ty souřadnice byly:

X výchozí = 0,5
Y výchozí = 0,25

Tentokrát to ale zapíšeme jako

C = 0,5 + 0,25i

Pro první opakování je Z = C.

Takže to dosadíme do vzorečku:

Z = (0,5 + 0,25i) 2 + 0,5 + 0,25i

Možná si ještě vzpomenete na tuto poučku ze střední školy:

(a + b) 2 = a 2 + 2ab + b 2

Použijeme to tedy v našem vzorečku:

Z = 0,5 2 + (2 · 0,5 · 0,25i) + 0,25i 2 + 0,5 + 0,25i

vynásobíme co máme v závorce:

Z = 0,5 2 + 0,25i + 0,25i 2 + 0,5 + 0,25i

teď umocníme ty dvě mocniny, co tam máme a u toho využijeme poučku o imaginární jednotce o které jsem tady o pár odstavců dříve psal:

i 2 = –1

tudíž:

ai 2 = –a 2

takže jdeme na to:

Z = 0,25 + 0,25i – 0,0625 + 0,5 + 0,25i

no teď to jenom posčítáme:

Z = 0,6875 + 0,5i

Heuréka! Dospěli jsme trošku jinou početní operací ke stejnému vysledku, jako v přechozím případě a že tedy souřadnice nového bodu jsou:

X = 0,6875
Y = 0,5

Odvození vzorečku pro X a Y

Pro náročnější čtenáře si ještě můžeme ukázat, jak se upravil vzoreček tak aby se v něm počítalo pouze s reálnými čísly, tak jako v první půlce tohoto článku.

Nejprve si zavedeme zkratky, ať se v tom lépe vyznáme:

X v = X výchozí
Y v = Y výchozí
X p = X předchozí
Y p = Y předchozí

Tak a teď si dosadíme do vzorečku tyto hodnoty:

C = X v + Y v i
Z n-1 = X p + Y p i

Vzoreček byl tedy:

Z n = (Z n-1 ) 2 + C

Takže dosadíme:

Z n = ( X p + Y p i ) 2 + X v + Y v i

Teď upravíme podle poučky  (a + b) 2 = a 2 + 2ab + b 2 :

Z n = X p 2 + 2 · X p · Y p i + Y p i 2 + X v + Y v i

upravíme podle poučky ai 2 = –a 2 :

Z n = X p2 + 2 · X p · Y p i – Y p 2 + X v + Y v i

No a teď si z toho vyzobeme pouze reálnou část, t.j. pouze členy, které neobsahuji imaginární jednotku "i" a tím získáme výslednou souřadnici X:

X = X p 2 – Y p 2 + X v

Protože jsem nechtěl čtenáře na začátku článku odrazovat mocninami, tak vzhledem k tomu, že a 2 = a · a , tak ještě to X můžeme rozepsat takto:

X = (X p · X p ) – (Y p · Y p ) + X v

A teď z toho naopak vybereme pouze členy, které obsahují imaginární jednotku "i" a získáme souřadnici Y (akorát to "i" už z toho vynecháme):

Y = 2 · X p · Y p + Y v

No a máme výpočet pro X a Y. Hurá! Pro absolutní názornost ještě nahradíme ty zkratky a získáme stejný vzoreček, jako na záčátku tohoto článku:

X  = ( X předchozí · X předchozí ) – ( Y předchozí · Y předchozí ) + X výchozí
Y  = ( 2 · X předchozí · Y předchozí ) + Y výchozí

Líbil se vám článek?





Další blogy

Jak jsem zdobil dort
Jak jsem zdobil dort
Je pátek pozdě večer. Zítra má náš Míša narozeniny. Je bezpodmínečně nutné ještě dokázat vytvořit z cukrářských surovin velký obličej Spidermana na dort. Je to věc největšího významu. Velké drama právě začíná...
Tajemství hudební improvizace
Tajemství hudební improvizace
Naprosto přirozenou a zábavnou cestou se může na hudební nástroj naučit hrát skoro každý bez cizí pomoci. Improvizace se vůbec nemusí složitě učit a trénovat. Jak? Podělím se s vámi o to tajemství.
Brouk, na jehož krovkách kvete celý vesmír
Brouk, na jehož krovkách kvete celý vesmír
Představte si, že existuje naprosto jednoduchý matematický výpočet, jehož výsledkem je tajemný graf, který v sobě obsahuje nekonečně komplikovaný vesmír tvarů. Tvarů, které jsou v přírodě všude okolo nás a které jsou uložené hluboko v našem podvědomí.
Jak jsem se dostal k hudbě
Jak jsem se dostal k hudbě
Přečtěte si příběh o tom, jak jsem dlouhé roky hrál tajně na piano jen sám pro sebe a jak se mi změnil život, když jsem se rozhodl nenechat si to pro sebe a podělit se s lidmi o hudbu, která skrze mě proudí.