EINE GESCHWINDIGKEITSGRENZE VON 1974 FÜR DAS LÖSEN VON GLEICHUNGEN, ENDLICH BEWIESEN

Um herauszufinden, wo eine Funktion f die Null kreuzt, führt ein Computer oft eine Iteration aus: Er beginnt bei einem Schätzwert x, stellt der Funktion einige Fragen, berechnet einen besseren Schätzwert und wiederholt das. Die Fragen sind Auswertungen: der Wert von f an einer Stelle oder der ihrer Steigung (der Ableitung) oder einer höheren Ableitung.

Stellen, die sich verdoppeln

Die Geschwindigkeit eines solchen Verfahrens wird an seiner Ordnung gemessen. Ist der aktuelle Fehler ε, hinterlässt eine Iteration der Ordnung p einen Fehler von ungefähr ε hoch p. Ordnung 2 bedeutet, dass sich nahe an der Antwort die Zahl der korrekten Stellen bei jedem Schritt verdoppelt; Ordnung 4, dass sie sich vervierfacht.

Das Newton-Verfahren verwendet zwei Auswertungen pro Schritt – f(x) und seine Steigung f′(x) – und geht zu x − f(x)/f′(x) über. Es hat die Ordnung 2. Mehr Fragen pro Schritt können mehr Geschwindigkeit bringen. Die Frage ist, wie viel.

Eine Vermutung von 1974

1974 schlugen H. T. Kung und J. F. Traub eine Antwort vor, als „Conjecture 8.1“ einer Arbeit im Journal of the ACM: Eine Iteration ohne Gedächtnis, die n Auswertungen pro Schritt verwendet, hat höchstens die Ordnung 2ⁿ⁻¹. „Ohne Gedächtnis“ bedeutet, dass das Verfahren von früheren Schritten nichts außer seinem aktuellen Schätzwert behält.

Die Schranke ließ sich nicht senken: Kung und Traub hatten selbst „Mehrpunktverfahren“ gebaut, die 2ⁿ⁻¹ für jedes n ≥ 2 erreichen – Ordnung 4 mit drei Auswertungen, 8 mit vier, 16 mit fünf. Was fehlte, war die andere Hälfte: ein Beweis, dass kein Verfahren es besser kann. Teilergebnisse kamen zusammen mit der Vermutung und danach. Die Schranke wurde für interpolationsbasierte Verfahren bewiesen, für rationale Verfahren mit zwei Auswertungen und unter verschiedenen Zusatzbedingungen; für Verfahren, die nur Funktionswerte verwenden, wurde eine schwächere Schranke, 2ⁿ, nachgewiesen. Der allgemeine Fall blieb offen.

Den Algorithmus täuschen

Matthew Colbrook vom Department of Applied Mathematics and Theoretical Physics der University of Cambridge beweist sie nun vollständig. Das Modell ist bewusst großzügig gegenüber dem Algorithmus. Er darf unterwegs wählen, wo er auswertet und welche Ableitungen er bildet. Er darf die Antworten auf jede beliebige deterministische Weise verarbeiten, ohne dass von seinen Regeln irgendeine Glattheit verlangt wird.

Der Beweis wendet den Determinismus des Algorithmus gegen ihn selbst. Man konstruiere zwei Funktionen, die auf alle seine Fragen genau dieselben Antworten geben, aber verschiedene Nullstellen haben. Der Algorithmus muss für beide denselben Schätzwert liefern, also verfehlt er bei einer von ihnen das Ziel um mindestens die Hälfte des Abstands zwischen den beiden Nullstellen.

Um solche Paare zu finden, verschiebt Colbrook eine Referenzfunktion um ein kleines Polynom vom Grad höchstens n, das n + 1 einstellbare Koeffizienten hat. Jede Auswertung legt höchstens eine Kombination davon fest, sodass nach n Fragen einige Verschiebungen für den Algorithmus unsichtbar bleiben. Diese Abzählung allein genügt nicht: Eine unsichtbare Verschiebung könnte die Nullstelle kaum bewegen.

Das zentrale Werkzeug ist die Wronski-Determinante – eine Determinante, die aus einer Familie von Polynomen und deren Ableitungen gebildet wird. Ein neues Lemma besagt: Hat ein Polynom der Familie viele Nullstellen, die in einer kleinen Kreisscheibe dicht beieinanderliegen, muss die Wronski-Determinante der Familie in der Nähe verschwinden. Indem der Beweis dem Algorithmus stets mit einer Funktion antwortet, deren Nullstelle von diesen wenigen Punkten fernbleibt, hält er die Nullstelle frei beweglich.

Die Buchführung liefert den Exponenten. Beginnt man in einem Abstand ε von der Nullstelle, bleiben die möglichen Nullstellen über einen Bereich verteilt, der mindestens eine Konstante mal eine Potenz von ε groß ist. Wie es in der Arbeit heißt, „bleibt der Exponent nach der ersten Beobachtung gleich eins und verdoppelt sich dann, was nach n Beobachtungen 2ⁿ⁻¹ ergibt“.

Eine Funktion für jede Größenordnung

Eine Schwierigkeit blieb. Die Definition der Ordnung erlaubt, dass die vorangestellte Konstante von der Funktion abhängt, sodass eine andere ungünstige Funktion auf jeder Größenordnung nichts beweist. Colbrook konstruiert deshalb eine einzige Funktion, indem nacheinander Korrekturen hinzugefügt werden, von denen jede an allen Punkten verschwindet, die der Algorithmus bereits abgefragt hat, sodass alle bisherigen Antworten exakt gleich bleiben.

Der Grenzwert ist eine ganze Funktion – überall glatt, sogar über den komplexen Zahlen –, deren Steigung auf der reellen Achse zwischen 3/4 und 5/4 bleibt: eine stetig ansteigende Kurve mit einer gutartigen Nullstelle. Für jedes p über 2ⁿ⁻¹ erreicht das Verfahren auf ihr die Ordnung p nicht. Die optimale Ordnung ohne Gedächtnis ist daher für n ≥ 2 genau 2ⁿ⁻¹. Die Arbeit beweist dieselbe Schranke, wenn die Auswertungen komplexe Zahlen sind.

Der Preis dafür, alles auf einmal zu fragen

Eine schärfere Aussage betrifft Auswertungen, die in Gruppen erfolgen, wobei jede Frage einer Gruppe gewählt wird, bevor eine ihrer Antworten eintrifft – die Situation paralleler Verfahren. Mit Gruppen der Größen ℓ₁, …, ℓₖ ist die Ordnung höchstens ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). Alle n Fragen auf einmal zu stellen, begrenzt die Ordnung auf n; sie einzeln nacheinander zu stellen, erlaubt 2ⁿ⁻¹. Bei fünf Auswertungen heißt das 5 gegen 16.

Von der Maschine geprüft

Die Ergebnisse sind in Lean formal verifiziert, einem Beweisassistenten, der jeden logischen Schritt überprüft. Der Code ist öffentlich und im Palomar-Register eingetragen. Laut der Arbeit wurde die Formalisierung in Lean mit Hilfe von ChatGPT 6 durchgeführt und anschließend mit dem Lean 4 Comparator gegen die Theoreme der Arbeit geprüft; jedes Argument wurde von Colbrook überprüft, und Colbrook übernimmt die volle Verantwortung für den Inhalt.

Die Grenze betrifft Verfahren, die vergessen. Verfahren, die ihre früheren Schritte wiederverwenden dürfen, gehorchen anderen Schranken, die diese Arbeit beiseitelässt.