Fraktale mal anders als neu markieren
(Montag, 21.05.2007 15:30)
Beispiel: das Bifurkationsfraktal (Feigenbaumdiagramm)
Normalerweise wird das Bifurkationsfraktal durch das Iterieren der Gleichung y'=r·y·(1-y) berechnet. Als Startwert nimmt man z.B. y=0.1. Das y wird dann in die Gleichung eingesetzt und das Ergebnis ist dann das neue y, das dann wieder eingesetzt wird usw.
Die Ergebnisse werden als Punkte in einem Diagramm gezeichnet, die x-Achse entspricht dabei dem Parameter r und die y-Achse der Variable y. Die Figur, die dabei entsteht, bezeichnet man als Bifurkation.
(Siehe auch Wikipedia-Artikel: Feigenbaumdiagramm)
Der Nachteil an diesem Verfahren ist, dass wenn man sehr große, hochauflösende Bilder berechnen möchte, sehr viele Punkte gezeichnet werden müssen, damit das Fraktal rauschfrei abgebildet wird. Auf der Suche nach einer Alternative habe ich folgendes Verfahren entwickelt.
Was wäre, wenn man nicht einen Wert immer wieder in die Gleichung einsetzt, sondern sehr viele (1 Mio.) gleichzeitig? Das würde dann ungefähr folgendermaßen aussehen.
| Am Anfang wären alle Punkte gleich verteilt: |  |
| Nun führt man die erste Iteration auf alle Werte gleichzeitig durch. In der kleinen Animation wird deutlich, wie die Gleichung die gesamte Punktemenge wie ein Blatt Papier faltet. |  |
| Danach sieht das dann so aus: |  |
| Nach der zweiten Iteration... |  |
| ... sieht die Punktemenge so aus: |  |
| Die Iterationen werden immer wieder durchgeführt, bis sich die Punktemenge an das Bifurkationsdiagramm annähert. | |
| Der ganze Vorgang wird in der folgenden MPEG-Animation schön dargestellt. |  bifforw.mpg (1.7 MB) |
2. Die Mathematik dahinter
Jetzt ein Geständnis: Diese Bilder wurden in Wirklichkeit nicht mit 1 Million Punkten, sondern mit unendliche vielen gezeichnet.
Hä?
Ich betrachte nämlich nur die Wahrscheinlichkeit, dass sich an einer Stelle ein Punkt befindet.
Vorsicht, Mathematik!
Die einzelnen Spalten der Bilder werden in Wirklichkeit durch große Vektoren repräsentiert. Am Anfang sind alle diese Vektoren mit dem Wert 1 gefüllt - was in der grafischen Darstellung einer grauen Fläche entspricht.
Die Gleichung y'=r*y*(1-y) wird für einen Parameter r in eine große, sehr dünn besetzte Matrix umgewandelt, die schematisch so aussieht:
Weiß entspricht der 0.
Eine Iteration entspricht für eine Spalte nun der Multiplikation des Vektors mit dieser Matrix.
Das Ergebnis der Iterationen, also der ständigen Multiplikation mit der Matrix, ergibt einen Spaltenvektor des Bifurkationsfraktals. Da für die resultierenden Vektoren zwischen r = -2 und r = 4 gilt v = M·v, entsprechen sie dem Eigenvektor der jeweiligen Matrix M zum Eigenwert 1.
Ein Vorteil dieser Berechnung ist, dass sie auch umkehrbar ist. Die normale Berechnungsvariante, in der die Punkte einzeln gezeichnet werden, ist nicht umkehrbar, da die logistische Funktion r*x*(1-x) nicht invertierbar ist.
Die Matrix der Umkehrung sieht schematisch so aus:
Die Ergebnisse der iterativen Multiplikation mit der Umkehrmatrix werden im folgenden vorgestellt.
Mathematik Ex!
3. Invertierung der Transformation
| Bei der Umkehrrichtung gehe ich wieder von dem Fall aus, dass die Wahrscheinlichkeit, dass sich an einer Stelle ein Punkt befindet, überall gleich ist: |  |
| Da die Umkehrfunktion nicht überall definiert ist, wird ein großer Teil der Punkte verworfen: |  |
| Nun wird die erste Iteration durchgeführt: |  |
| Das Ergebnis der ersten Iteration: |  |
| Und wieder werden Punkte verworfen: |  |
| Die zweite Iteration: |  |
| Das Ergebnis der zweiten Iteration: |  |
| Diese Iterationen werden weitergeführt, bis folgendes Bild entsteht: |  |
| Auch diesen Vorgang habe ich in einem MPEG-Filmchen visualisiert: |  bifback.mpg (1.7 MB) |
4. Zusammenfassung der bisherigen Ergebnisse
Schon wieder Mathematik!
In diesem Bild entsprechen die Spaltenvektoren für r < -2 bzw. r > 4 den Eigenvektoren der entsprechenden Rücktransformationsmatrix zum Eigenwert 1.
Eigentlich entsprechen sie auch den Eigenvektoren der Vorwärtsmatrix, aber im Vorwärtsfall konvergiert die iterative Multiplikation nur im Bereich zwischen -2 < r < 4.
Interessant sind jetzt folgende Fragestellungen:
- Haben die Matrizen noch andere Eigenvektoren?
- Gibt es eine Möglichkeit, die Eigenvektoren schneller zu berechnen, als durch iteratives Multiplizieren?
- Kann man Rhabarberkuchen auch mit Erdbeeren machen?
Da sich dieses Verfahren prinzipiell auf alle Fraktale inklusive Julia- und IFS-Fraktale übertragen lässt und sich die großen Matrizen aufgrund ihrer dünnen Besetzung mit wenig Aufwand speichern und multiplizieren lassen, könnten sich neue Methoden der Fraktalberechnung ergeben.
Hierzu folgen später noch einige Definitionserweiterungen für unendlich große Matrizen.
Mathematik Ex.
Und nun kommen wir zu einer Weltpremiere (glaube ich zumindest). Wir fügen zusammen, was zusammen gehört:
Wir legen die Lösungen für die Vorwärts- und Rückwärtstransformation übereinander und es ergibt sich die vielleicht erste wirklich vollständige Darstellung des Bifurkationsfraktals:
(Die Bilder lassen sich mit einem Klick in höherer Auflösung runterladen.)
... Schönheit liegt im Auge des Betrachters ...
5. Nachbetrachtungen
1. Inversion
Für Funktionen, deren Definitions- und Wertebereich gleich der Menge der reellen Zahlen ist, entspricht die Rückwärtsmatrix gleich der inversen Vorwärtsmatrix. Außerdem sind die Determinanten der Matrizen gleich 1.
2. iterative Multiplikation
Die Iterationen lassen sich beschleunigen, wenn man die Matrizen quadriert. Durch jede Quadrierung nähern sich die Iterationen doppelt so schnell dem Ergebnis.
3. Vorwärts/Rückwärts
Das Iterationsverfahren, das zur Berechnung von Fliehzeitfraktalen wie Mandelbrot- und Juliamenge verwendet wird, ist komplementär zum Iterationsverfahren der IFS-, Flame- und Bifurkationsfraktale. (Was ich damit genau meine, werde ich in einem späteren Update erklären. Ich hab's erstmal hier hingeschrieben, damit ich es nicht vergesse.)
4. praktische Anwendung
Um zu zeigen, dass man das ganze Zeug auch wirklich praktisch anwenden kann, habe ich den Algorithmus in OpenGL implementiert. Mehr dazu gibt es im Artikel Echtzeitfraktalberechnung mit OpenGL.