Dies ist eine maschinelle Übersetzung; das englische Original ist die maßgebliche Fassung. Original lesen
Eine Halbierung der Schrittweite sollte den Fehler halbieren. Das Werkzeug meldet 1,73.
Die Seite gibt das Verhältnis selbst an: 0,000405 bei h = 0,2; 0,000234 bei der Hälfte davon. Dividiert man die beiden Werte, erhält man 1,73 statt 2 – und nichts daran ist fehlerhaft.
Das Euler-Verfahren ist erster Ordnung. Das steht in jedem Lehrbuch, und es bedeutet, dass der Fehler proportional zur Schrittweite h ist; eine Halbierung von h sollte den Fehler also halbieren.
Öffnet man Euler's method mit den Standardeinstellungen: y′ = x − y, y(0) = 1, vierzig Schritte mit h = 0,2, endend bei x = 8. Die Seite weist einen globalen Fehler von 0,000405 aus und tut dann etwas ungewöhnlich Ehrliches: Sie führt das Ganze noch einmal mit h/2 aus und gibt auch diesen Fehler an, 0,000234, samt dem Verhältnis zwischen beiden:
Eh / Eh/2 = 0,000405 / 0,000234 = 1,731285
Nicht 2. Das Verfahren ist erster Ordnung, die Rechnung stimmt, und das Halbieren der Schrittweite brachte eine Verringerung um 42 % statt um 50 %.
Den Bereich durchfahren, nicht bloß Stichproben nehmen
Zwei Zahlen können nur eine Richtung vorgeben. Verfolgt man das Verhältnis über den gesamten Bereich und behält den Endpunkt bei x = 8 bei, indem man die Schrittzahl mit jeder Halbierung von h verdoppelt, erhält man:
- h = 0,4 → Verhältnis 1,475764
- h = 0,2 → Verhältnis 1,731285
- h = 0,1 → Verhältnis 1,865689
- h = 0,05 → Verhältnis 1,933036
- h = 0,025 → Verhältnis 1,966586
Die versprochene 2 ist ein Grenzwert, und so sieht die Annäherung daran aus. Doch die interessante Spalte ist nicht das Verhältnis, sondern der Rückstand: wie weit jeder Messwert unter 2 liegt:
0,524 → 0,269 → 0,134 → 0,067 → 0,033
Dieser Wert halbiert sich jedes Mal, wenn sich h halbiert. Die Lücke zwischen „erster Ordnung“ und dem, was erste Ordnung tatsächlich liefert, ist in h selbst von erster Ordnung.
Woher die fehlende Hälfte kommt
Die Ordnung rührt von einem Abbruch her. Euler behält den ersten Term der Taylor-Entwicklung der Lösung bei und verwirft alles ab der zweiten Ableitung, was das Taylor tool sichtbar macht: Die verworfenen Terme enthalten h², h³ und so weiter. Ein einzelner Schritt verliert daher eine Größe von der Ordnung h², und um x = 8 zu erreichen, braucht es 8/h solcher Schritte; so wird aus h² pro Schritt in der Summe h. Das „erste“ in erster Ordnung ist bereits eine Aussage über eine Summe.
Der globale Fehler ist also nicht C·h. Er lautet
E(h) = C₁h + C₂h² + C₃h³ + ⋯
und das Verhältnis zweier solcher Summen ist
E(h) / E(h/2) = (C₁h + C₂h² + ⋯) / (C₁h/2 + C₂h²/4 + ⋯)
was gegen 2 strebt, wenn h schrumpft und der h²-Term schneller verschwindet als der h-Term. Doch bei jedem endlichen h ist der zweite Term weiterhin vorhanden und trägt überproportional zum Nenner bei. „Erste Ordnung“ benennt den Term, der am längsten überlebt, nicht den einzigen vorhandenen Term. Bei h = 0,4 zehrt der h²-Beitrag ein Viertel des versprochenen Faktors zwei auf, und das Verhältnis liegt bei 1,476.
Dasselbe zeigt sich in der Fehlerspalte der Schritt-Tabelle auf der Seite. Der fortlaufende Fehler steigt nicht stetig an: Er wächst bis x = 0,8 auf etwa 0,0804 an, fällt dann, wenn die Lösung flacher verläuft, und endet bei den in der Zusammenfassung angegebenen 0,000405. Der globale Fehler ist eine Summe lokaler Fehler, die sich teilweise gegenseitig aufheben – und es gibt keinen Grund, warum diese Summe bei einer Schrittweite, die man in der Praxis tatsächlich verwenden würde, ein glattes Vielfaches von h sein sollte.
Warum dies von Bedeutung ist – und keine Pedanterie
Der Standardweg zur Schätzung eines nicht berechenbaren Fehlers ist die Richardson-Extrapolation, und sie funktioniert, indem man das Verhältnis voraussetzt. Man rechnet mit h, man rechnet mit h/2, und wenn das Verfahren von der Ordnung p ist, entspricht die Differenz zwischen beiden Ergebnissen etwa dem (2p − 1)-Fachen des Fehlers der feineren Rechnung. Für das Euler-Verfahren gilt p = 1, die Differenz ist also ungefähr gleich dem verbleibenden Fehler.
Wendet man diese Überlegung auf h = 0,4 an, setzt man ein Verhältnis von 2 voraus, obwohl der wahre Wert bei 1,476 liegt. Rechnet man dies durch: Die Schätzung, die man erhält, beträgt das 0,476-Fache des tatsächlich verbleibenden Fehlers; sie unterschätzt ihn also um einen Faktor von etwa zwei – und sie unterschätzt ihn, statt ihn zu überschätzen. Man wiegt sich in dem Glauben, das Ergebnis sei besser als es tatsächlich ist – und diese Zuversicht wächst ausgerechnet dann, wenn die Schrittweite gröber wird, also genau dann, wenn man es am wenigsten gebrauchen kann.
Der Schutz davor ist genau das, was die Seite vorführt: das Verhältnis nicht vorauszusetzen, sondern zu messen. Zwei Durchläufe liefern das Verhältnis; drei zeigen dessen Trend. Liegt das Verhältnis für das angenommene p nicht nahe bei 2p, dann ist entweder der Schritt zu grob für den asymptotischen Bereich, oder das Verfahren hat nicht die vermutete Ordnung, oder die Lösung weist eine Eigenschaft auf, die in der Analyse nicht vorhergesehen wurde. Alle drei Umstände sollte man kennen, bevor man ein Ergebnis angibt.
Das Argument für ein besseres Verfahren, nicht für einen kleineren Schritt
Die Halbierung der Schrittweite verdoppelt den Rechenaufwand. Bei einem Verfahren erster Ordnung bringt das letztlich einen Faktor zwei. Das ist ein schlechter Tausch und der Grund, warum in der Praxis so gut wie nichts mit dem Euler-Verfahren integriert wird.
Simpson's rule ist vierter Ordnung: Die Halbierung ihrer Schrittweite teilt den Fehler durch etwa 16; dieselbe Verdopplung des Aufwands bringt also achtmal mehr Genauigkeit als die Verdopplung beim Euler-Verfahren. Die Verfahren von Runge und Kutta leisten das Entsprechende für Differentialgleichungen, und Butchers geschichtlicher Abriss in den Quellenangaben führt diese Entwicklungslinie auf Runge im Jahr 1895 und Kutta im Jahr 1901 zurück.
Das Grundprinzip lohnt es sich mitzunehmen: Bei einem Verfahren der Ordnung p beträgt der Wechselkurs 2p an Genauigkeit pro Verdopplung des Aufwands, und p ist eine Eigenschaft des Algorithmus, nicht des Problems. Die Wahl des Verfahrens bestimmt den Wechselkurs. Die Wahl der Schrittweite bewegt einen lediglich darauf entlang – und wie der obige Durchlauf zeigt, tut sie das nicht einmal mit der versprochenen Rate, bis h klein genug ist, dass das Versprechen zur Realität geworden ist.