Mandelbrotova množina (E7/87)

Opäť tu máme nedeľný retro článok s obľúbeným matematickým orieškom.

Mandelbrotova množina, alebo, ako zamestnať osobný mikropočítač

Keď sa matematik Gaston Julia (1893–1978) zaoberal problémami zostrojovania fraktálnych (zlomkových) kriviek, iste netušil ich veľkú budúcnosť. Výsledky jeho práce sa používajú v počítačovej grafike pri vytváraní vierohodných obrázkov horských chrbtov či morských pobreží. Jeho nasledovník bol výskumník firmy IBM – Benoit Mandelbrot. Našiel v rovine komplexných čísel zaujímavú množinu. Dnes nesie jeho meno – Mandelbrotova množina.

Povedzme si o nej niečo viac. Každé komplexné číslo z možno zobraziť ako bod komplexnej roviny. Súradnica bodu na osi x je určená reálnou časťou a súradnica na osi y imaginárnou časťou komplexného čísla. Počítajme hodnotu výrazu zn = z(n-1)^2  + u[mi]. Zn je premenná s počiatočnou hodnotou z0 = u[mi] a u[mi] je komplexná konštanta. Nech napríklad z0 = u[mi] = 1 + 2i. Prvé tri kroky výpočtu dajú výsledky:
z1=-2 +6i
z2 =-31 – 22i
z3=-374 + 684i
Pozrime sa na absolútnu hodnotu výsledkov Zn. Musíme sčítať štvorce ich reálnej a imaginárnej časti a celkový súčet odmocniť. Absolutne hodnoty sú 6,325; 38,013; 1 445,33. Vidíme, že rýchlo rastú. Čísla u[mi] s takouto vlastnosťou nie sú pre nás zaujímavé.

Mandelbrotova množina je množina takých komplexných čísel u[mi], pre ktoré veľkosť |zn| ostáva konečná aj po l’ubovolnom počte krokov nášho výpočtu. V teórii sa hovorí, že naše komplexné číslo |zn| uteká do nekonečna práve vtedy, ak po istom počte krokov dosiahne jeho absolútna hodnota veľkosť 2 a viac. Pri výpočtoch sa ukazuje, že dostatočne veľa utekajúcich bodov dosiahne hodnotu 2 už po niekoľkých krokoch. Pri voľbe rozumného počtu krokov k, všetky body u na komplexnej rovine, pre ktoré platí |zk| < 2, patria do Mandelbrotovej množiny. Obvykle sa udávajú potrebné počty krokov k rádovo v stovkách.

Popíšme si postup, ktorý nám umožní vidieť Mandelbrotovu množinu a jej okolie na farebnom monitore mikropočítača. Najprv si vyberieme štvorcovú alebo obdlžnikovú oblasť komplexnej roviny, ktorú chceme zviditeľniť. Určíme jej súradnice na reálnej osi XD, XH a na imaginárnej osi YD, YH. Rozmery matice šachovnicovo rozmiestnených obrazových bodov (ďalej ich budeme nazývať pixelmi) musíme prispôsobiť možnostiam nášho mikropočítača. Snažíme sa plne využiť kapacitu obrazovej pamäti. Rozmery strán každého pixelu DX, DY vypočítame tak, že dlžku x-ovej (y-ovej) súradnice strán oblasti podelíme počtom stlpcov (riadkov) obrazu. Zvolený počet krokov pre získanie Mandelbrotovej množiny označíme KH.
Teraz nasleduje jadro postupu, ktorý je uvedený pre pixel v M-tom riadku a N-tom stĺpci. Algoritmus má štyri časti. Treba ho opakovať pre každý pixel.

  1. Vypočítame reálnu čast čísla zodpovedajúcu danému pixelu ako N-DX + XD a jeho imaginárnu časť ako M-DY+YD.
  2. Vložíme počiatočné hodnoty premennej z a premennej uchovávajúcej počet vykonaných opakovaní k na: zo = u[mi] a k0 = 0
  3. Pokiaľ k nedosiahne hodnotu väčšiu alebo rovnú KH, alebo nezávisle na tom |z| nie je väčšia alebo rovná 2, vykonáme nasledujúce operácie: z <- z^2 + u[mi]; k <- k+1
  4. Určime farbu pixelu v M-tom riadku a N-tom stlpci podla hodnoty, ktorú dosiahla premenná k v tretej časti algoritmu.

Ak sa k = kH, nech je pixel čierny. Tieto pixely tvoria samotnú Mandelbrotovu – množinu. V ostatných prípadoch je možné pixel vysvietiť farbou podľa našich estetických zámerov a podľa počtu farieb, ktorým disponujeme. Môžeme zvoliť napríklad taký postup, aby sa každá farba vyskytovala v obrázku iba raz, alebo naopak, aby každá zmena k o jednotku zmenila farbu pixelov. Okolie čiernej Mandelbrotovej množiny bude hýriť farbami. Ak sú naše zobrazovacie možnosti iba čiernobiele, pri k rovnom kH pixel nech je čierny, v ostatných prípadoch nech je biely.

Pri podrobnejšom pohľade na získané obrázky vidíme, že materská množina má na krajoch prilepené množstvo menších výčnelkov pripomínajúcich bradavice. Všetky čierne oblasti sú spojené aspoň tenkými prielivmi. Možno totiž dokázať, že Mendelbrotova množina je spojitá.

Samotný program je jednoduchý, ale vzhľadom na obrovský počet pixelov a veľký počet opakovaní trvajú výpočty pomerne dlho. Na mikropočítači PP01 trvá výpočet obrázku rozmerov 256 X 256 pixelov, hodnote kH=100 a programe v BASICU viac ako 12 hodín. Možno síce znížiť počet pixelov i opakovaní, ale zaplatíme za to zníženou jemnosťou obrázku. Pri dlhom čakaní na výsledok l’ahko pochopíme, prečo je Mandelbrotova množina obľúbeným testom rýchlosti pre paralelne pracujúce počítače. Napriklad OMS T 414 zvládne obrázok 512 X 512 pixelov pri 256 krokoch rádovo za desatiny sekundy…
Tým, ktorí budú mať šťastnú ruku pri výbere zviditeľňovanej oblasti komplexnej roviny, sa mikropočítač odvďačí za trpezlivosť neobyčajnými pestrofarebnými pohľadmi na jeden z najzložitejších matematických objektov súčasnosti. Obrázok v žiadnej svojej oblasti pritom neposkytuje opakujúci sa pohľad. Príklady pohľadov na rôzne časti Mandelbrotovej množiny môžete vidieť na obrázkoch.

Ing. IVAN HÁBOVČÍK

Elektrón 7 / 1987, strana 44 a 45


5 PAPER 7: CLEAR: INK 1
10 REM **** MANDELBROTOVA MNOZINA ****
15 REM *** ODPORUCANE HODNOTY: XU=-2,XO=0.5,YU=-1.25,YO=1.25
17 REM ** KX=50,S=4,PX=255
20 PRINT "VSTUP PARAMETROV"
30 PRINT "VSTUP ROZMEROV ZVIDITELNOVANEJ OBLASTI"
40 PRINT "X-DOLNE=": INPUT XU
50 PRINT "X-HORNE=": INPUT XO
60 PRINT "Y-DOLNE=": INPUT YL
70 PRINT "Y-HORNE=": INPUT YO
80 PRINT "ZADAJ POCET CYKLOV": INPUT KX
90 PRINT "ZADAJ HRANICNU SUMU": INPUT S
100 PRINT "ZADAJ POCET PIXELOV STRAN OBRAZKU": INPUT PX
110 SCALE 0,PX,0,PX: PAPER 0: CLEAR
120 DX=(XO-XU)/PX
130 DY=(YO-YU)/PX
140 FOR M=0 TO PX
150 FOR N=0 TO PX
160 XC=XU+N*DX: YC=YU+M*DY
170 K=0: XZ=0: YZ=0
180 K=K+1
190 XX=XZ*XZ: YY=YZ*YZ
200 YZ=2*XZ*YZ+YC
210 XZ=XX-YY+XC
220 IF K=KX+1 THEN 270
230 IF XX+YY<S THEN 180
240 L=K-TRUNC(K/C)*C+1: F=TRUNC(L/A): INK F
250 MOVE N,M
260 PLOT N,M
270 NEXT N
280 NEXT M
290 BEEP 200,200
300 GOTO 300

Jedna poznámka pod čiarou k uverejnenému programu: Riadok 240 vyzerá ako z „iného sveta“. Premenné C a A nie sú pred použitím definované, rovnako ani F, takže samozrejme to nemôže fungovať. Ak máte predstavu ako to má správne vyzerať podeľte sa o ňu, prosím, v komentári. Vďaka.

/ikon

3 názory na “Mandelbrotova množina (E7/87)

  1. Předpokládám, že ve srovnání s programem, který jsem použil já, řádek 230 nahrazuje konstrukci INK I-8*(I\8) (proměnná I je předpokládám to samé, jako v programu z Elektroniky proměnná K).
    V souvislosti s větou „podľa počtu farieb, ktorým disponujeme. Môžeme zvoliť napríklad taký postup, aby sa každá farba vyskytovala v obrázku iba raz, alebo naopak, aby každá zmena k o jednotku zmenila farbu pixelov“ A nebo C tedy budou konstanty definující počty dostupných barev (u mne nahrazeno konstantou 8) pro přepočet K (0..KX) na barvu pixelu. TRUNC (K/C)*C nejspíš nahrazuje moje použití MOD (\).
    Neslouží mi teď mozek, ale řekl bych tedy C počet „odstínů“ a A do kolika barev je vtěsnat. C=8 A=1 bude kreslit jako mnou použitý program (při zvýšení K o 1 zvýší barvu, při přetečení opakuje paletu), C=KX A=KX/8 by mělo rozhodit celý interval do 8 barev (při KX-256 v krocích po 32).
    Nebo jsem vedle?

    Program z Elektroniky bude pomalejší, protože počítá celé pole 256×256, ale mnou použitý program počítá jen polovinu a vykresluje zrcadlově.

  2. Ahojte, ešte to trochu vysvetlím…

    Keby sme dosadili za premennú C číslo 8 a za premennú A číslo 1 tak hore uvedený program by generoval farby od 1 po 8 a to by nefungovalo. INK 8 by spôsobil chybu v programe. Ale na druhej strane je dobré že generuje až od 1 lebo čiernu farbu by sme nemali používať na vyfarbenie okolia množiny pretože samotná Mandelbrotova množina je čierna a to je spojitý ohraničený priestor. Ponúka sa jednoduché riešenie za C dosadiť čislo 7. Zápis riadku by mohol vyzerať následovne:

    240 L=K-TRUNC(K/7)*7+1: F=TRUNC(L/1): INK F

    Takto to funguje tak ako má ale je tu jedno ale, druhá časť riadku je delenie „niečoho“ jednotkou a keďže pracujeme s celými číslami tak dostaneme zase len to isté „niečo“ takže môžeme túto časť vypustiť. Zjednodušený zápis bude takýto:

    240 F=K-TRUNC(K/7)*7+1: INK F

    Ako to bolo pôvodne myslené to neviem, možno že C by mohlo znamenať Colors a to by premenná C mohla mať hodnotu 8 alebo aj 7 keď nechceme používať čiernu farbu ale na čo slúžila v tomto prípade premenná A to netuším.

    Asi je pravda že dexov program je rýchlejší lebo využíva toho že Mandelbrotova množina ako celok je symetrická ale programom uverejneným v Elektróne si môžeme zobraziť akúkoľvek časť množiny a na to symetrický výpočet nie je vhodný.

Pridaj komentár