Newton-Fraktale

Für die ungeduldigen: Man kann das Programm gleich hier herunterladen. Weiter unten gibt's ein Changelog.

Obwohl ich ja eigentlich Informatiker bin, finde ich die Mathematik, die wir unterrichtet bekommen, teilweise wirklich interessant. Und vor ein Paar Stunden wurde sogar etwas behandelt, das mich richtig fasziniert hat, so, dass ich ein kleines Programm dazu geschrieben habe und hier diese Seite ins Netz stelle. Es geht um Fraktale.

Zuerst will ich das einmal versuchen sehr einfach zu erklären, damit man das auch versteht, wenn man nicht so interessiert an Mathe ist. Zunächst einmal gehen wir von einer einfachen Funktion aus, nämlich f_(x) = x² - 1

$latex:f_{(x)} = x^2 - 1$

Diese Funktion hat zwei Nullstellen, also Stellen, an denen der Funktionswert Null annimmt. Diese stellen sind x = -1 und x = 1, im Diagramm deutlich zu sehen (die Stellen, an denen die Funktion die X-Achse schneidet)

Nun ist die Frage, wie man die Nullstellen berechnen kann (wenn man sie eben nicht so schön sieht wie hier). Dazu bietet sich das Newton-Verfahren an. Das ist eine Formel, mit der man iterativ (also durch mehrfaches Anwenden) eine Lösung annähern kann. Die Formel lautet

$latex:u_{n+1} = u_n - \frac{f(u_n)}{f'(u_n)}$

Oder konkret für unser Beispiel f_(x) = x² - 1, indem wir f_(x) = x² - 1 und f'_(x) = 2x, also die erste Ableitung der Funktion einsetzen:

$latex:u_{n+1} = u_n - \frac{u_n^2 - 1}{2 \* u_n}$

Über das Newton-Verfahren wissen wir, dass wenn wir mit einem beliebigen u₀ anfangen, das ganze immer gegen eine Nullstelle konvergieren wird. Schwer zu glauben? Probieren wir erst mal aus. Wir wählen uns ein u₀ von 5.

$latex:u_0 = 5$ $latex:u_1 = u_0 - \frac{u_0^2 - 1}{2 \* u_0} = 5 - \frac{24}{10} = 2.6$ $latex:u_2 = u_1 - \frac{u_1^2 - 1}{2 \* u_1} = 2.6 - \frac{5.76}{5.2} \approx 1.492$ $latex:u_3 = u_2 - \frac{u_2^2 - 1}{2 \* u_2} = 1.492 - \frac{1.227}{2.984} \approx 1.081$ $latex:u_4 = u_3 - \frac{u_3^2 - 1}{2 \* u_3} = 1.081 - \frac{0.168}{2.162} \approx 1.003$ $latex:u_5 = u_4 - \frac{u_4^2 - 1}{2 \* u_4} = 1.003 - \frac{0.006009}{2.006} \approx 1.0000045$

Sehr schön, oder? Schon nach ein Paar Schritten haben wir eine sehr gute Lösung, nämlich ein "u" Nahe an der 1, einer unserer Nullstellen. Aber wieso sind wir jetzt bei der 1 gelandet und nicht bei der -1, die ja auch eine Nullstelle der Funktion ist? Naja, das scheint zunächst sehr einleuchtend: unser Startwert, die 5, ist an der 1 einfach näher dran (Entfernung: 4) als die -1 (Entfernung: 6). Kommt also immer diejenige Nullstelle heraus, die am nähsten am Startwert lag? Nein. Und das ist jetzt genau das Interessante!

Denn wenn die Verteilung der Lösungen nicht "gerecht" ist, wie schaut sie dann aus? Dazu kann man sich folgendes überlegen: Man hat einen Zahlenstrahl und betrachtet den Ausschnitt von -3 bis 3. Die Nullstellen markieren wir uns bei -1 (blau) und bei 1 (rot):

Und jetzt geht man die Zahlen von -3 bis 3 durch, sagen wir in 0.1-Schritten. Diese Zahlen nimmt man dann als Startwerte für das oben gezeigte Newton-Verfahren. Dann schaut man, welche Nullstelle letztendlich herauskommt, und diejenige Farbe zeichnet man am Zahlenstrahl an.

Wie man sieht gibt es einige "Ausreißer", also Lösungen dort, wo man sie nicht vermuten würde. Das war allerdings nur ein kleines Beispiel, das noch recht unspektakulär ist. Vorallem deswegen, weil es eben ein eindimensionaler Zahlenstrahl ist. Ein zweidimensionales Bild sähe schon viel schöner aus. Da hat die Mathematik auch gleich eine schöne Lösung parat. Wir verwenden keine reelen Zahlen, sondern imaginäre Zahlen! Imaginäre Zahlen (auch komplexe Zahlen genannt) sind wie folgt aufgebaut:

$latex:z = n + mi,\spc z \in \mathbb{C}$ $latex:n, m \in \mathbb{R}$ $latex:i^2 = -1$

Jede komplexe Zahl "z" besteht also aus dem reelen Koordinatenpaar (n, m). Dabei ist "n" der sogenannte Realteil und m der Imaginärteil. Die Zahl "i" ist die imaginäre Einheit, die zu i² = -1 definiert ist. Daran sollte man sich nicht stören, wenn mans nicht glauben will, kann man wirklich einfach die komplexen Zahlen als "normale" Zahlenpaare mit eben besonderen Rechenregeln sehen. Sehr wichtig hierbei: die Regeln, um komplexe Zahlen zu addieren, subtrahieren oder multiplizieren werden zwar etwas "komisch", allerdings funktioniert das Denkmodell komplett! Man kann damit also wirklich tolle Dinge anstellen.

Wenn man jetzt die Definition der komplexen Zahlen "geschluckt" hat (mein Mathe-Prof, Herr Kurzweil hätte gesagt "Wers nicht glaubt läßt's zuhause noch einwirken"), dann können wir gleich nach dem Beispiel mit dem Zahlenstrahl fortfahren.

Erste Änderung: Wir stellen uns keinen Strahl mehr vor, sondern ein Bild (also nicht nur "Länge", sondern "Länge" und "Höhe", also zweidimensional). Auf diesem Bild betrachten wir jetzt jeden Bildpunkt als komplexe Zahl. Von links nach rechts wird der Realteil angetragen, von unten nach oben der Imaginärteil. War wirklich nicht so schwer, oder? Von links nach rechts wird also das "n" größer und von unten nach oben das "m".

Zweite Änderung: Wir denken uns nicht so eine langweilige Gleichung wie f(x) = x² - 1 aus, sondern eine, die vielleicht fünf oder sechs Nullstellen hat. Alle Überlegungen sind absolut analog! Jetzt ist es vielleicht noch sehr wissenswert, das das Suchen von Gleichungen sehr einfach wird. Denn da wir jetzt komplex rechnen, hat jedes Polynom n-ten Grades (z.B. ist x^2 + x zweiten Grades, weil die höchste Potenz 2 ist) auch n Nullstellen (in C). Das ist vielleicht schon ein bischen schockierend, aber bitte, einwirken lassen. Die Koeffizienten, also die Zahlen, die vor den Potenzen der Gleichung stehen, lassen wir auch gleich aus "C" (der Menge der komplexen Zahlen) sein, damits noch schöner wird.

Jetzt machen wir das genau gleiche wie vorhin mit den Zahlenstrahl. Wir sehen die Bildpunkte als Startwerte für das Newton-Verfahren und malen in verschiedenen Farben die jeweilige Nullstelle ein. Die Farbwahl ist hierbei uns überlassen. Man kann also z.B. eine Gleichung dritten Grades hernehmen (z.B. "x^3 - x^2 + 2x - 4") und die drei Nullstellen jeweis mit blau, rot und grün in das Bild einzeichnen lassen.

Auf gehts! Zuerst gezeigt wird "x³ - 1" (wenn man auf die Grafik klickt, kommt sie in höherer Auflösung):

Hier jetzt "x^7 + 2x^6 + 3x^5 + 4x^4 + 5x^3 + 6x^2 + 7x + 8" (sehr schön, oder?):

Jetzt wird's sehr bunt... "x^17 - 2x^16 + 4x^15 + 3x^14 - 5x^13 + 2x^12 + 7x^11 - 8x^10 + 3x^9 + 3x^8 + 11x^7 + 12*x^6 - 2x^5 + 3x^4 - 4x^3 + 4*x^2 + x + 4":

Das kleine C++-Programm, dass ich geschrieben habe, um die Dateien zu erzeugen, kann man sich hier herunterladen. Es benötigt den gcc, die SDL Libraries (und Headerdateien) und SDL_image um zu kompilieren. Sehr selbsterklärend (hoffe ich). Mit den Pfeiltasten navigiert man in einem Bild, mit + und - kann man rein- und rauszoomen und mit Escape beendet man das Ganze. Auch mit der Maus kann man das Programm bedienen: klicken zentriert den angewählen Punkt, drehen am Mausrad zoomt rein oder raus. Das Programm ist lizensiert unter der GNU General Public License. Viel Spaß dabei!

Version	Veränderungen	Datum
0.08 Download	Der alten Zeiten Willen: Habe das Programm wieder zum kompilieren gebracht... ...und dabei festgestellt, was für eine Katastrophe es ist :-( Die Codebasis stammt von 2004. Glasklarerweise konnte ich damals kein C++ programmieren.	1.11.2011
0.07 Download	Cluster-Computing Mode! Update am FractalWizard Programm zum erstellen von Polynomen mit definierten Nullstellen in R	9.7.2004
0.06	FractalWizard, der Fraktalzauberer! Sehr leichtes, menügeführtes erstellen von Fraktalen ist nun möglich. Kleiner Bugfix	9.7.2004
0.05	Weitere Kommandozeilenparameter Schon wieder neue Skripten (zur Filmerstellung) Erstellung von MPG-Filmen möglich (nicht nur MNG) Automatische LaTeX-Skripterstellung und PDF-Generierung Rudimentäre (!) Dokumentation Bedienung durch sinvolle Fehlermeldungen ergänzt Richtige Versionsnummern Bugfixes (v.a. beim Schreiben von PNG-Dateien) Den Beispielfilm musste ich wegen der Quotabegrenzung leider heruntenehmen! Hier kann man sich einen Beispiel-PDF ansehen	9.7.2004
0.04	Weitere Kommandozeilenparameter Diverse (!) Bugfixes Filmerstellung und neue Skripte dazu Lizenz endlich auch mit dabei	5.7.2004
0.03	Bessere Skripts zur automatischen Erzeugung von Fraktalen Bilder von der Homepage jetzt auch automatisch berechenbar Bugfixes	30.6.2004
0.02	Skriptgesteuerte Fraktalgenerierung Vorherige Analyse zum erstellen einheitlicher Farben Diverse Bugfixes Skript zum erzeugen von Fraktalskripten Hübschere Farben!	30.6.2004
0.01	Erstes Release	28.6.2004