Basins of Attraction - Algorithmen

Um für eine komplexe Funktion f (z) die Einzugsbereiche ihrer Nullstellen (Basins of Attraction) ζ1, ζ2, … für einen Bereich B ⊆ ℂ zu berechnen und darzustellen, wird zunächst jeder Nullstelle von f  eine eigene Farbe zugeordnet. Dann wird für jedes z0 ϵ B ein Iterationsverfahren mit z0 als Startwert ausgeführt. z0 ϵ B erhält dann die Farbe der Nullstelle ζk , gegen die das Iterationsverfahren konvergiert (s. auch folgende Animation) bzw. die Farbe Schwarz im Falle der Divergenz des Verfahrens. Hier der zugehörige Algorithmus in Pseudocode:

Algorithmus I - Basins of Attraction

Algorithmus I - Einzugsbereiche der Nullstellen (Basins of Attraction)
Basins of Attraction - Algorithmus I


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

Einzugsbereiche der Nullstellen für f(x)=x^3-x beim Newton-Verfahren
Einzugsbereiche der Nullstellen für f(x)=x^5-2x^4-10x^3+20x^2+9x-18 beim Newton-Verfahren

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. Basins of Attraction für z^2-1=0) und im Fall komplexer Funktionen mit drei oder mehr Nullstellen zeigt der Plot jedoch ein Fraktal [1] mit entsprechenden farbigen Teilbereichen in B für die Nullstellen (basins of attraction). Das folgende Beispiel zeigt für das komplexe Newton-Verfahren die Einzugsbereiche der Funktion f (z) = z³ - 1 für den Bereich B = [-2, 2] x [-2, 2].

Zwei-Schritt-Verfahren (two-step methods)

Bei den Zwei-Schritt-Verfahren (two-step methods) wird für jeden Iterationsschritt i zunächst ein Zwischenwert (predictor) berechnet. Üblicherweise wird hierzu das Newton-Verfahren verwendet. Der Zwischenwert wird dann mit dem "eigentlichen" Verfahren verbessert (corrector) (vgl. Erklärung beim Ostrowski-Verfahren für reelle Funktionen).

 

Konvergenzgeschwindigkeit

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

z0 ϵ B beim jeweilig angewandten Iterationsverfahren. Hierbei wird, ausgehend vom Startwert z0 , solange iteriert, bis die Abbruchbedingung |zi - zi-1 | ≤ ε  erfüllt ist. z0 ϵ 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 z0 ϵ B die Farbe schwarz zugeordnet, falls die maximale Iterationsanzahl erreicht wird. Hier der zugehörige Algorithmus in Pseudocode:

Algorithmus II  -  Konvergenzgeschwindigkeit

Algorithmus II : Konvergenzgeschwindigkeit des Iterationsverfahrens für komplexe Nullstellen

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 z0 ϵ B sehr verschiedene Größenordnungen annehmen. Bei insgesamt sehr kleinen Werten für B sieht man bei der vorgegebenen Regenbogen-Palette kaum Unterschiede (s.linkes Bild in folgender Galerie). Mittels p_step  können die Werte von i  entlang der Palette "gestreckt" werden (s. mittleres Bild in folgender Galerie mit p_step=9).

 

Um z0 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 oben verwendete Funktion f (z ) = z³ - 1 für B mit Re [-2, 2] , Im [-2, 2]  folgende Fraktale:


Quellenverweise

 

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