Mandelbrotmängden

Mandelbrotmängden är en berömd fraktal uppkallad efter den franske matematikern Benoît B. Mandelbrot.

Historik[redigera | redigera wikitext]

Funktionen som ligger bakom Mandelbrotmängden upptäcktes ursprungligen år 1905 av den franske matematikern Pierre Fatou och studerades sedan vidare av Gaston Julia som under slutet av 1920-talet arbetade med metoder som itererar enkla komplexvärda funktioner. Julia upptäckte även de med mandelbrotmängden besläktade juliamängderna. Fatou och Julia undersökte främst konvergenser av enskilda parametrar; Julia skapade några bilder med låg upplösning för hand, men bättre visualiseringar skulle kräva datorkraft för de omfattande beräkningarna.

Benoît B. Mandelbrot var anställd vid IBM och arbetade där bland annat med att försöka få bukt med vissa typer av brus, ett kaosfenomen kallat cantordamm, som uppstår vid datakommunikation vilket föranledde honom att experimentera med kaotiska förlopp. När han återupptäckte Julias arbeten hade han fördelen att vara bland de första med tillgång till nödvändig datorkraft. Där skapade han den första bilden av mandelbrotmängden, en svart/vit utskrift på papper. Han beskrev sina resultat år 1982.

Definition[redigera | redigera wikitext]

Mandelbrotmängden är en mängd av punkter i det komplexa talplanet. Punkterna i mängden är de komplexa tal c för vilka den rekursiva talföljden z_n, definierad av

z_{n+1}=z_{n}^{2}+c,

inte går mot oändligheten när startvärdet är $z_{0}=0$ .

För att beräkna en bild av Mandelbrotmängden antar man att varje bildpunkt motsvarar ett specifikt $c$ , vilket genererar en specifik talföljd, och eftersom en digital bild innehåller ett ändligt antal bildpunkter innebär det att ett ändligt antal talföljder behöver undersökas vad gäller divergens.

Man kan visa att talföljden alltid divergerar om absolutbeloppet av något $z_{n}$ blir större än 2. Eftersom det inte är möjligt att utföra ett oändligt antal iterationer på ändlig tid brukar man i praktiken välja ett förutbestämt maximalt antal iterationer och om $|z_{n}|$ för en specifik talföljd inte överstigit 2 innan man når denna iteration så antar man att motsvarande $c$ tillhör mandelbrotmängden, annars inte.

Formeln ovan är skriven med komplexa tal men det går även att uttrycka samma sak med reella tal. Istället för det komplexa talet $c$ undersöker vi då punkten $(a,b)$ och istället för den komplexa talföljden $z_{n}$ får vi då två reella talföljder $x_{n}$ och $y_{n}$ :

x_{0}=0\,

y_{0}=0\,

x_{n+1}=x_{n}^{2}-y_{n}^{2}+a\,

y_{n+1}=2x_{n}y_{n}+b\,

Formelns funktion[redigera | redigera wikitext]

Först bestäms hur många gånger funktionen skall itereras eller det maximala beloppet indexräknaren $n$ kan anta. Detta för att det inte går att exakt beräkna fraktalen utan vad som nås är en approximation av den. Det i sin tur beror på att vissa punkter kan ta närmare oändligt många iterationer på sig innan de lämnar systemet och det går ju inte att beräkna. Nästa steg är att välja en punkt (eller koordinatpar om du vill). Den motsvarar punkten i det komplexa talplanet som skall analyseras huruvida den är en punkt i mandelbrotmängden eller ej. Sedan sätts parametern $z$ till att peka på origo, alltså nollpunkten. Även indexräknaren nollställs:

max n = noggrannhet Antal iterationer
c = [a, b]            Punkten som analyseras
z_{(n = 0)} = [0, 0].     Nollställ z och n

Detta är utgångsläget, för att sedan pröva om punkten c tillhör mandelbrotmängden så itereras formeln ovan och vid varje iteration så testas om absolutbeloppet av $z$ har nått över gränsvärdet som anger storleken på fångstmängden som brukas, i det här fallet är det $|z|<2,0$ som är fångstmängd. Om uttrycket är sant så görs nästa upprepning; i annat fall är $z$ utanför radien 2,0 och kommer garanterat att gå mot oändligheten. Om $z$ däremot inte går mot oändligheten så avbryts beräkningarna när indexräknaren $n$ har nått sitt maxvärde "max $n$ " och punkten antas vara en delmängd av mandelbrotmängden. (Det betyder att punkten ligger inom det svarta området i bild 1a. Det stora cirkelsegmentet som syns lite otydligt längst till vänster i bilden motsvarar $|z|$ == 2.0, och är gränsen för var $z$ har fallit ur fångstmängden efter den första iterationen. Nästa kurva i ordningen motsvarar den andra upprepningen o.s.v.)

För att beräkna absolutbeloppet av $z$ så kvadreras $x$ och $y$ sedan dras roten ur summan:

Absolutbelopp; (två dimensioner)

    |z| = sqrt(x² + y²)

Jämför; Pythagoras sats, längden på hypotenusan.

Men då $|z|<{\text{max}}$ är analogt med $|z|^{2}<{\text{max}}^{2}$ så gäller alltså även $(x^{2}+y^{2})<{\text{max}}^{2}$ vilket innebär att det går att undvika beräkningsmödan i rotutradgningen och testa direkt på ${\text{max}}^{2}$ i stället (i det här fallet 4). (Att beräkna fraktaler kan vara processkrävande, så att undvika onödiga beräkningar är en fördel.)

Algoritm[redigera | redigera wikitext]

Nu räcker det alltså inte med bara en formel utan det behövs även en algoritm. Algoritmens uppgifter är att dela in talplanet i ett rutnät som har samma upplösning som bildytan fraktalen skall visas på, utföra beräkningarna och testa villkor för fångstmängd och indexräknare och därefter upprepa eller avbryta. Rutnätet motsvarar koordinaterna (c) som skall approximeras och arbetas av punkt för punkt tills hela bilden är klar. Avbryts beräkningen på grund av att z fallit ur fångstmängden så betyder det att c pekar på en punkt i auran och ges då vanligtvis en färg från en predefinierad palett (egentligen en tabell), då används normalt det uppnådda värdet på n som index när färgen hämtas ur tabellen. Sedan skrivs punkten dit i den aktuella färgen vid koordinaten c. Uppnår indexräknaren däremot maxvärdet så skrivs vanligtvis en svart punkt dit för att markera att den tillhör mandelbrotmängden.

Pseudokod (där operanderna är i normaltext och operatorerna i fetstil) .

Räkna b från -2,0 till 2,0
  Räkna a från -2,0 till 2,0
    Sätt c till [a, b]
    Sätt z till [0, 0]
    Sätt n till 0
    Om |z| < 2 Och n < max n
      Sätt z till z² + c
      Öka n med 1
    Upprepa
    Sätt aktuell färg till n
    Skriv_pixel [a, b]
  Nästa a
Nästa b

Perturbation och Series Approximation[redigera | redigera wikitext]

Mycket starkt förstorade bilder kräver mer än den vanliga 64- eller 80-bitars precision som de flesta hårdvaruflyttalsdatatyper stöder. För att rendera mycket förstorade bilder (c:a >1e13 för den vanliga 64-bitars double datatypen) behöver man använda mjukvaruimplementerade "bignum" eller liknande matematikbibliotek, vilket är avsevärt långsammare. Emellertid kan detta påskyndas genom användandet av störningsteori (perturbation), vilket innebär att en referenspunkt beräknas med full precision och sedan används för att beräkna de omgivande punkterna, som därmed kan beräknas med lägre precision - dvs. så låg precision som stöds av hårdvarans datatyper.

Ofta förekommer dock områden i en bild där hårdvarans precision inte räcker till, som då antingen behöver mer precision eller ytterligare referenspunkter för att kunna beräknas korrekt. Genom att mäta avståndet från referenspunktens omloppsbana med den med låg precision beräknade punktens omloppsbana kan man detektera punkter som inte kan beräknas korrekt med låg precision, och därmed avbryta beräkningen av dessa och senare beräkna dem igen med t.ex. en närmare referenspunkt.

Vidare kan en trunkerad Taylorserie användas för att beräkna startvärdet för varje punkt som skall beräknas från referenspunkten. Detta gör att ett ofta avsevärt antal iterationer kan hoppas över.^[1]

Sammantaget kan dessa metoder snabba upp renderingen av mycket förstorade bilder upp till hundratalet gånger jämfört med de snabbaste traditionella programmen.^[2]

Eftersom Mandelbrotfraktaler har funnits i flera decennier och vars mönster och oändlighet fascinerat många, har det engagerat många skickliga programmerare under årtiondena att anta utmaningen att skapa snabba program, optimerade för denna typ av beräkningar, för att utforska dessa fraktaler bortom gränserna för vad som är möjligt med de datatyper som stöds av hårdvaran. Metoderna Perturbation och Series Approximation kan därför ses som en revolution inom detta område. Bilder som förut krävde t.ex. en timme för att renderas, kan nu renderas inom en minut.