Berechnung der Fraktale

Diese Beschreibung dient gleichzeitig als Einführung in das Java-Programm, mit dem die gezeigten Bilder berechnet wurden. Die kursiv geschriebenen Bezeichnungen werden dort verwendet.

1. Verfahren

Betrachtet werden soll das Verhalten der Folge F(c): z_n+1 = f(z_n,c), z₀ = c für eine kompakte Menge von komplexen Zahlen c. Die Folge kann gegen einen oder mehrere Werte konvergieren, für einzelne Werte undefiniert sein, oder beschränkt bleiben. Die Konvergenzpunkte nennt man Attraktoren der Funktion f, wobei auch die Flucht ins Unendliche darunter subsummiert wird.

Die Berechnung der Folge ist zu beenden, wenn ein Abbruchkriterium erfüllt ist. Dies kann die Feststellung sein, dass ein Attraktor oder eine maximale Schrittzahl erreicht wird, denn für die Berechnung per Computer muss sowohl die ausgewählte Zahlenmenge als auch die Zahl der Iterationsschritte beschränkt sein.

Will man die ausgewählte Zahlenmenge auf einem Bildschirm grafisch darstellen, so kann man jedem Bildpunkt (Pixel) eine ausgewählte Zahl zuordnen, die den Mittelpunkt des Quadrats bildet, das der Bildpunkt repräsentiert. Die Berechnung soll sich dabei immer auf ein ausgewähltes Quadrat der komplexen Ebene beschränken.

Folgende Angaben sind daher für die Berechnung notwendig:

• Der Mittelpunkt des ausgewählten Quadrats (centre),
• die Kantenlänge des Quadrats (length),
• die Anzahl der Bildpunkte pro Kantenlänge (numofPix),
• die maximale Iterationstiefe (maxIt),
• die Funktion f,
• das Abbruchkriterium K für die Iteration.

Das Ergebnis ist ein quadratisches Bild, wobei jeder Pixel einen berechneten Punkt des ausgewählten Quadrats darstellt und die gewählte Farbe des Pixels das Ergebnis der Berechnung charakterisiert.

Zu berechnen sind:

• Die Werte c für alle zu betrachtenden Punkte der komplexen Ebene:
  Jeder Wert ist als Mittelpunkt des Quadrats der Kantenlänge step = length/numofPix zu betrachten in dem es liegt. Beginnt man die Berechnung bei der unteren linken Ecke des Quadrats in der komplexen Ebene so ist der Ausgangspunkt c = start der Berechnung mit centre = centrere + centreim i:
  start = (centrere - length/2 +step/2) + (centreim - length/2 + step/2) i und die Schrittweite in Richtung beider Achsen step.
  Die Bearbeitung erfolgt zeilenweise.
• Für jeden Punkt c ist die Iteration durchzuführen. Jedem Iterationsschritt n soll ein Zustand Z_n zugeordnet werden, der folgende Werte enthält:
     maxIt, state und n
  wobei
     state = -1: die Iteration wird weitergeführt
     state = 0: die Iteration hat maxIt erreicht
     state = j > 0: der j-te Attraktor wurde erreicht
  Der Anfangszustand ist Z₀ = (maxIt, -1, 0). Das Abbruchkriterium K(z_n) bestimmt den Zustand Z_n+1. Ist Z_n+1 state = -1, dann wird z_n+1 = f(z_n,c) ausgeführt.
  Das Ergebnis der Iteration wird an Hand des letzten Zustandes ermittelt und ist im Bild als farbiger Bildpunkt darzustellen.
  Die Ränder der Mengen von Werten z für die f(z) denselben Attraktor erreicht, bilden das Fraktal zu f. Diese Ränder sind in der bildlichen Darstellung nicht als Bildpunkte sondern nur durch den Farbwechsel zwischen benachbarten Bildpunkten darstellbar.
  Das Fraktal kann also immer nur näherungsweise dargestellt werden.

Der bisher dargestellte Berechnungsrahmen ist unabhängig von der Gestalt des jeweiligen Fraktals. Nur die Funktion f, das Kriterium K und die grafische Darstellung des Ergebnisses ist speziell für jedes einzelne Fraktal zu berechnen. Dies gilt jedoch nicht für die Ausgabe der Farbwerte in eine Ergebnisdatei, für die ein einheitliches Verfahren (BMP) verwendet werden soll.

2. Die Fraktale

Die Berechnungen sollen für folgende Fraktale durchgeführt werden:

Das Mandelbrot-Fraktal

Die Menge der c, für die in der Folge
F(c): z_n+1 = z_n² + c, z₀ = c, |z_n| < 2 für alle n bleibt, ergibt die Mandelbrot-Menge.
Der Attraktor dieser Menge (im Unendlichen) wird für alle c erreicht, bei denen der Abstand von z_n zum Nullpunkt den Wert 2 überschreitet. Bei Abbruch der Iteration ist entweder n < maxIt und state = 1 oder n = maxIt und state = 0.
Der Rand der Mandelbrot-Menge ist das Mandelbrot-Fraktal.

Das Julia-Fraktal eines Punktes c_fix

Die Menge der c, für die in der Folge
F(c): z_n+1 = z_n² + c_fix, z₀ = c, |z_n| < 2 für alle n bleibt, ergibt die Julia-Menge des Punktes c_fix, wenn c_fix aus der Mandelbrot-Menge gewählt wurde.
Der Attraktor dieser Menge (im Unendlichen) wird für alle c erreicht, bei denen der Abstand von z_n zum Nullpunkt den Wert 2 überschreitet. Bei Abbruch der Iteration ist entweder n < maxIt und state = 1 oder n = maxIt und state = 0.
Der Rand der Julia-Menge ist das Julia-Fraktal.

Für jedes maxIt, das man wählt, erhält man eine Menge, die größer ist, als die eigentliche Mandelbrot- oder Julia-Menge. Man sollte den Wert so wählen, dass sich das sichtbare Ergebnis nicht mehr von dem mit einem größeren maxIt berechneten unterscheiden lässt. Dies ist aber an den Grenzen der Berechenbarkeit mit dem PC nicht immer machbar.

Newton-Fraktale

Die Funktion f(z) = z - P(z)/P'(z) beschreibt ein Näherungsverfahren zur Bestimmung der Nullstellen von P(z). Es sollen Polynome P(z) = z³+uz²+vz+w mit ganzzahligen Koeffizienten u, v und w betrachtet werden:

Mt P'(z) = 3z²+2uz+v wird f(z) = (2z³+uz²-w)/(3z²+2uz+v) und mit derFolge F(c): z_n+1 = (2z_n³+uz_n²-w)/(3z_n²+2z_n+v), z₀ = c

erhält man dort, wo sie konvergiert, bis zu drei verschiedene Nullstellen von P(z) als Attraktoren.

Für alle zu berechnenden Werte c wird die Folge F(c) entweder gegen eine Nullstelle konvergieren, oder die Iteration ist nach maxit Schritten abzubrechen.  Die Nullstellen werden in der Reihenfolge ihres Auftretens nummeriert und state erhält  die Nummer als Wert. Im Falle des Abbruchs wird state = 0 gesetzt.

Bildet man für Polynome mit drei verschiedenen Nullstellen die drei Mengen von Werten c, bei denen F(c) gegen den gleichen Attraktor strebt, so bilden die Ränder dieser Mengen das Newton-Fraktal für das Polynom P(z).

3. Berechnung der Fraktale mit Java

Die komplexen Zahlen werden als Objekte der Klasse Comp definiert. Sie werden als Paar (re, im) vom Typ double dargestellt.

Der Berechnungsrahmen zur Herstellung des Fraktal-Bildes wird in der Klasse FracPic erstellt. Die Berechnung eines Iterationspunktes erfolgt zunächst in der Klasse MandelFrac für das Mandelbrot-Fraktal. Dabei ist die Klasse so gestaltet, dass sie für die anderen Fraktale erweitert werden kann und nur noch wenige Methoden überschrieben werden müssen.

Die Eingabdaten in der Datei input.txt werden in der Klasse FracInput verarbeitet, die Berechnung aufgerufen und die Ergebnisdaten ausgegeben. Standardmäßig wird für die Berechnung der Fraktale centre = 0 + 0 i und length = 4 gesetzt. numofPix wird auf das Intervall 100 <= numofPix <= 2000 beschränkt.

Das Ergebnis ist eine BMP-Datei erzeugt durch die Klasse Bmp. Für die BMP-Datei ist ein Dateikopf auszugeben, der die Form der Ausgabe bestimmt. Im Dateikopf wurde festgelegt, dass pro Pixel 3 Bytes für die RGB-Farben vorgesehen werden und die Breite des Bildes ein Vielfaches von 4 zu sein hat. Die Ausgabe wird pro Bildzeile gepuffert. In der gewählten Form der BMP-Ausgabe wird die zuletzt berechnete Zeile des Bildes zuerst ausgegeben; daher beginnt die Berechnung in der linken unteren Ecke des Quadrats.

Die verwendeten Farbwerte werden über eine Farbtafel definiert, die in der Klasse FracCols berechnet wird.

Mit Hilfe einer Internetseite werden die Eingabedaten im Dialog erstellt, die Berechnung ausgeführt und das Ergebnis dargestellt. Bei allen Fraktalen wird die Berechnung von interessanten Fraktalausschnitten ermöglicht.

3.1. Mandelbaum-Fraktal
Die Abfrage für das Kriterium K ist statt |z_n| > 2: islastC(z): z.re² + z.im² > 4, um eine Berechnung der Quadratwurzel zu vermeiden.
Für die Darstellung der Bildpunkte werden die Iterationsanzahlen in Farbwerte umgerechnet. Dabei soll die durch persönliche Vorlieben entstandene Auswahl von Farben unabhängig von der Berechnung in der Klasse MandelFrac erfolgen. Die Wahl der Farben erfolgt in der Klasse FracCols. Die Farben der Farbtafel werden als Zahlenwerte getrennt nach R-, G- und B-Farbwerten gespeichert. Für die Mandelbaum- und die Julia-Fraktale wurden für die ersten 10 Tsd. Iterationsschritte ebenso viele Farbtöne in der Klasse FracCols festgelegt. Diese Anzahl wurde festgelegt, um Teilfraktale bis zur Grenze der Genauigkeit der Gleitkomma-Rechnung des PC berechnen zu können. Die Farbänderungen wurden mit steigenden Iterationszahlen erheblich verlangsamt, um die auftretenden Strukturen noch angemessen darstellen zu können.
Die folgende Farbtafel zeigt die 10 Tsd. Farben, jeweils Tsd. Farben pro Zeile:

Die Mandelbrot-Menge selbst (state = 0) wird dunkelblau dargestellt, Iterationszahlen über 10 Tsd. hellgelb.

3.2. Julia-Fraktal
Die Berechnung ist mit der des Mandelbrot-Fraktals fast identisch. Es ist nur an einer Stelle c durch c_fix zu ersetzen, was durch Überschreiben einer elementaren Methode und Erweiterung der Klasse MandelFrac zur Klasse JuliaFrac erfolgt. Bei der Eingabe ist zusätzlich der Wert von c_fix festzulegen. Die Darstellung der Ausgabe kann ebenfalls übernommen werden. Es wurde jedoch noch ein Kompressionsfaktor für die Farbtafel colFac >= 1 eingeführt, um Berechnungen zu Punkten außerhalb der Mandelbrot-Menge farbiger erscheinen zu lassen.

Für die Berechnung eines Ausschnitts eines Mandelbaum- oder Julia-Fraktals mit 1 Mill. Pixeln und 10 Tsd. Iterationen bei allen Pixeln benötigte der PC mit Windows 10 und Prozessor Intel Core I3 9100F 4x3,6 GHz etwa 37 Sek. Für die Berechnung des Apfelmännchens mit 1 Mill. Pixeln reichen maximal 150 Iterationen pro Pixel aus. Dafür werden 0,125 Sek. benötigt.

3.3. Newton-Fraktal 
Für die Newton-Fraktale sind die Funktion f, das Kriterium K und die Ausgabe des Pixelwertes neu zu formulieren. Bei F(c) wird c nur als Startwert benötigt. In der neu formulierten Funktion f(z,c) kann c daher als Hilfsvariable für die Berechnung des Funktionswertes benutzt werden. Die Klasse entsteht durch Erweiterung der Klasse MandelFrac zu NewtonFrac. Die Farben in der Klasse FracCols sind anders als bisher zu wählen. Sie bestehen für Punkte c, die verschiedene Attraktoren erreichen, aus drei Grundfarben, die gemäß der Iterationsanzahl durch verschiedene Helligkeitstöne verändert werden. Hier sind 30 verschiedene Helligkeitstöne vorgesehen. Bereiche, in denen die Berechnung nicht konvergiert, werden dunkelblau dargestellt.

Für die Berechnung eines Newton-Fraktals mit 1 Mill. Pixeln werden bei maximal 50 Iterationen pro Pixel etwa 0,1 Sek. benötigt.