Hlavní navigace

Fraktály v počítačové grafice XVIII

Pavel Tišnovský 22. 2. 2006

V osmnáctém pokračování seriálu o fraktálech používaných (nejenom) v počítačové grafice si vysvětlíme vztah mezi Mandelbrotovou množinou a známou konstantou π. Také si řekneme, jaké číselné řady (kódované do geometrické podoby) je možné v Mandelbrotově množině nalézt.

Obsah

1. Mandelbrotova množina a konstanta π
2. Výpočet π z Mandelbrotovy množiny v okolí bodu –0,75+0i
3. Výpočet π z Mandelbrotovy množiny v okolí bodu +0,25+0i
4. Mandelbrotova množina a posloupnost přirozených čísel
5. Mandelbrotova množina a Fibonacciho posloupnost
6. Literatura a odkazy na Internetu
7. Obsah dalšího pokračování tohoto seriálu

1. Mandelbrotova množina a konstanta π

Mandelbrotova množina je známá především jako nejkomplexnější útvar, který je možné v rovině zakreslit. Kromě toho se však ukazuje, že zdánlivě velmi jednoduchý iterační vzorec zn+1=zn2+C neslouží „pouze“ k vykreslování esteticky pěkného fraktálu, ale že se v geometrické struktuře Mandelbrotovy množiny skrývají známé číselné řady a dokonce i několik univerzálních matematických konstant. Ve druhé a třetí kapitole si ukážeme, jakým způsobem je možné z Mandelbrotovy množiny vypočítat číslo π, tj. podíl mezi obvodem kružnice a jejím průměrem. V dalších kapitolách (čtvrté a páté) si řekneme, jak je možné v Mandelbrotově množině nalézt číselné řady zakódované do jejích geometrických tva­rů.

2. Výpočet π z Mandelbrotovy množiny v okolí bodu –0,75+0i

První oblastí Mandelbrotovy množiny, ve které je možné nalézt číslo π, je okolí bodu -0,75+0i – viz první ilustrační obrázek. Jedná se o jediný bod na přímce s rovnicí x=-0,75, který leží uvnitř Mandelbrotovy množiny, všechny ostatní body na této přímce po určitém počtu iterací způsobí divergenci posloupnosti zn. Pokud budeme zaznamenávat počet iterací nutných pro rozhodnutí divergence (tj. pro platnost testu |zn|>2.0) u bodů -0,75+δi, kde δ se bude blížit k nule, přijdeme na zajímavý úkaz: počet iterací vynásobený hodnotou δ se bude přibližovat ke známému číslu π! Níže je ukázán program, který číslo π právě popsaným způsobem počítá, hodnota δ (v programu reprezentovaná přímo proměnnou cy) se postupně snižuje od hodnoty 1.0 směrem k nule. Počet iterací nutných pro rozhodnutí divergence se zvyšuje a vypočtená hodnota π=δ×iter se stále více blíží k matematické konstantě.

fractals18_1
Obrázek 1: Oblast, ve které se počítá číslo π podle první metody
// --------------------------------------------------------------------
// Výpočet konstanty PI pomocí iteračního cyklu platného pro
// Mandelbrotovu množinu. Vyžaduje se překladač s třicetidvoubitovým
// datovým typem int a úplnou podporou reálných čísel ve dvojité
// přesnosti.
// --------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

#define PI 3.14159265358979323846

void mandelbrot_pi1(void)
{
    double zx, zy;                      // složky komplexní proměnné Z
    double cx, cy;                      // složky komplexní konstanty C
    double zx2, zy2;                    // druhé mocniny složek Z
    int    i;                           // počitadlo iterací
    const int maxiter=1000*1000*1000;   // maximální počet iterací

    cx=-0.75;                           // nastavení hodnoty komplexní
    cy=1.0;                             // konstanty C
    do {
        zx=zy=0.0;                      // bude se počítat orbit nuly
        for (i=0; i<maxiter; i++) {     // iterační smyčka
            zx2=zx*zx;                  // výpočet nové hodnoty Z
            zy2=zy*zy;
            if (zx2+zy2>4.0) break;     // podmínka divergence
            zy=2.0*zx*zy+cy;
            zx=zx2-zy2+cx;              // Z(i+1)=Z(i)^2+c
        }
                                        // tisk výsledku
        printf("%10.8f \t %8d \t %14.10f %14.10f %10.6f\n",
                cy,                     // nastavená imaginární složka C
                i,                      // dosažený počet iterací
                i*cy,                   // počet iterací vynásobený imag.
                                        // složkou konstanty C
                i*cy-PI,                // absolutní chyba
                100.0*(i*cy-PI)/PI);    // relativní chyba
        cy/=2.0;                        // další přiblížení k nulové
    } while (cy>1.0E-7);                // hodnotě imaginární složky C
}

int main(void)
{
    mandelbrot_pi1();                   // výpočet PI
    return 0;
}

// -------------------------------------------------------------------- 

Ve funkci mandelbrot_pi1() je mimo vlastního výpočtu proveden i tisk vypočtených hodnot spolu s absolutní a relativní chybou (odchylkou) od čísla π uloženého s přesností na dvacet desetinných míst. Program pro svou korektní činnost vyžaduje minimálně třicetidvoubitové prostředí s podporou reálných čísel uložených ve dvojité přesnosti (to platforma x86 samozřejmě už minimálně jedno desetiletí zaručuje). Výsledky běhu programu jsou zobrazeny v následující tabulce:

Výsledky běhu
Hodnota cy Počet iterací Vypočtené π Absolutní chyba Relativní chyba
1.00000000 3 3.0000000000  –0.1415926536  –4.507034%
0.50000000 6 3.0000000000  –0.1415926536  –4.507034%
0.25000000 13 3.2500000000 0.1084073464 3.450713%
0.12500000 26 3.2500000000 0.1084073464 3.450713%
0.06250000 51 3.1875000000 0.0459073464 1.461276%
0.03125000 101 3.1562500000 0.0146573464 0.466558%
0.01562500 202 3.1562500000 0.0146573464 0.466558%
0.00781250 403 3.1484375000 0.0068448464 0.217878%
0.00390625 805 3.1445312500 0.0029385964 0.093538%
0.00195313 1609 3.1425781250 0.0009854714 0.031369%
0.00097656 3217 3.1416015625 0.0000089089 0.000284%
0.00048828 6435 3.1420898438 0.0004971902 0.015826%
0.00024414 12869 3.1418457031 0.0002530495 0.008055%
0.00012207 25737 3.1417236328 0.0001309792 0.004169%
0.00006104 51473 3.1416625977 0.0000699441 0.002226%
0.00003052 102945 3.1416320801 0.0000394265 0.001255%
0.00001526 205889 3.1416168213 0.0000241677 0.000769%
0.00000763 411775 3.1415939331 0.0000012795 0.000041%
0.00000381 823551 3.1415977478 0.0000050942 0.000162%
0.00000191 1647100 3.1415939331 0.0000012795 0.000041%
0.00000095 3294199 3.1415929794 0.0000003258 0.000010%
0.00000048 6588398 3.1415929794 0.0000003258 0.000010%
0.00000024 13176795 3.1415927410 0.0000000874 0.000003%
0.00000012 26353590 3.1415927410 0.0000000874 0.000003%

3. Výpočet π z Mandelbrotovy množiny v okolí bodu +0,25+0i

Druhou oblastí Mandelbrotovy množiny, ve které je možné nalézt hodnotu π, je okolí bodu +0,25+0i, což je také naznačeno na druhém obrázku. Tentokrát se k uvedenému bodu nepřibližujeme ve směru vertikálním (tj. změnou imaginární složky konstanty C), ale naopak ve směru horizontálním, tj. změnou reálné složky této konstanty. Další změnou je vlastní výpočet čísla π, kde se již nepoužívá prostého vynásobení počtu iterací a vzdálenosti od bodu, ale výpočtu druhé odmocniny vzdálenosti – to souvisí s jinými geometrickými aspekty v okolí bodu -0,75+0i a +0,25+0i. V následujícím výpisu je ukázáno, jak může výpočet π v okolí bodu +0,25+0i vypadat.

fractals18_2
Obrázek 2: Oblast, ve které se počítá číslo π podle druhé metody
// --------------------------------------------------------------------
// Výpočet konstanty PI pomocí iteračního cyklu platného pro
// Mandelbrotovu množinu. Vyžaduje se překladač s třicetidvoubitovým
// datovým typem int a úplnou podporou reálných čísel ve dvojité
// přesnosti.
// --------------------------------------------------------------------

#include <nath.h>
#include <stdio.h>
#include <stdlib.h>

#define PI 3.14159265358979323846

void mandelbrot_pi2(void)
{
    double zx, zy;                      // složky komplexní proměnné Z
    double cx, cy;                      // složky komplexní konstanty C
    double zx2, zy2;                    // druhé mocniny složek Z
    int    i;                           // počitadlo iterací
    const int maxiter=1000*1000*1000;   // maximální počet iterací
    double dcx=0.5;                     // změna vůči přesné hodnotě cx
    double pi;                          // vypočtená hodnota PI

    do {
        zx=zy=0.0;                      // bude se počítat orbit nuly
        cx=0.25+dcx;                    // nastavení hodnoty komplexní
        cy=0.0;                         // konstanty C
        for (i=0; i<maxiter; i++) {     // iterační smyčka
            zx2=zx*zx;                  // výpočet nové hodnoty Z
            zy2=zy*zy;
            if (zx2+zy2>4.0) break;     // podmínka divergence
            zy=2.0*zx*zy+cy;
            zx=zx2-zy2+cx;              // Z(i+1)=Z(i)^2+c
        }
        pi=i*sqrt(dcx);                 // výpočet PI
                                        // tisk výsledku
        printf("%10.8f \t %8d \t %14.10f %14.10f %10.6f\n",
                dcx,                    // změna vůči přesné hodnotě cx
                i,                      // dosažený počet iterací
                pi,                     // vypočtené číslo PI
                pi-PI,                  // absolutní chyba
                100.0*(pi-PI)/PI);      // relativní chyba
        dcx/=2.0;                       // další přiblížení k hodnotě 0.25
    } while (dcx>1.0E-9);               // reálné složky C
}

int main(void)
{
    mandelbrot_pi2();                   // výpočet PI
    return 0;
}

// -------------------------------------------------------------------- 

Ve druhé tabulce jsou uvedeny výsledky výpočtu čísla π pomocí funkce mandelbrot_pi2(). Všimněte si, že počet iterací vzrůstá menší měrou, za což ovšem platíme většími relativními i absolutními chybami při porovnání s přesnější hodnotou.

Přesnější hodnoty
Hodnota dcx Počet iterací Vypočtené π Absolutní chyba Relativní chyba
0.50000000 3 2.1213203436  –1.0202723100  –32.476276
0.25000000 5 2.5000000000  –0.6415926536  –20.422528
0.12500000 7 2.4748737342  –0.6667189194  –21.222322
0.06250000 11 2.7500000000  –0.3915926536  –12.464781
0.03125000 16 2.8284271247  –0.3131655288  –9.968368
0.01562500 23 2.8750000000  –0.2665926536  –8.485908
0.00781250 34 3.0052038200  –0.1363888335  –4.341391
0.00390625 48 3.0000000000  –0.1415926536  –4.507034
0.00195313 69 3.0493979939  –0.0921946597  –2.934647
0.00097656 99 3.0937500000  –0.0478426536  –1.522879
0.00048828 140 3.0935921677  –0.0480004859  –1.527903
0.00024414 199 3.1093750000  –0.0322176536  –1.025520
0.00012207 282 3.1156892546  –0.0259033990  –0.824531
0.00006104 400 3.1250000000  –0.0165926536  –0.528161
0.00003052 567 3.1322620698  –0.0093305838  –0.297002
0.00001526 802 3.1328125000  –0.0087801536  –0.279481
0.00000763 1135 3.1350242057  –0.0065684479  –0.209080
0.00000381 1607 3.1386718750  –0.0029207786  –0.092971
0.00000191 2273 3.1391674094  –0.0024252441  –0.077198
0.00000095 3215 3.1396484375  –0.0019442161  –0.061886
0.00000048 4548 3.1405484774  –0.0010441762  –0.033237
0.00000024 6432 3.1406250000  –0.0009676536  –0.030801
0.00000012 9097 3.1408937444  –0.0006989092  –0.022247
0.00000006 12866 3.1411132813  –0.0004793723  –0.015259
0.00000003 18196 3.1412390113  –0.0003536422  –0.011257
0.00000001 25734 3.1413574219  –0.0002352317  –0.007488
0.00000001 36394 3.1414116448  –0.0001810088  –0.005762
0.00000000 51470 3.1414794922  –0.0001131614  –0.003602
0.00000000 72790 3.1414979616  –0.0000946920  –0.003014

Konstantu π lze v různých podobách nalézt i v dalších bodech Mandelbrotovy množiny (resp. v jejich okolí), výpočty se však dále komplikují, např.  místo přímého použití vzdáleností od bodů se musí vyčíslovat jejich odmocniny, nebo naopak umocňovat dosažený počet iterací.

4. Mandelbrotova množina a posloupnost přirozených čísel

V Mandelbrotově množině může pozorný matematik nalézt i další zajímavé jevy. Asi nejviditelnější je geometricky zakódovaná posloupnost přirozených čísel. Nejprve si však musíme říci, jak vůbec budeme přirozená čísla v Mandelbrotově množině nacházet a kterým geometrickým prvkům je budeme přiřazovat. Pokud největší srdcovou oblast Mandelbrotovy množiny označíme číslem 1, je možné další čísla přiřazovat i k jí přilehlým kruhovým oblastem. Přiřazení není samozřejmě nahodilé, ale řídí se jedním pravidlem: dané kruhové oblasti je přiřazeno takové přirozené číslo N, které odpovídá počtu ramen spirál umístěných na hranici mezi danou kruhovou oblastí a srdcovou oblastí tvořící střed Mandelbrotovy množiny. Místo počítání ramen spirál je možné vysledovat i počet rozvětvení „antén“, které z kruhových oblastí vychází na opačné straně, než leží spoj se srdcovou oblastí.

Při popisu tak komplexní struktury, jakou je Mandelbrotova množina, samozřejmě slova nevyjadřují skutečnost dokonale, proto je lepší provést vlastní experimenty (například v programu XaoS či FractInt, nebo pomocí demonstračních příkladů uvedených v předchozích částech tohoto seriálu), resp. se podívat na ilustrační obrázky umístěné v dalším textu. Na třetím obrázku je zobrazena Mandelbrotova množina s kruhovými oblastmi, jež po svém ohodnocení přirozeným číslem tvoří aritmetickou číselnou řadu. Kruhové oblasti nebyly z celé množiny, kde jich je nekonečné množství, vybrány náhodně. Jedná se o posloupnost vždy největší kruhové části, pokud v jejich hledání postupujeme ve směru hodinových ručiček (například od „dvanácté hodiny“). Aritmetická řada pokračuje do nekonečna, protože se v oblasti Elephant valley (tu již známe z předchozích částí tohoto seriálu) jednotlivé kruhové části na sebe stále více nabalují.

fractals18_3
Obrázek 3: Kruhové oblasti tvořící aritmetickou číselnou řadu

5. Mandelbrotova množina a Fibonacciho posloupnost

Objevení aritmetické řady v Mandelbrotově množině není ještě tak zajímavé – ostatně těžko si můžeme představit něco jednoduššího. Existuje však i další (tentokrát netriviální) posloupnost, kterou lze vysledovat o geometricky interpretovat. Jedná se o Fibonacciho posloupnost, která je kupodivu nacházena ve stále dalších matematických, fyzikálních i biologických souvislostech. Fibonacciho posloupnost je možné v Mandelbrotově množině vysledovat následujícím způsobem: z předchozího textu víme, že největší kruhové oblasti (nalevo od srdcové části) je přiřazeno číslo 2 a druhým dvou největším oblastem (nahoře či dole od srdcové části) číslo 3. Nyní se mezi těmito oblastmi pokusme najít nejbližší menší oblast. Jedná se o oblast s číslem 5 (obsahuje pětiramenné spirály) a zde si již můžeme všimnout, že platí 2+3=5. Můžeme pokračovat dále: mezi oblastí 3 a oblastí 5 nalezneme nejblíže menší kruhovou oblast. Ta má po zobrazení jí příslušejících spirál přiřazeno číslo 8, takže platí: 3+5=8. Mezi oblastmi 5 a 8 je největší oblast 13 atd. Dostáváme tedy číselnou řadu 1, 2, 3, 5, 8, 13, což není nic jiného než ona zmiňovaná Fibonacciho posloupnost.

fractals18_4
Obrázek 4: Kruhové oblasti tvořící Fibonacciho posloupnost

Na dalších obrázcích jsou zobrazeny spirály postupně příslušející kruhovým oblastem s ohodnocením 2, 3, 5, 8 a 13. Přepočítáním ramen se můžete o „pravdivosti“ přiřazení sami přesvědčit.

fractals18_5
Obrázek 5: Část oblasti s ohodnocením 2

fractals18_6
Obrázek 6: Část oblasti s ohodnocením 3

fractals18_7
Obrázek 7: Část oblasti s ohodnocením 5

fractals18_8
Obrázek 8: Část oblasti s ohodnocením 8

fractals18_9
Obrázek 9: Část oblasti s ohodnocením 13

6. Literatura a odkazy na Internetu

  1. Oficiální stránky programu FractInt:
    http://www.frac­tint.org/
  2. Stránky programu XaoS:
    http://xaos.sou­rceforge.net/en­glish.php
  3. Starší (a IMHO hezčí) verze stránek programu XaoS:
    http://xaos.sou­rceforge.net/blac­k/index.php
  4. Stránka věnovaná „počítání“ v Mandelbrotově množině:
    http://math.bu­.edu/DYSYS/FRAC­GEOM2/FRACGEOM2­.html

7. Obsah dalšího pokračování tohoto seriálu

V devatenáctém pokračování tohoto seriálu si ukážeme způsoby generování dalších fraktálních útvarů v komplexní rovině. Budou popsány Mandelbrotovy a Juliovy množiny s vyššími mocninami v iteračním vztahu.

Našli jste v článku chybu?

23. 2. 2006 8:38

S tim pluginem to zni zajimave, protoze ty zname oblasti M-setu je mozne najit i algoritmicky, tj. nejenom mit v databazi seznam bodu okolo hlavni srdcovky, ale nachazet i podobne oblasti v mensich "podkopiich M-setu.

Appletu s M-setem existuje velke mnozstvi (jeden se tusim dodava i s JDK), bohuzel to jsou vetsinou velmi primitivni programky, ktere toho moc neumi. Pred nejakym casem jsem ve skole zadaval projekt pro paralelni generovani fraktalu (nejenom M-setu) na vice pocitacich, ale ne…

22. 2. 2006 19:03

uzasny clanok!

tak ma napadly po bludeni v mandelbrotovej mnozine nejake veci:
1. spravit nejaky naucny chodnik v mandelbrotke - napr nejaky plugin do xaosu a ako by user zoomoval tak by sa mu postupne zobrazovali sipky s navestim ze tym smerom je napr "elephant valley" :-)
2. dobry napad by podla mna bol napr. nejaky webapplet s mandelbrotkou niekde na internete ktora by sa tiez dala nejako zoomovat a hocikto by mohol zanechat vlastny odkaz niekde v hlboko zabludenej casti mandelbrot…



Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí