Neueste Artikel

Kategorien

Suchen

Facebook

Sonstiges

RSS-Feed-Icon RSS-Feed

Fraktale mal anders als neu markieren

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)

bild

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: bild
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. bild
Danach sieht das dann so aus: bild
Nach der zweiten Iteration... bild
... sieht die Punktemenge so aus: bild
Die Iterationen werden immer wieder durchgeführt, bis sich die Punktemenge an das Bifurkationsdiagramm annähert. bild
Der ganze Vorgang wird in der folgenden MPEG-Animation schön dargestellt. Animation Bifurkation
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:

Matrix
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:

Matrix

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: bild
Da die Umkehrfunktion nicht überall definiert ist, wird ein großer Teil der Punkte verworfen: bild
Nun wird die erste Iteration durchgeführt: bild
Das Ergebnis der ersten Iteration: bild
Und wieder werden Punkte verworfen: bild
Die zweite Iteration: bild
Das Ergebnis der zweiten Iteration: bild
Diese Iterationen werden weitergeführt, bis folgendes Bild entsteht: bild
Auch diesen Vorgang habe ich in einem MPEG-Filmchen visualisiert: Animation Bifurkation
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.)

Bifurkation

Bifurkation

... 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.