Newton-Fraktal

Das Newton-Verfahren sucht eine Nullstelle eines Polynoms $p$, indem es ausgehend von einem Startpunkt $z_0$ einen Schritt wiederholt:

Jedes Pixel des Bildes ist ein Startpunkt in der komplexen Ebene. Es erhält die Farbe der Nullstelle, in deren Kreisscheibe es zuerst eintritt. Jede Kreisscheibe ist mathematisch abgesichert: Nach Smales γ-Satz konvergiert das Newton-Verfahren von jedem Startpunkt darin zu dieser Nullstelle. Eine Farbe ist also niemals eine Vermutung anhand der Frage, welche Nullstelle am nächsten liegt. Um eine einfache Nullstelle $\zeta$ hat die Kreisscheibe den Radius $(3-\sqrt7)/(2\gamma)$, wobei $\gamma = \max_{k\ge2}\bigl|p^{(k)}(\zeta)/(k!\,p'(\zeta))\bigr|^{1/(k-1)}$.

Die Schattierung zeigt, wie viele Schritte ein Startpunkt braucht, um eine Kreisscheibe zu erreichen; die Hell-Dunkel-Darstellung hängt von der gewählten Darstellung ab. Die dünnen Linien markieren die Ränder der „Startpunkte, die innerhalb von k Schritten eine Kreisscheibe erreichen“ — die Stufen, die die rote Taste einzeln zeigt. Schwarz bedeutet nur, dass ein Startpunkt in den ausprobierten Schritten in keine Kreisscheibe eingetreten ist. Die weiche Schattierung, das Leuchten entlang des Randes und der goldene Draht in der Darstellung „Goldglanz“ dienen nur der Anzeige; zu welcher Nullstelle ein Pixel gelangt und in wie vielen Schritten, sind numerische Ergebnisse einer 32-Bit-Berechnung.

Das gesamte Einzugsgebiet einer Nullstelle umfasst alle Startpunkte, die sie schließlich erreichen, einschließlich der kleinen Teile weit entfernt von der Nullstelle. Alle diese Einzugsgebiete haben ein und denselben Rand: die Julia-Menge der Abbildung $N$. Beliebig nahe an jedem Randpunkt gibt es daher Startpunkte, die zu jeder der Nullstellen gelangen. Deshalb wechseln sich die Farben auf jeder Größenordnung ab, und deshalb zeigt die Option „Das gesamte Einzugsgebiet einer Nullstelle zeigen“ dieses in jeder Perle entlang des Randes.

Nahe diesem Rand können wenige Schritte des Newton-Verfahrens benachbarte Startpunkte weit auseinanderziehen. Im Beispiel „Nur ein Haarbreit auseinander“ haben zwei Startpunkte für $z^3-1$ zunächst Abstand 0.02, nach einem Schritt 0.047 und nach zwei Schritten 0.268; sie treten bei den Schritten 6 und 7 in die Kreisscheiben verschiedener Nullstellen ein.

Mit nur zwei Nullstellen ist das Bild einfach: Der Rand ist die Mittelsenkrechte der beiden Nullstellen. In der Koordinate $w = (z-1)/(z+1)$ (Nullstellen bei ±1) wird der Newton-Schritt zu $w \mapsto w^2$. Mit einer dritten Nullstelle wird der Rand zu einem Fraktal.

Für $p(z) = z^3 - 2z + 2$ gelangt der Startpunkt 0 zu 1 und zurück zu 0, immer weiter: ein Zyklus, dessen Multiplikator $N'(0)\,N'(1)$ gleich 0 ist. Daher gerät auch jeder hinreichend nahe Startpunkt in diesen Zyklus. Diese Startpunkte bilden die schwarzen Inseln; sie erreichen niemals eine Nullstelle.

Wo können solche Zyklen auftreten? $N' = p\,p''/p'^2$ verschwindet an jeder Nullstelle, also ist jede Nullstelle ein kritischer Punkt von $N$ und liegt in ihrem eigenen Einzugsgebiet. Die übrigen kritischen Punkte — die freien kritischen Punkte — sind die Nullstellen von $p''$, die keine Nullstellen des Polynoms sind; wo auch $p'$ verschwindet, hat $N$ eine mehrfache Polstelle, die weiterhin ein kritischer Punkt ist und auf ∞ abgebildet wird. Nach einem Satz von Fatou zieht jeder anziehende Zyklus mindestens einen kritischen Punkt an. Ein Zyklus, der keine Nullstelle ist, kann keine Nullstelle anziehen, denn diese bleibt in ihrem eigenen Einzugsgebiet. Er muss also einen freien kritischen Punkt anziehen. Das Verfolgen der freien kritischen Punkte kann daher diese Fälle des Scheiterns aufdecken. Die Liste verwendet numerische Näherungen; lassen sich Nullstellen nicht zuverlässig voneinander trennen, meldet sie diese als ungeklärt, statt einen mehrfachen Punkt oder eine Polstelle festzustellen. Die Umkehrung gilt nicht: Für $z^3-1$ ist der freie kritische Punkt 0 auch eine Nullstelle von $p'$; er wird auf ∞ abgebildet, einen abstoßenden Fixpunkt von $N$, und es gibt keine schwarzen Inseln.

Bei drei Nullstellen hat $p''$ eine Nullstelle, den Schwerpunkt der Nullstellen des Polynoms; sofern er nicht selbst eine Nullstelle des Polynoms ist (wie bei $z^3-z$), ist er der einzige freie kritische Punkt. Das kleine Teilbild ist eine Karte der Positionen für die ausgewählte Nullstelle, während die beiden anderen fest bleiben: Jeder Punkt erhält die Farbe der Nullstelle, in deren mathematisch abgesicherte Kreisscheibe die Bahn des Schwerpunkts eintritt, wenn die ausgewählte Nullstelle dorthin gesetzt wird, und ist schwarz, wenn sie innerhalb von 300 Schritten in keine eintritt. In dieser Familie kubischer Polynome zeigen die schwarzen Blöcke kleine Kopien der Struktur der Mandelbrot-Menge, die Curry, Garnett und Sullivan (1983) erstmals in Computerexperimenten beobachteten. Ziehe die ausgewählte Nullstelle durch einen solchen Block, und die schwarzen Inseln im Bild erscheinen und verschwinden. Bewegt man Nullstelle 1 von $z^3-2z+2$ auf der reellen Achse nach links durch ihren Block (das Beispiel „Durch den schwarzen Block“), verdoppelt sich die Periode des Zyklus, 2 → 4 → 8, bei etwa −1.8045 und −1.832 (numerisch) — wie auf der reellen Achse der Mandelbrot-Menge.

Arthur Cayley fragte 1879, welche Nullstelle das Newton-Verfahren von einem gegebenen komplexen Startpunkt aus findet; er löste den Fall zweier Nullstellen und fand den Fall mit drei Nullstellen schwierig. Pierre Fatou und Gaston Julia entwickelten um 1918–1920 die Theorie der Iteration rationaler Abbildungen, lange vor Computerbildern. Bilder der Newton-Einzugsgebiete und der Mandelbrot-ähnlichen Struktur in ihrem Parameterraum erschienen in den frühen 1980er-Jahren; Steve Smales Abschätzungen (1986) liefern die hier verwendeten mathematisch abgesicherten Kreisscheiben.