Newtonfraktal
Das Newtonfraktal zu einer nicht-konstanten meromorphen Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} , die die komplexen Zahlen in sich abbildet, ist eine Teilmenge der Menge der komplexen Zahlen. Genauer ist es die Julia-Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal J_f} zur Funktion
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\colon z\mapsto f(z) = z-\frac{p(z)}{p'(z)}, }
die das Newtonverfahren zum Auffinden von Nullstellen der Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} beschreibt. Das Newtonverfahren selbst konstruiert aus einem Startwert eine Folge mit der Rekursionsvorschrift Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z_{k+1} = f(z_k)} .
Abhängig vom Startwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z = z_0} kann der Orbit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z}
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z,\; f(z),\; f^2(z),\; f^3(z),\, \ldots }
ganz unterschiedliches Verhalten zeigen.
Anmerkung: Hier bezieht sich der Exponent auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} als Funktion, und nicht auf deren Funktionswert. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f^{\,n}} bedeutet also die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -fach iterierte Anwendung von auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} (oder das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -te Iterierte von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} ), formal also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f^{\,0}(z) = z , \, f^{\,n+1}(z) = f(f^{\,n}(z))} .
Für die Dynamik in einer Umgebung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} gibt es genau zwei Möglichkeiten:
- es gibt eine Umgebung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} , so dass die Folge der Abstände Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|z-w\|,\; \|f(z)-f(w)\|,\;\|f^2(z)-f^2(w)\|,\, \ldots } beschränkt ist, oder
- für jede (noch so kleine) Umgebung von überdecken die Bilder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U,\; f(U),\; f^2(U),\; f^3(U),\, \ldots } die gesamte komplexe Ebene samt dem Punkt unendlich (also die gesamte Riemannsche Zahlenkugel).
Die Punkte im ersten Fall bilden die Fatou-Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal F_f} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} , die Punkte im zweiten Fall die Julia-Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal J_f} . In der Fatou-Menge kann es insbesondere vorkommen, dass die Folge der Abstände gegen null konvergiert, sich die Orbits von Punkten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} also dem Orbit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} annähern. Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} mindestens drei Nullstellen hat, ist die Julia-Menge immer ein „Fraktal“; daher wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal J_f} gelegentlich auch „Newtonfraktal von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} “ genannt.
Bedeutung für das Newtonverfahren
Liegt der Startwert der Newtoniteration nahe an einer einfachen Nullstelle von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} , dann konvergiert das Verfahren quadratisch gegen diese Nullstelle (d. h., die Anzahl der korrekten Dezimalziffern verdoppelt sich langfristig in jedem Schritt). Bei einer mehrfachen Nullstelle ist das Newtonverfahren immerhin noch linear konvergent. Nullstellen liegen immer in der Fatou-Menge.
Je näher der Startwert jedoch an der Julia-Menge liegt, desto unüberschaubarer ist das Resultat des Newtonverfahrens:
- Selbst Startwerte, die weit von einer Nullstelle entfernt liegen, können zu dieser hin konvergieren, auch wenn andere Nullstellen wesentlich näher am Startwert liegen (zu Fall 1).
- Es gibt Startwerte, die nicht gegen eine Nullstelle konvergieren, sondern lediglich gegen einen periodischen Zyklus (zu Fall 1). Ein Beispiel dafür ist das Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z^3-2z+2} . Hier gibt es Startwerte, die vom anziehenden Zyklus {0,1} eingefangen werden, so dass ganze Flächen in der Ebene gegen keine Nullstelle konvergieren.
- Liegt der Startwert in der Julia-Menge selbst, dann konvergiert er nicht gegen eine Nullstelle (zu Fall 2).
Überraschenderweise kann die Julia-Menge (das Newtonfraktal) auch positives Maß in der Ebene haben: das heißt, dass zufällige Startwerte in der Julia-Menge liegen und damit nicht gegen eine Nullstelle (oder einen anderen anziehenden Zyklus von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} ) konvergieren (dieses Verhalten kommt nur in wenigen Fällen vor und wurde auch erst vor wenigen Jahren bewiesen, ist aber durchaus möglich). Selbst wenn das Newtonfraktal eine Nullmenge ist, kann es also ganze Gebiete geben, in denen das Verfahren nicht gegen eine Nullstelle konvergiert.
Diese Feststellung gilt auch für reellwertige rationale Funktionen. Wiederum dient das Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z^3-2z+2} als Beispiel. Weil es reelle Koeffizienten hat, bleiben die Werte der Newtoniteration für reelle Startwert reellwertig. Da die reelle Achse durch Gebiete der Nichtkonvergenz verläuft, gibt es Intervalle, für die keine Konvergenz vorliegt. Von solchen Intervallen gibt es unendlich viele.
Beispielfraktale
Beispiel 1
Abbildung 1 zeigt das Newtonfraktal (in weiß) zu Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle z^{3}-2z+2} , farbcodiert nach Konvergenzgeschwindigkeit und den drei Nullstellen. Startwerte, die in den beige gezeichneten Gebieten liegen, konvergieren gegen die gleiche Nullstelle (im Bild links in hellbeige), analog für das grüne und das blaue Gebiet. Die Nullstellen zum grünen bzw. blauen Gebiet liegen symmetrisch zur waagerechten Symmetrieachse rechts im Bild. Je schneller ein Startwert zu seiner Nullstelle konvergiert, desto heller ist er eingefärbt. Die Werte in den unendlich vielen roten Bereichen konvergieren nicht gegen eine Nullstelle, sondern werden vom anziehenden Zyklus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{0,1\}} eingefangen. Das Newtonfraktal – im Bild als helle Struktur erkennbar – ist nicht beschränkt. In den drei zu erkennenden Richtungen reicht es bis nach ∞.
Beispiel 2
Abbildung 2 zeigt das Newtonfraktal zu einem Polynom mit 7 zufällig gewählten Nullstellen (weiße Punkte), der Bereich stellt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -1 < \operatorname{Re} (z), \operatorname{Im} (z) < 1} dar. Das Fraktal selbst ist z. B. der Rand des gelben Gebietes. Ebenso ist es der Rand des grünen Gebietes, der Rand des türkisfarbenen Gebietes etc. Diese Eigenschaft ist allen Julia-Mengen gemein. (Die Farben rot und pink wurden doppelt verwendet; dennoch entsprechen auch die Grenzen des roten bzw. des pinkfarbenen Gebietes dem Newtonfraktal.)
Weblinks
- J. H. Hubbard, D. Schleicher, S. Sutherland: How to Find All Roots of Complex Polynomials by Newton’s Method. In: Inventiones Mathematicae, vol. 146, 2001 – mit Diskussion der Struktur von Newtonfraktalen
- D. Schleicher, Robin Stoll: Newton’s method in practice: finding all roots of polynomials of degree one million efficiently. Beschreibung des Newtonverfahrens in der Praxis, mit der alle Nullstellen von bestimmten Polynomen von Grad über einer Million gefunden werden, arxiv:1508.02935
