Mandelbrot-fraktaler

Jeg tenker å bruke denne bloggen til å forklare forskjellige interessante ting jeg kommer over på en forståelig måte. I denne bloggposten vil jeg forklare Mandelbrot-fraktalen. Underveis gir jeg lynintroduksjoner til komplekse tall og konvergente og divergente følger.

Komplekse  tall

Fra barnsben av lærer vi om desimaltall, og at disse ligger på en linje. Matematikere kaller disse tallene for de relle tallene, og vi kaller mengden av alle reelle tall for \mathbb R («krittavle-R»). Du kan tenke på tallinja som en linje som er uendelig lang i begge retninger, hvor negative tall er til venstre og positive tall er til høyre.

Komplekse tall går ikke bare i én retning, men i to. De har altså både en x- og en y-koordinat. Alle komplekse tall ligger i planet:

Det komplekse planet. Hvert komplekse tall er gitt ved to koordinater.
Det komplekse planet. Hvert komplekse tall er gitt ved to koordinater.

Over er et bilde av det komplekse planet. Hvert komplekse tall er gitt ved to koordinater: en realdel a og en imaginærdel b. Vi ser at tallene med imaginærdel lik null (altså tallene med b=0), er reelle tall. Altså er alle reelle tall en del av det komplekse planet, men vi har mange nye tall.

Det er lett å legge sammen komplekse tall. Om vi har to komplekse tall, legger vi bare sammen realdelene og imaginærdelene hver for seg:

(a+ib) + (c+id) = (a+c)+i(b+d)

Tenker vi oss litt om, er dette akkurat som vektoraddisjon:

Å legge sammen komplekse tall gjøres ved parallellogram-regelen.
Å legge sammen komplekse tall gjøres ved parallellogram-regelen.

På bildet over har vi summert tallene 1+i og 1.5+0.5i.

Vi kan også gange sammen komplekse tall. Dette er rett fram, bare at vi krever en ting: for komplekse tall krever vi at i^2=-1. Den nye koordinaten vi innfører, fungerer som en kvadratrot for -1 (husk at om x er et reelt tall, er alltid kvadratroten positiv. Komplekse tall oppfører seg annerledes):

(a+ib)(c+id) = ac+ad i +bc i + bc i^2 = (ac-bc) + (ad+bc)i.

Det finnes også en geometrisk tolkning av multiplikasjon av komplekse tall, men det hopper vi over i denne runden (hvis du virkelig vil ha svaret: for å gange sammen to komplekse tall, så ganger vi sammen lengdene til tallene og legger sammen vinklene).

Alle komplekse tall har en lengde. Lengden til et komplekst tall er akkurat hva du tror det skal være, og hvis vi husker ungdomsskolepensumet, husker vi at vi kan regne ut lengen ved hjelp av Pythagoras’ formel. Vi skriver |z| for lengden til tallet z.

|z| = \sqrt{a^2+b^2}.

Dette er de egenskapene til komplekse tall vi trenger for å forstå hvordan Mandelbrot-fraktalen er definert. Komplekse tall er et fascinerende felt, og det er mange flere ting jeg kunne sagt, men jeg har ingen planer om å skrive bok akkurat nå.

Det viktigste å huske er at de legges sammen koordinatvis, og at i^2=-1. Fra dette følger alt det andre.

Følger

La oss starte med et eksempel. Jeg gir deg to startverdier a_1 = 1 og a_2=2. Så forteller jeg deg at du får neste tall i følgen ved å legge sammen de to forrige tallene. Dermed er a_3 = a_2 + a_1 = 2. Sånn kan vi fortsette, og generelt har vi at a_n = a_{n-1} + a_{n-2}. De første tallene vi får er er

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...

Dette gir oss det som kalles en følge. En følge er ikke noe annet en uendelig lang rekke av tall (de kan godt være naturlige tall eller komplekse tall). Her er hvordan du kan lage disse tallene i Python:

L = [1,1]
for i in range(20):
    L.append(L[i]+L[i+1])

L
>>
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711]

Det vi ser er at at tallene vokser veldig raskt. Faktisk vokser de eksponensielt raskt (like raskt som en bakteriekultur med nok næring og plass), og asymptotisk som \varphi^n, hvor \varphi=(1+\sqrt 5)/2 er det gylne snitt.

Denne følgen er også kjent som Fibonacci-følgen, og det er allerede skrevet masse om den. Se for eksempel Wikipedia.

Dette var et eksempel på en divergent følge. Den vokser og vokser og går ikke mot noe bestemt tall. Det er to måter en følge en følge kan divergere på. Enten går den mot uendelig, slik Fibonacci-følgen gjorde. Ellers kan den oscillere og aldri slå seg til ro. Et eksempel er a_n=(-1)^n. Denne går slik: 1, -1, 1, -1, …, og slår seg aldri til ro.

Med dette vet vi nok om følger til å introdusere Mandelbrot-mengden.

Mandelbrot

La f(z)=z^2+c. Dette er altså en funksjon som først kvadrerer et komplekst tall og så legger c til det. Geometrisk betyr dette at vi kvadrerer lengden til tallet og dobler vinkelen, og deretter flytter det med vektoren c  bortover (vi kan alltid tenke på komplekse tall som både tall og vektorer).

For hvert komplekse tall c lager vi følgende følge: z_0=0. Deretter er z_1=f(0). Og z_2=f(f(0)). Generelt er z_n=f(z_{n-1})=f^{(n)}(0). Vi bruker altså funksjonen igjen og igjen på det forrige resultatet.

Eksempel: la c=1. Da er z_0=0. Og z_1=0^2+1=1. Og z_2 = f(f(0))=f(1)=1+1=2. Før du leser neste avsnitt, ser du hva neste tall i følgen blir?

Vi regner ut z_3 = f(f(f(0))) = f(2) = 2^2+1=5. Og z_4 = 5^2+1=26. Og z_5 = 26^2+1= 677. Dette vokser utrolig raskt. Allerede z_{10} \approx 10^{90}, som er mye mer enn antall atomer i det observerbare universet.

Hva skjer så hvis vi prøver med c=-1 i stedet? Vi regner ut de første tallene i Python slik:

def z(n):
    if n == 0:
        return 0
    else:
        return z(n-1)**2-1

[z(i) for i in range(10)]
>>
[0, -1, 0, -1, 0, -1, 0, -1, 0, -1]

Nå vokser ikke tallene, og vi ser at følgen alternerer mellom 0 og -1. Vi sier at følgen er begrenset.

La oss prøve med et komplekst tall, for eksempel c = i, altså roten til minus én. Igjen kan vi bruke Python til å gjøre utregningen for oss. Python har et bibliotek som gjør at vi slipper å implementere komplekse tall selv. Så følgende kode virker:

import cmath

def z(n, c):
	if n == 0:
		return 0
	else:
		return z(n-1,c)**2 + c


print([z(k,1j) for k in range(12)]

>>
[0, 1j, (-1+1j), -1j, (-1+1j), -1j, (-1+1j), -1j, (-1+1j), -1j, (-1+1j), -1j]

Igjen ser vi at vi får noe som ikke vokser ut av all kontroll. Det er interessant å spørre seg for hvilke c i det komplekse planet vil denne følgen vokse ut av all kontroll, og for hvilke c vil den holde seg begrenset?

Det er akkurat dét Mandelbrot-mengden er: det er mengden av c-verdier i planet slik at følgen over er begrenset. Så langt vet vi at -1 og i er med i Mandelbrot-mengden, men ikke 1.

Implementering av Mandelbrot i Processing

Processing er et programmeringsspråk som er bygd på Java, men med enklere syntaks. Formålet er at det skal være enkelt å komme i gang, og da spesielt med grafikk. Siden det er bygd på Java, har vi tilgang til alle de vanlige Java-bibliotekene, og syntaksen er veldig lik.

Siden Mandelbrot-mengden er definert som en viss delmengde av det komplekse planet, er det kjekt å kunne regne på komplekse tall på datamaskinen. Derfor har jeg skrevet en liten klasse for å summere og gange sammen komplekse tall:

class Complex {
  double x;
  double y;
  
  Complex(double x_, double y_) {
    x = x_;
    y = y_;
  }
  
  @Override
  public String toString() {
    return String.valueOf(x) + "+i" + String.valueOf(y);
  }
  
  // adds c to self
  void add(Complex other) {
    x = x + other.x;
    y = y + other.y;
  }
  
  // squares this number
  void square() {
    double old_x = x;
    double old_y = y;
    x = old_x*old_x - old_y*old_y;
    y = 2*old_x * old_y;
  }
  
  // returns square of length
  double lengthSq() {
    return x*x+y*y;
  }
}

Vi har nå muligheter for å legge sammen to komplekse tall, kvadrere et tall, og å få lengden til tallet.

Vi trenger en funksjon som lager følgen z_n = f(z_{n-1}) som vi definerte over. Husk at et komplekst tall c er med i Mandelbrot-mengden om denne følgen er begrenset. Om vi har gitt z_{n-1}, vil denne funksjonen regne ut z_n:

public void iterate(Complex z, Complex c) {
  z.square();
  z.add(c);
}

Koordinatsystemet Processing bruker er forskjellig fra det koordinatsystemet vi lærer om på skolen. I Processing svarer koordinatet (0,0) til venstre øvre hjørne. Jeg har derfor skrevet en funksjon som oversetter fra «piksel-koordinater» til komplekse koordinater. Når vi har alt dette, kan vi bruke følgende funksjon for å regne ut om et punkt (i,j) er med i Mandelbrot-mengden:

boolean checkMandelbrot(int i, int j, int noIterations) {
  Complex c = pixelToComplex(i, j);
  int k = 0;
  Complex z = new Complex(0, 0);
  while (k < noIterations) { iterate(z, c); if (z.lengthSq() >= 4) {
      return false;
    }
    k++;
  }
  return true;
}

Funksjonen konverterer først pikselkoordinatet (i,j) til et komplekst tall. Deretter lager den følgen, og sjekker om den er ubegrenset eller ikke. Ifølge Wikipedia er følgen ubegrenset om den en gang får vektorer med lengde 2. Hvis dette skjer før vi har nådd maksimalt antall iterasjoner, returnerer vi false, som betyr at punktet ikke er med i Mandelbrot-mengden.

Til slutt gjør vi dette for alle punkter i bildet, og vi får ender opp med følgende versjon av Mandelbrot-mengden:

En enkel versjon av Mandelbrot-fraktalen, uten noe hokuspokus.
En enkel versjon av Mandelbrot-fraktalen, uten noe hokuspokus.

Hele koden for å generere dette har jeg lagt ut på GitHub.

Jeg har også skrevet en mer komplisert versjon av samme skript som gir penere bilder:

Fargene sier noe om hvor raskt følgen i det punktet divergerer.
Fargene sier noe om hvor raskt følgen i det punktet divergerer.

I det mer kompliserte programmet har jeg lagt til funksjonalitet som gjør at man kan zoome innover i fraktalen. Her er noen utsnitt av hva man se:

Sjekk ut koden på GitHub. Jeg må bare først advare om at koden til denne er ganske rotete og dårlig kommentert!

Det får være nok for denne gang. Forhåpentligvis har leseren lært noe om Mandelbrot-mengden og at matte blir mye morsommere når man kan programmere den.