Basins of Attraction - Grundlagen und Algorithmen

Wendet man für eine Funktion f : D → ℂ mit  D ⊆ ℂ  zur Lösung der Gleichung f (z) = 0 ein Iterations-verfahren an, so nennt man die Folge { z_i } mit dem Startpunkt z₀ ϵ B ⊆ ℂ, die gegen die Nullstelle ζ konvergiert, einen Orbit von z₀; ζ ist ein Attraktor für z₀. Die Menge aller Startpunkte z₀ ϵ B, die gegen ζ  konvergieren, ist der Einzugsbereich (Basin of Attraction) von ζ.

Die folgenden beiden Animationen zeigen für die Funktion z³ - 1 (links) und z⁴ - 1 (rechts) mit den Nullstellen ζ₁, ζ₂, ζ₃ bzw. ζ₁, ζ₂, ζ₃, ζ₄ die mit dem Newton-Verfahren entstehenden Orbits (weißer Streckenzug). Hier überfährt  z₀ (schwarzer Punkt mit weißem Rand) einen kleinen Bereich von B. Der Wert n ist die Iterationstiefe und gibt an, nach wie vielen Schritten ausgehend von z₀ eine Nullstelle ζ_k erreicht wird.

(Hinweis: Das "fertige" Fraktal mit allen Basins of Attraction (s. folgender Algorithmus) wurde zur Orientierung in der Grafik hinterlegt.)

Für die Berechnung und Darstellung der Basins of Attraction für einen Bereich B ⊆ ℂ einer komplexen Funktion f (z) wird zunächst jeder Nullstelle ζ_k von f  eine eigene Farbe zugeordnet.

Dann wird für jedes z₀ ϵ B ein Iterationsverfahren mit z₀ als Startwert ausgeführt. Der Startwert z₀ ϵ B erhält dann die Farbe der Nullstelle ζ_k , gegen die die Iteration konvergiert (s. auch folgende Animation) bzw. die Farbe Schwarz im Falle der Divergenz des Verfahrens. Hier der zugehörige Algorithmus in Pseudocode:

Man beachte, dass die Nullstellen ζ₁, ... ,  ζ_k (im Algorithmus sind diese in der Liste Z [ ] enthalten) bekannt und hinreichend genau vorgegeben sein müssen.

Führt man den obigen Algorithmus für reelle Funktionen f : D ⊆ ℝ → ℝ  und dem Newton-Verfahren zur Berechnung der Einzugsbereiche für einen Bereich B ⊆ ℝ (Intervall der x-Achse) durch, so erhält man in B farbige Teillinien, wie die folgenden zwei Beispiele zeigen (zur besseren Sichtbarkeit wurde die x-Achse "verbreitert").

Es zeigt sich, dass die gefundenen Nullstellen nicht in der größenmäßigen Reihenfolge auftreten - was man vielleicht erwarten würde - sondern dass es vielmehr zu Sprüngen und somit zu Farbwechseln kommt. Zommt man in ein Teilintervall von B hinein, in dem Sprünge / Farbwechsel stattfinden, so erhält man auch in diesem Teilintervall wieder weitere Teilintervalle, in denen erneut Sprünge / Farbwechsel stattfinden (vgl. Newton-Verfahren).

Wie sieht nun die entsprechende Grafik für komplexe Funktionen aus?

Wendet man z.B. das Newton-Verfahren auf die komplexe Funktion f (z) = z² - 1 an (diese hat nur die beiden reellen Nullstellen 1 und -1), so ist das entstehende Bild der Einzugsbereiche z.B. für B [-2, 2] x [-2, 2] eher unspektakulär:

Für andere Verfahren (s. unter Basins of Attraction für z^2-1=0) und im Fall komplexer Funktionen mit drei oder mehr Nullstellen zeigt der Plot für einen Bereich B ⊆ ℂ jedoch ein Fraktal [1] mit farbigen Teilbereichen in B. Das folgende Beispiel zeigt für das komplexe Newton-Verfahren die Basins of Attraction der Funktion f (z) = z³ - 1 für den Bereich B = [-2, 2] x [-2, 2].

Eine andere Art der Darstellung zeigt für eine Funktion f  die Konvergenzgeschwindigkeit für jeden Punkt

z₀ ϵ B beim jeweilig angewandten Iterationsverfahren. Hierbei wird, ausgehend vom Startwert z₀ , solange iteriert, bis die Abbruchbedingung |z_i - z_i-1 | ≤ ε  erfüllt ist. z₀ ϵ B wird dann die Farbe einer vorgegebenen Farbpalette zugeordnet, wobei der letzte Wert des Iterationsindexes i  die Position in der Farbpalette angibt:

Wie auch beim obigen Algorithmus wird z₀ ϵ B die Farbe schwarz zugeordnet, falls die maximale Iterationsanzahl erreicht wird. Hier der zugehörige Algorithmus in Pseudocode:

Die Größe/Länge P der Farbpalette kann zwar beliebig sein, jedoch hat sich eine Größe/Länge von P=256 bei vielen Programmen zur Erzeugung von Fraktalen etabliert.

Der letzte Iterationswert i  kann für die Punkte z₀ ϵ B sehr verschiedene Größenordnungen annehmen. Bei insgesamt sehr kleinen Werten für i (für das Beispiel z³-1=0 liegen für das Newton-Verfahren die meisten Werte unter 25, s. dazu auch die Animation am Anfang dieser Seite) sieht man bei der vorgegebenen Regenbogen-Palette kaum Unterschiede, wie im linken Bild der folgenden Galerie zu sehen ist. Mittels p_step  können die Werte von i  entlang der Palette "gestreckt" werden (s. mittleres Bild in folgender Galerie mit p_step=10).

Um z₀ auch für Werte von i > P einfärben zu können, wird eine Modulo-Berechnung mit der Palettenlänge P  durchgeführt, d.h. die Farbwerte wiederholen sich für Werte von i > P.  Alternativ kann man die Einfärbung auch so vornehmen, dass Stufen bei der Einfärbung entstehen (s. rechtes Bild in folgender Galerie).

Mit dem Algorithmus II, dem Newton-Verfahren und der obigen Regenbogen-Palette ergeben sich so für die Funktion f (z ) = z³ - 1 für B = [-2, 2] x [-2, 2]  folgende Fraktale:

Quellenverweise

[1]    https://de.wikipedia.org/wiki/Fraktal

Download

Für den interessierten Leser liegt hier ein EXCEL-Sheet bereit, mit dem auch die Animation zu den Orbits am Anfang der Seite erstellt wurde. Mit Hilfe von Schiebereglern kann die Position von z₀ innerhalb B verschoben werden. Ich habe bewusst auf eine "elegante" Programmierung mit VBA und Macros verzichtet, damit die Datei problemlos in den verschiedenen Programmversionen ausgeführt und inhaltlich leicht nachvollzogen werden kann.