Dies ist eine maschinelle Übersetzung; das Original ist auf Englisch. Original lesen
Eine Halbierung der Schrittweite sollte den Fehler halbieren. Das Tool zeigt 1,73.
Die Seite gibt das Verhältnis selbst aus: 0,000405 bei h = 0,2 und 0,000234 bei der Hälfte davon. Dividiert man beide Zahlen, ergibt sich 1,73 und nicht 2, und nichts daran ist fehlerhaft.
Das Euler-Verfahren ist von erster Ordnung. Jedes Lehrbuch sagt das, und das bedeutet, dass der Fehler proportional zur Schrittweite h ist — eine Halbierung von h sollte den Fehler also halbieren.
Öffnen Sie 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 bei h/2 aus und gibt auch diesen Fehler an, 0,000234, zusammen mit dem Verhältnis dazwischen:
Eh / Eh/2 = 0,000405 / 0,000234 = 1,731285
Nicht 2. Das Verfahren ist von erster Ordnung, die Arithmetik ist korrekt, und die Halbierung des Schrittes brachte eine Reduktion um 42% statt um 50%.
Systematisch variieren, statt nur Stichproben zu nehmen
Zwei Zahlen können nur eine Richtung angeben. Verfolgen wir also das Verhältnis über einen Bereich hinweg, wobei der Endpunkt bei x = 8 fixiert bleibt, indem die Schrittanzahl bei jeder Halbierung von h verdoppelt wird:
- 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 an ihn aus. Die interessante Spalte ist jedoch nicht das Verhältnis, sondern das Defizit – also wie weit jeder Messwert unter 2 liegt:
0,524 → 0,269 → 0,134 → 0,067 → 0,033
Dieses halbiert sich jedes Mal, wenn h halbiert wird. Die Lücke zwischen der „ersten Ordnung“ und dem, was erste Ordnung tatsächlich liefert, ist selbst von erster Ordnung in h.
Woher die fehlende Hälfte kommt
Die Ordnung ergibt sich aus einem Abbruch. Das Euler-Verfahren behält das erste Glied 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.
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 abfällt als der h-Term – aber bei jedem endlichen h ist das zweite Glied weiterhin enthalten und trägt überproportional zum Nenner bei. „Erste Ordnung“ bezeichnet das Glied, das am längsten bestehen bleibt, nicht das einzige vorhandene. Bei h = 0,4 ist der h²-Beitrag groß genug, um ein Viertel der erwarteten Verbesserung aufzuzehren.
Das Gleiche lässt sich in der Fehlerspalte der Schritttabelle auf der Seite beobachten. Einzelne Schrittfehler summieren sich nicht gleichmäßig auf: Sie steigen bis etwa 0,0804 bei x = 0,8 an und fallen dann, wenn der Verlauf der Lösung flacher wird. Der globale Fehler ist eine Summe lokaler Fehler, die sich teilweise gegenseitig aufheben, und diese Summe hat keinen Grund, bei einer tatsächlich genutzten Schrittweite ein exaktes Vielfaches von h zu sein.
Warum das wichtig ist – und es ist keine Pedanterie
Der Standardweg zur Schätzung eines nicht berechenbaren Fehlers ist die Richardson-Extrapolation, und sie funktioniert, indem sie das Verhältnis voraussetzt. Rechnet man bei h und bei h/2, und ist das Verfahren von der Ordnung p, so entspricht die Differenz zwischen den beiden Ergebnissen etwa dem (2p − 1)-Fachen des Fehlers des feineren Durchlaufs. Für das Euler-Verfahren gilt p = 1, sodass die Differenz etwa gleich dem verbleibenden Fehler ist.
Setzt man h = 0,4 in diese Überlegung ein, hat man ein Verhältnis von 2 angenommen, wo das tatsächliche 1,476 beträgt. Rechnet man es durch: Die erhaltene Schätzung beträgt 0,476 des tatsächlich verbleibenden Fehlers, unterschätzt ihn also um etwa den Faktor zwei – und, das ist der entscheidende Punkt, sie unterschätzt ihn, anstatt ihn zu überschätzen. Man wird glauben, das Ergebnis sei besser als es ist, und dieses Vertrauen wird umso größer, je gröber der Schritt wird – genau dann, wenn man es am wenigsten gebrauchen kann.
Die Absicherung ist diejenige, die die Seite demonstriert: Nehmen Sie das Verhältnis nicht an, sondern messen Sie es. Zwei Durchläufe liefern das Verhältnis; drei liefern den Trend des Verhältnisses. Wenn das Verhältnis für das vermutete p nicht nahe bei 2p liegt, ist entweder der Schritt zu grob für den asymptotischen Bereich, oder das Verfahren hat nicht die geglaubte Ordnung, oder die Lösung weist eine Eigenschaft auf, die die Analyse nicht vorhergesehen hat. Alle drei Punkte sind es wert, geklärt zu werden, bevor man eine Zahl nennt.
Was ein Argument für ein besseres Verfahren ist, nicht für einen kleineren Schritt
Eine Halbierung des Schrittes verdoppelt den Aufwand. Bei einem Verfahren erster Ordnung bringt das schließlich einen Faktor zwei. Das ist ein schlechter Tausch, und deshalb wird in der Praxis nahezu nie mit dem Euler-Verfahren integriert.
Simpson's rule ist von vierter Ordnung: Die Halbierung ihrer Schrittweite verringert den Fehler um etwa 16, sodass dieselbe Verdopplung des Aufwands achtmal mehr Genauigkeit bringt als die Verdopplung beim Euler-Verfahren. Die Runge-Kutta-Verfahren leisten das Äquivalente für Differentialgleichungen, und Butchers Historie in den Literaturangaben zeichnet nach, wie schnell die Fachwelt die erste Ordnung aufgab, sobald sie eine Alternative hatte.
Die allgemeine Erkenntnis lohnt sich mitzunehmen: Für ein Verfahren der Ordnung p beträgt das Tauschverhältnis 2p an Genauigkeit pro Verdopplung des Aufwands, und p ist eine Eigenschaft des Algorithmus und nicht des Problems. Die Wahl des Verfahrens legt das Tauschverhältnis fest. Die Wahl der Schrittweite bewegt einen lediglich darauf entlang – und wie die obige Variation zeigt, tut sie das noch nicht einmal mit der angepriesenen Rate, bis h klein genug ist, dass das Versprechen wahr geworden ist.