Mandelbrot-Menge berechnen in Excel

Wenn es draußen sonnig wird, gibt es nichts Schöneres, als sich an den Computer zu setzen und ein bisschen zu experimentieren.

Heute haben wir beschlossen, Excel zu öffnen und mit Fraktalen zu spielen.

Schon seit einiger Zeit frage ich mich, welche Klassen von numerischen Berechnungen man eigentlich alle mit reinem Excel durchführen kann. Wie sich herausstellt, sind es so einige.

Keine Frage, alle Data-Science-Tools, die es gibt, haben ihre Berechtigung, und natürlich geht die Leistungsfähigkeit von Python oder R weit über Excel hinaus. Aber darum geht es hier gar nicht. Denn man übersieht leicht, dass auch das alte Schlachtross selbst immer leistungsfähiger wird.

Spaß mit Fraktalen

Lass uns also herausfinden, ob man mit Excel Fraktale berechnen kann (Spoiler: man kann).

Fraktale waren in den 80er und 90er Jahren recht populär, als Rechenleistung allgemein verfügbar wurde und deutlich mehr Menschen als zuvor begannen, sich mit Programmiersprachen und Numerik zu beschäftigen. Heute ist es etwas ruhiger um das Thema geworden. Trotzdem tauchen noch immer sehr schöne Darstellungen von Fraktalen auf, normalerweise aber mit dem Fokus auf dem ästhetischen Aspekt und nicht auf der Mathematik dahinter.

Es gibt im Netz einige Seiten über Fraktale und Excel, aber soweit ich gesehen habe, enden sie immer mit der Benutzung von VBA. Genau das möchte ich vermeiden, denn VBA-Skripte sind für mich kein reines Excel. Ich arbeite nach dem Grundsatz wenn es ohne VBA nicht geht, ist Excel das falsche Werkzeug.

Die Mandelbrot-Menge, ganz kurz rekapituliert

Als Beispiel nehmen wir den Urgroßvater aller Fraktale, die sogenannte Mandelbrot-Menge. Wenn Du mehr darüber wissen willst, findest Du dazu gute Texte auf Wikipedia (hier auf Englisch und hier auf Deutsch). Ich setze im Folgenden ein paar Grundkenntnisse über komplexe Zahlen voraus. Wenn Du möchtest, kannst Du die Erklärungen aber auch überspringen und direkt mit den Dateien experimentieren.

Wir betrachten also die Funktion f(z)=z²+C, die wir iterativ anwenden, d.h. wir erzeugen neue z-Werte durch die Operation z_n+1=z_n²+C, und wir beginnen mit z₀=0. Sowohl z als auch C sind komplexe Zahlen.

Das Diagramm in diesem Artikel zeigt die komplexe Ebene der Werte C. Der entscheidende Punkt liegt nun darin, zu bestimmen, ob die durch die obige Iteration erzeugte Folge z_n für einen gegebenen Punkt C konvergent oder divergent ist, also ob ihre Werte moderat bleiben oder über alle Maßen wachsen.

Das Innere des Apfelmännchens ist dann mathematisch gesehen der Konvergenzbereich der oben beschriebenen Folge.

Lambda-Funktionen in Excel

Der Schlüssel zur Umsetzung in Excel liegt in der Verwendung von rekursiven Lambda-Funktionen. Mehr dazu weiter unten.

Beginnen wir zum Aufwärmen mit ein paar Hilfsfunktionen. Excel verfügt nicht über einen komplexen Datentyp. Daher müssen wir die Real- und Imaginärteile explizit berechnen. Die Funktionen sind sehr einfach, und es ginge auch ohne sie. Dennoch verbessern sie die Lesbarkeit des Codes enorm.

Darüber hinaus können wir anhand dieser Hilfsfunktionen sehen, wie man mit Lambda-Funktionen arbeitet.

Definieren wir also zunächst die realen und imaginären Teile des Quadrats:

ComplexSquareRe
  = LAMBDA(R;I;R*R-I*I)
ComplexSquareIm
  = LAMBDA(R;I;2*R*I)

Wir speichern diese Funktionen in unserer Exceltabelle mit dem Namensmanager. Das heißt, der Funktionsname wird als Name eingetragen und alles einschließlich des Gleichheitszeichens in die Definition. Ein kurzer beschreibender Text ist ebenfalls immer zu empfehlen.

Darauf aufbauend definieren wir den einzelnen Iterationsschritt, ebenfalls unterteilt in Real- und Imaginärteil. Hier wirst Du feststellen, dass jeweils eine Komponente der Zahl C in den Funktionen nicht benötigt wird, was man auch wegoptimieren könnte. Auch dies habe ich der Übersichtlichkeit halber unterlassen.

IterStepRe
  = LAMBDA(R;I;CR;CI;
           ComplexSquareRe(R;I)+CR)
IterStepIm
  = LAMBDA(R;I;CR;CI;
           ComplexSquareIm(R;I)+CI)

Schließlich benötigen wir den Absolutwert einer komplexen Zahl, weil wir ihn verwenden wollen, um über die Konvergenz einer Reihe zu entscheiden. Wenn der Absolutwert einen gewissen vorgegebenen Grenzwert überschreitet, gehen wir davon aus, dass die Reihe divergiert.

AbsValue
  = LAMBDA(R;I;WURZEL(R*R+I*I))

Auch hier liegt Optimierungspotenzial verborgen, wenn wir versuchen, die Effizienz auf die Spitze zu treiben. Die Wurzeloperation (WURZEL in meiner deutschen Einstellung) ist numerisch relativ teuer, und es ist leicht, sie zu vermeiden. Vergleiche stattdessen einfach den Ausdruck unter der Wurzel mit dem Quadrat der Grenze. Schon brauchst Du keine Wurzel mehr, und das Quadrat der Schranke muss nur einmal berechnet werden.

Rekursive Lambda-Funktionen

Ein paar Überlegungen

Die entscheidende rekursive Funktion wird sich selbst aufrufen (deshalb heißt sie ja rekursiv). Es gibt dabei ein paar Dinge zu beachten:

Der Name, unter dem die Funktion im Namensmanager gespeichert ist, muss mit dem Namen übereinstimmen, mit dem die Funktion selbst aufgerufen wird.
Die Funktion sollte so gestaltet sein, dass sie ein sicheres Abbruchkriterium enthält – wir werden sehen, wie das in unserem Beispiel umgesetzt wurde.

Mandel
  = LAMBDA(R;I;CR;CI;n;
    LET(
      nnew; n+1;
      Rnew; IterStepRe(R;I;CR;CI);
      Inew; IterStepIm(R;I;CR;CI);
      Absnew; AbsValue(Rnew;INew);
      WENN(
        ODER(nnew>=MaxIter;
             Absnew>=UpperLimit);
        nnew;
        Mandel(Rnew;Inew;CR;CI;nnew)
      )
    )
  )

Wie es scheint, spielt die Sprache keine Rolle. Excel hat, aus welchem Grund auch immer, einige Befehle, die sich je nach verwendeter Sprache unterscheiden. Dieses Beispiel wurde in deutschem Excel geschrieben. Wenn Du auf Englisch programmierst, musst Du ODER durch OR und WENN durch IF ersetzen:

...
IF(
  OR(nnew>=MaxIter;
     Absnew>=UpperLimit);
...

Die Beispieldateien scheinen sich jedoch an das verwendete Sprachschema anzupassen, auch was den Inhalt des Namensmanagers betrifft. Es sollte also kein Problem sein, die Beispiele in jeder beliebigen Sprachversion ohne weitere Anpassungen zu verwenden. Bitte gib mir einen Hinweis, falls dies doch zu Problemen führt.

Wie Fraktale in Excel nun tatsächlich berechnet werden

Wir geben unserer Funktion fünf Argumente. Die ersten beiden sind die Real- und Imaginärteile von z. Wir initialisieren sie mit z₀=0, wie oben erklärt, wenn wir die Funktion aufrufen. Das dritte und vierte Argument sind der Real- und Imaginärteil der Zahl C. Das fünfte Argument, n, ist ein Zähler, der die Iterationstiefe überwacht. Wir werden ihn ebenfalls mit 0 initialisieren.

Der Funktionskörper selbst ist durch eine LET-Funktion übersichtlich strukturiert. Zuerst wird der Iterationszähler inkrementiert, dann werden Real- und Imaginärteil des neuen Wertes berechnet und schließlich sein Absolutwert, um über die Konvergenz entscheiden zu können.

Nun kommen wir zum entscheidenden Schritt. Das IF-Kriterium entscheidet, ob wir die Iteration beenden oder eine weitere Runde durchführen.

Hierfür benötigen wir zwei zusätzliche Parameter, die wir als benannte Zellen im Arbeitsblatt gespeichert haben.

MaxIter ist die maximale Iterationstiefe. In diesem Beispiel ist sie 250. Wenn dieser Wert erreicht ist, können wir mit einiger Sicherheit davon ausgehen, dass die Reihe nicht divergiert, da die Berechnung bis zu diesem Punkt fortgeschritten ist.
UpperLimit ist der absolute Grenzwert, der überschritten werden muss, damit wir annehmen, dass die Reihe divergiert. In den Beispieldateien liegt er bei 10.000. Oft ist dies schon nach wenigen Iterationen der Fall.

In beiden Fällen bricht die Funktion ab und gibt die Iterationstiefe nnew zurück. Wenn keiner der beiden Fälle eingetreten ist, geht die Iteration mit den neuen Werten in die nächste Runde.

Bei der grafischen Darstellung handelt es sich also um ein Höhendiagramm, das die erreichte Iterationstiefe auf der Ebene von C darstellt. Im Inneren des Apfelmännchens ist MaxIter erreicht, d.h. hier haben wir gemäß unserer Konvention Konvergenz. Außerhalb sieht man, farblich kodiert, verschiedene Grade der Divergenz. Du kannst die Farbkodierung und die Iterationstiefe in der Datei anpassen, um das Aussehen der Darstellung zu verändern.

Und nun viel Spaß beim Experimentieren.

Die Beispieldateien

Um mit Fraktalen in Excel herumzuspielen, kannst Du die hier bereitgestellten Beispieldateien herunterladen.

Die Dateien enthalten die beschriebenen Funktionen und eine einfache Logik, die eine C-Ebene (mit einstellbaren Maxima und Minima) definiert, in der die Mandel-Funktion in jeder Zelle aufgerufen wird. Schließlich wird ein Graph mit den Funktionswerten erstellt.

Datei	Beschreibung
MandelbrotFrac100.xlsx	Berechnung auf einem 100×100-Raster. Eigentlich 101. Schnell, aber die Grafik ist recht grob.
MandelbrotFrac255.xlsx	Berechnung auf einem 255×255-Gitter. Das ist das Maximum, das der verwendete Diagrammtyp in Excel zulässt. Trotzdem immer noch sehr schnell.

Bitte beachte, dass ich keine Garantie für Codebeispiele, einschließlich der bereitgestellten Dateien, übernehme. Das Bild der Mandelbrotmenge ist Eigentum des Autors.