Newton-Verfahren: die Ästhetik des Scheiterns

Christoph Pöppe

Im letzten Beitrag hatte ich Ihnen vom Newton-Verfahren erzählt, jener klassischen Methode, die eine Lösung einer Gleichung mit unnachahmlicher Geschwindigkeit und Präzision findet. Das gilt für gewöhnliche Gleichungen mit einer einzigen Unbekannten ebenso wie für Gleichungssysteme, in der mehrere Unbekannte zugleich die richtigen Werte haben müssen, damit alle Gleichungen erfüllt werden.

Wie jedes empfindsame Wesen neigt auch das Newton-Verfahren gelegentlich zu heftigen Reaktionen, die es gewaltig in die Irre führen. An dieser Stelle hilft es, die Formel anzusehen, die das Verfahren beschreibt. Gesucht ist eine Nullstelle der differenzierbaren Funktion f, also ein x, für das die Gleichung f(x)=0 erfüllt ist. Wir haben vielleicht eine ungefähre Vorstellung von der Lösung und geben sie dem Verfahren als Anfangswert vor, nennen wir diese Zahl x₀. Dann schlägt das Verfahren der Reihe nach Zahlen x₁, x₂, x₃ … vor; die sollen der richtigen Lösung immer näher kommen. Und zwar macht es aus einem Vorschlag x_n einen verbesserten Vorschlag x_n+1 nach der Formel \[x_{n+1}=x_n-{f(x_n) \over f’(x_n)} \;.\] Wie kommt man zu der Formel? Man berechnet die Nullstelle der Tangente an der Stelle \(x_n\), die Steigung dieser Tangente ist \(f’(x_n)\), und der Rest ist eine einfache Umrechnung.

An dieser Stelle zeigt sich die Achillesferse des Verfahrens. Die Steigung der Tangente steht im Nenner; wenn der klein wird, dann wird der Sprung von x_n nach x_n+1 groß, das heißt, der nächste Vorschlag landet weit draußen, und wenn der Nenner gleich null ist, geht gar nichts mehr. Dann bricht das Verfahren zusammen.

Bei mehreren Unbekannten sieht die Formel im Wesentlichen genau so aus, nur ist dann die Ableitung eine ganze Matrix, und der Zusammenbruch findet statt, wenn die Matrix kein Inverses hat – wofür es noch ein viel größeres Sortiment an Möglichkeiten gibt.

Das mögen die Praktiker, die sich nur für eine Lösung interessieren, natürlich überhaupt nicht und suchen es nach Kräften zu vermeiden, zum Beispiel indem sie dem Verfahren Zügel anlegen. Hier allerdings möchte ich ganz im Gegenteil das Verfahren geradezu lustvoll scheitern lassen. Am Ende bilden die Punkte des Scheiterns eine Struktur, die in ganz anderem Kontext große Aufmerksamkeit erregt hat: ein Fraktal.

Man kann die Gleichung, um die es geht, als zwei (reelle) Gleichungen mit zwei (reellen) Unbekannten auffassen. Aber das würde die Sache eher verschleiern als klären. Besser ist es, man geht zu den komplexen Zahlen über. Wie war das? Eine komplexe Zahl sind zwei reelle. Anstelle des Zahlenpaars (a, b) schreibt man a+bi; dabei ist die „imaginäre Einheit“ i jene merkwürdige Zahl, deren Quadrat gleich –1 ist. Und wundersamerweise sind mit dieser Festlegung die komplexen Zahlen ein „Körper“, also eine Menge, in der man hemmungslos addieren, subtrahieren, multiplizieren und dividieren kann, mit der einzigen Einschränkung, dass die Division durch null nicht geht.

Komplexe Zahlen kann man als Punkte in der Ebene darstellen – kein Wunder, es sind ja Paare reeller Zahlen – und sich damit ein Bild vom Verhalten komplexer Funktionen machen. Ich hatte in einem früheren Beitrag eine spezielle Sorte komplexer Funktionen besprochen, die holomorphen Funktionen, und dabei deren farbenfrohe und überaus instruktive Darstellungen durch Elias Wegert gepriesen. Umso erfreulicher ist es, dass Wegerts Kalender „Complex Beauties“, deren Internet-Heimat einem Hackerangriff zum Opfer gefallen war, mittlerweile wieder zugänglich sind.

Aber zurück zum Newton-Verfahren. Die Funktion, um deren Nullstellen es geht, lautet \(f(z)=z^3-1\). (Es ist üblich, die Variable z statt x zu nennen, wenn es um komplexe Zahlen geht.) Im Reellen wäre die Sache ausgesprochen langweilig. Man sieht sofort, dass z=1 eine Lösung ist, und mit etwas Nachdenken auch, dass es die einzige Lösung ist. Wenn man das Newton-Verfahren in z=0 startet (das ist die einzige Stelle, an der \(f’(z)=3z^2=0\) ist), versagt es; von allen anderen Stellen aus landet es über kurz oder lang bei der Eins – es steht ja keine andere Lösung zur Auswahl. Was wilde Bocksprünge unterwegs nicht ausschließt.

Im Komplexen gibt es dagegen drei Lösungen der Gleichung, außer der Eins noch zwei weitere, die ebenfalls auf dem Einheitskreis liegen (dem Kreis um den Nullpunkt mit Radius 1), und zwar so, dass alle drei ein gleichseitiges Dreieck bilden (die „dritten Einheitswurzeln“). Wenn man nun das Newton-Verfahren auf irgendeinen Punkt der komplexen Ebene setzt: Wo wird es wohl hinspringen?

Ich stelle mir tatsächlich gerne einen Floh vor, der über die komplexe Ebene hüpft, und zwar nach einer sehr strengen Vorschrift: An dem Punkt z_n, auf dem er sitzt, findet er eine Anweisung vor, die ihm den Punkt z_n+1 ansagt, zu dem er hinspringen soll; die Anweisung lautet wie im Reellen \(z_{n+1}=z_n-{f(z_n) \over f’(z_n)} \). Dort angekommen, findet er die entsprechende neue Anweisung vor, folgt ihr, und so weiter.

Wenn man den Floh in der Nähe einer dritten Einheitswurzel starten lässt, wird er dieser wohl zustreben. Sitzt er auf einer solchen Lösung, so bleibt er da in alle Ewigkeit: Jede Lösung ist ein „Fixpunkt“ der Iteration, die durch das Newton-Verfahren definiert wird. Auf kurze Entfernung übt ein Fixpunkt so etwas wie eine Anziehungskraft aus. Das darf man sich nicht allzu physikalisch vorstellen. Vor allem hat der Floh keine Massenträgheit und kann deshalb nicht übers Ziel hinausschießen. Aber wenn man es nicht zu wörtlich nimmt, trifft das Bild von dem Fixpunkt, der alles gierig in sich hineinsaugt, was in seine Umgebung gerät, und nichts mehr loslässt, die Sache durchaus.

Nun sind allerdings drei Fixpunkte im Spiel, und jeder hat seinen Machtbereich (der in der englischen Literatur „basin of attraction“ heißt). Was macht ein Floh, der irgendwo auf der Grenze zwischen zwei Machtbereichen sitzt? Und wie sieht diese Grenze überhaupt aus?
Wer sie noch nie gesehen hat, wird jetzt eine Überraschung erleben:

Es besteht allerdings eine gute Chance, dass Sie dieses Bild so oder so ähnlich schon einmal gesehen haben. Es ist nämlich einerseits einfach zu programmieren: Für jedes Pixel des Bildes setzt man das Newton-Verfahren an dem entsprechenden Punkt der komplexen Ebene an und lässt es laufen, bis klar ist, zu welchem Fixpunkt es strebt. Dann färbt man das Pixel in der zugehörigen Farbe ein. Der Autor des vorliegenden Bildes hat darüber hinaus die Schattierung umso heller gewählt, je rascher das Verfahren sich dem jeweiligen Fixpunkt nähert.

Andererseits ist die unendlich zerknitterte Grenze zwischen den Machtbereichen ein klassisches Beispiel für ein Fraktal. Und Fraktale sind ein umfangreiches Thema für sich. Nachdem Benoît Mandelbrot (1924–2010) den Begriff populär gemacht und mit allerlei faszinierenden Bildern angereichert hatte, eroberte die „fraktale Geometrie der Natur“ (so der Titel eines einflussreichen Buchs von Mandelbrot) die wissenschaftlichen ebenso wie die allgemeinen Medien.

Einige Eigenschaften fraktaler Gebilde sieht man dem Bild unmittelbar an. Die „Grenze“, das heißt die Menge aller Punkte, die unter der Newton-Iteration nicht gegen einen der Fixpunkte streben, sondern irgendwann auf die tödliche Null geraten oder auf ewig im Kreis hüpfen, ist selbstähnlich: Man nehme einen beliebigen Ausschnitt, vergrößere ihn geeignet und verzerre ihn vielleicht ein bisschen, dann kommt er mit der ursprünglichen Menge zur Deckung! Man sieht zum Beispiel, dass die charakteristischen „Tropfen“ – das spitze Ende zum Nullpunkt gerichtet, das stumpfe nach außen – aus kleinen Tropfen bestehen, die ihrerseits aus noch kleineren Tröpfchen bestehen, und so weiter bis ins unendlich Kleine.

Wie bei Fraktalen üblich, verfügt auch diese Grenze über Eigenschaften, die man zunächst für unmöglich halten würde: Jeder ihrer Punkte ist ein Dreiländereck! Das heißt, in nächster Umgebung der Grenze finden sich stets rote, grüne und blaue Punkte. Und jedes der drei Reiche besteht aus einem „Mutterland“ und unendlich vielen Exklaven. Das kann man nachvollziehen, bis die Einzelheiten in der begrenzten Bildauflösung verschwinden. Und die Selbstähnlichkeit sorgt dafür, dass das bis ins unendlich Kleine so weitergeht.

Damit hat das Newton-Verfahren die in ihm steckende Wildheit eindrucksvoll demonstriert. Praktiker arbeiten lieber mit gedämpften Versionen. Zum Schluss noch, mehr zum Vergnügen als zur Vermittlung mathematischen Tiefsinns, ein paar Beispiele dafür, was passiert, wenn das Verfahren nicht nur nicht gedämpft, sondern im Gegenteil „enthemmt“ wird. Auf das Finden eines Fixpunkts kommt es dabei nicht mehr an; aber die selbstähnliche Struktur tritt noch deutlich eindrucksvoller zu Tage.

Einen besonderen Dreh bekommt die Sache, wenn das Verfahren nicht einfach überschießt, sondern nach dem Ende eines Schritts um 90 Grad nach links abbiegt und dieselbe Entfernung nochmals zurücklegt. Da erzeugt selbst die einfachere Gleichung z²–1=0 fraktale Tannenbäumchen.

The post Newton-Verfahren: die Ästhetik des Scheiterns originally appeared on the HLFF SciLogs blog.