Warum ergibt sich in der Gleitkomma-Arithmetik eine numerische Ungenauigkeit, wenn ein kleiner Term zu einer Differenz großer Terme hinzugefügt wird?

Ich habe das Buch Computersimulation von Flüssigkeiten von Allen und Tildesley gelesen . Ab Seite 71 diskutieren die Autoren die verschiedenen Algorithmen, mit denen Newtons Bewegungsgleichungen in Simulationen der Molekulardynamik (MD) integriert werden. Ab Seite 78 diskutieren die Autoren den Verlet-Algorithmus, bei dem es sich möglicherweise um den kanonischen Integrationsalgorithmus in MD handelt. Sie stellen fest:

Die wahrscheinlich am weitesten verbreitete Methode zur Integration der Bewegungsgleichungen ist die von Verlet (1967) eingeführte und Stormer (Gear 1971) zugeschriebene. Diese Methode ist eine direkte Lösung der Gleichung zweiter Ordnung $m_i \ddot{\textbf{r}}_i = \textbf{f}_i$ . Das Verfahren basiert auf Positionen $\textbf{r}(t)$ , Beschleunigungen $\textbf{a}(t)$ und den Positionen $\textbf{r}(t - \delta t)$ aus dem vorherigen Schritt. Die Gleichung zum Vorrücken der Positionen lautet wie folgt:

$$\tag{3.14}\textbf{r}(t + \delta t) = 2\textbf{r}(t) - \textbf{r}(t - \delta t) + \delta t^2 \textbf{a}(t).$$

In Bezug auf Gleichung (3.14) sind mehrere Punkte zu beachten. Es ist zu sehen, dass die Geschwindigkeiten überhaupt nicht auftreten. Sie wurden durch Addition der durch Taylor-Expansion um erhaltenen Gleichungen eliminiert $\textbf{r}(t)$:

$$\textbf{r}(t + \delta t) = \textbf{r}(t) + \delta t \textbf{v}(t) + (1/2) \delta t^2 \textbf{a}(t) + ...$$

$$\tag{3.15}\textbf{r}(t - \delta t) = \textbf{r}(t) - \delta t \textbf{v}(t) + (1/2) \delta t^2 \textbf{a}(t) - ... .$$

Später (auf Seite 80) geben die Autoren Folgendes an:

Gegenüber dem Verlet-Algorithmus kann die Form des Algorithmus unnötigerweise eine gewisse numerische Ungenauigkeit einführen. Dies entsteht, weil in Gleichung (3.14) ein kleiner Term ( $\mathcal{O}(\delta t^2)$ ) zu einer Differenz von großen Terms ( $\mathcal{O}(\delta t^0)$ ) addiert wird , um die Trajektorie zu erzeugen.

Ich vermute, dass der "kleine Term" $\delta t^2 \textbf{a}(t)$ ist und die "Differenz der großen Terme" $2\textbf{r}(t) - \textbf{r}(t - \delta t)$ .

Meine Frage ist, warum numerische Ungenauigkeit durch Hinzufügen eines kleinen Terms zu einem Unterschied von großen Terms entsteht.

Ich interessiere mich für einen eher grundsätzlichen, begrifflichen Grund, da mir Einzelheiten der Gleitkomma-Arithmetik überhaupt nicht bekannt sind. Kennen Sie auch Referenzen vom Typ "Überblick" (Bücher, Artikel oder Websites), die mich mit den Grundgedanken der Gleitkomma-Arithmetik in Verbindung mit dieser Frage bekannt machen? Vielen Dank für Ihre Zeit.

Ihre Beobachtung, dass die Form des Algorithmus unnötigerweise eine gewisse numerische Ungenauigkeit hervorruft, ist richtig. Ihre Erklärung ergibt sich jedoch, weil in Gleichung (3.14) ein kleiner Term ( ) zu einer Differenz großer Terme ( O ( δ t 0 ) ) addiert wird , um die Trajektorie zu erzeugen. '' ist falsch.$O(δt^2)$$O(δt^0)$

Der wahre Grund für die geringe numerische Instabilität von Verlets Algorithmus ist, dass er nur marginal stabil ist, da die Differenzgleichung (im Wesentlichen der Fall, in dem Sie a in Verlet vernachlässigen ) parasitär ist Lösung proportional zu k , wodurch die eingeführten Fehler in k linear anwachsen, wohingegen für ein vollständig stabiles Mehrschrittverfahren, das auf eine dissipative Differentialgleichung angewendet wird, das Fehlerwachstum begrenzt ist.$x_{k+1}=2x_k-x_{k-1}$$a$$k$$k$

Edit: Beachten Sie, dass das Buch über die numerische Simulation der Molekulardynamik ist, und für eine angemessene Genauigkeit der resultierenden Erwartungen immer braucht man eine große Anzahl von Schritten, wie die Genauigkeit Waage mit O ( N - 1 / 2 ) nur. (Oft liegt der Zeitschritt in Pikosekunden, um der intrinsischen Oszillationsskala zu folgen. Biologisch relevante Zeitskalen liegen jedoch in Millisekunden oder darüber ( N ∼ 10 9 ), obwohl normalerweise nicht so weit gerechnet wird.)$N$$O(N^{-1/2})$$N\sim 10^9$

Weitere Informationen finden Sie unter http://en.wikipedia.org/wiki/Linear_multistep_method#Stability_and_convergence

Wenn Sie nach einer guten Einführung suchen, würde ich David Goldbergs Was jeder Informatiker über Fließkommaarithmetik wissen sollte empfehlen . Es ist vielleicht ein bisschen zu detailliert, aber es ist kostenlos online verfügbar.

Wenn Sie eine gute Bibliothek haben, empfehle ich Michael Overtons Numerical Computing mit IEEE Floating Point Arithmetic oder die ersten Kapitel von Nick Highams Genauigkeit und Stabilität numerischer Algorithmen .

Was Allen und Tildesley speziell ansprechen, ist die numerische Löschung . Die kurze davon ist , dass , wenn Sie, sagen wir, nur drei Ziffern und Sie subtrahieren 100aus 101, erhalten Sie 1.00(in drei Ziffern). Die Zahl scheint auf drei Ziffern genau zu sein, aber tatsächlich ist nur die erste Ziffer wahr und das Ende .00ist Müll. Warum? Nun, 100und 101sind nur ungenaue Darstellungen von, sagen wir, 100.12345und 101.4321, aber Sie konnten sie nur als dreistellige Zahlen speichern.

Um das Beispiel von Pedro auf die Gleichung anzuwenden , nehmen Sie an, dass Ihre Variablen mit den folgenden Werten gespeichert sind:$(3.14)$

r ( t - & dgr ; t ) = 100 & dgr; t 2 a ( t ) =

Aus sollte das folgen$(3.14)$

Da wir jedoch nur drei Ziffern verwenden können, wird das Ergebnis auf abgeschnitten

Dieser Fehler breitet sich aus, so dass Sie nach 20 Schritten unter der Annahme, dass unverändert bleibt, r ( t + 20 δ t ) = 331 anstelle von 433,90 erhalten .$\mathbf{a}(t)$$\mathbf{r}(t + 20\delta t) = 331$$433.90$

Pedro gibt bereits die wichtige Tatsache, nämlich Stornierung. Der Punkt ist, dass jede Zahl, mit der Sie rechnen, eine zugehörige Genauigkeit hat; Beispielsweise kann eine Gleitkommazahl mit einfacher Genauigkeit nur Dinge mit einer Genauigkeit von bis zu 8 Stellen darstellen. Wenn Sie zwei Zahlen haben, die fast genau gleich sind, sich aber in der 7. Ziffer unterscheiden, ist der Unterschied wieder eine 8-stellige Gleitkommazahl mit einfacher Genauigkeit, und es sieht so aus, als ob sie auf 8 Ziffern genau ist, in Wirklichkeit jedoch nur die erste 1 oder 2 Ziffern sind genau, da die Mengen, aus denen Sie sie berechnet haben, über diese ersten 1 oder 2 Ziffern der Differenz hinaus nicht genau sind.

Das Buch, das Sie zitieren, stammt aus dem Jahr 1989. Damals wurden Berechnungen meist in einfacher Genauigkeit durchgeführt, und Abrundung und Löschung waren schwerwiegende Probleme. Heutzutage werden die meisten Berechnungen mit doppelter Genauigkeit und einer Genauigkeit von 16 Stellen durchgeführt, und dies ist heute weitaus weniger ein Problem als früher. Ich denke, es lohnt sich, die von Ihnen zitierten Absätze mit einem Körnchen Salz zu lesen und sie im Kontext ihrer Zeit zu betrachten.