Bester Algorithmus zur Vermeidung von Genauigkeitsverlust?

Question

Eine kürzliche Hausaufgabe, die ich erhalten habe, fordert uns auf, Ausdrücke zu nehmen, die im Computer einen Präzisionsverlust verursachen könnten, und sie so zu verändern, dass dieser Verlust vermieden wird.

Leider wurden die Anweisungen dafür nicht sehr klar gemacht. Aus der Beobachtung verschiedener Beispiele weiß ich, dass es bestimmte Methoden gibt, um dies zu tun: Taylor-Reihen zu verwenden, Konjugate zu verwenden, wenn Quadratwurzeln beteiligt sind, oder einen gemeinsamen Nenner zu finden, wenn zwei Brüche subtrahiert werden.

Allerdings habe ich einige Schwierigkeiten, genau zu bemerken, wann ein Genauigkeitsverlust auftreten wird. Bis jetzt ist das einzige, was ich sicher weiß, dass, wenn Sie zwei Zahlen subtrahieren, die nahe daran sind, die gleichen zu sein, ein Verlust der Genauigkeit auftritt, da Ziffern hoher Ordnung signifikant sind, und Sie diese von der Rundung verlieren.

Meine Frage ist, was sind einige andere häufige Situationen, die ich suchen sollte, und was gelten als "gute" Methoden, sie zu nähern?

Zum Beispiel, hier ist ein Problem:

f(x) = tan(x) − sin(x) when x ~ 0 

Was ist der beste und schlechteste Algorithmus dies aus diesen drei Möglichkeiten zur Bewertung:

(a) (1/ cos(x) − 1) sin(x), 
(b) (x^3)/2 
(c) tan(x)*(sin(x)^2)/(cos(x) + 1). 

Ich verstehe, dass, wenn x in der Nähe von null, tan (x) und sin (x) sind nahezu gleich. Ich verstehe nicht, wie oder warum diese Algorithmen besser oder schlechter sind, um das Problem zu lösen.

Answer 1

Eine andere Faustregel, die normalerweise verwendet wird, ist folgende: Wenn Sie eine lange Reihe von Zahlen hinzufügen, beginnen Sie mit der Addition von Zahlen, die am nächsten bei Null liegen und enden mit den größten Zahlen.

Erklären warum das gut ist, ist etwas schwierig. Wenn Sie einer großen Zahl kleine Zahlen hinzufügen, besteht die Möglichkeit, dass sie vollständig verworfen werden, da sie kleiner sind als die niedrigste Ziffer in der aktuellen Mantisse einer großen Zahl. nehmen zum Beispiel diese Situation: nichts

a = 1,000,000; 
do 100,000,000 time: 
    a += 0.01; 

wenn 0,01 kleiner als die niedrigste Mantisse Ziffer, dann tut die Schleife und das Endergebnis ist ein == 1.000.000 aber wenn Sie dies tun, wie folgt aus:

a = 0; 
do 100,000,000 time: 
    a += 0.01; 
a += 1,000,000; 

Als die niedrige Zahl langsam wächst und Sie eher mit etwas in der Nähe von a == 2.000.000 enden, die die richtige Antwort ist.
Dies ist natürlich ein extremes Beispiel, aber ich hoffe, Sie bekommen die Idee.

Answer 2

Ich musste eine Numerik-Klasse zurück, als ich noch ein Student war, und es war sehr schmerzhaft. Wie auch immer, IEEE 754 ist der Fließkomma-Standard, der typischerweise von modernen CPUs implementiert wird. Es ist nützlich, die Grundlagen zu verstehen, denn das gibt Ihnen eine Menge Intuition darüber, was nicht zu tun ist. Die vereinfachte Erklärung dafür ist, dass Computer Gleitkommazahlen in einer wissenschaftlichen Notation der Basis 2 mit einer festen Anzahl von Stellen (Bits) für den Exponenten und für die Mantisse speichern. Dies bedeutet, dass je größer der absolute Wert einer Zahl ist, desto weniger genau kann sie dargestellt werden. Für 32-Bit-Gleitkommazahlen in IEEE 754 repräsentiert die Hälfte der möglichen Bitmuster zwischen -1 und 1, obwohl Zahlen bis zu 10^38 mit einem 32-Bit-Gleitkomma darstellbar sind. Für Werte größer als 2^24 (ca. 16,7 Millionen) kann ein 32-Bit-Float nicht alle Ganzzahlen genau darstellen.

Was bedeutet dies für Sie ist, dass Sie in der Regel vermeiden wollen folgendes: ist

1. Mit Zwischenwerte werden groß, wenn die endgültige Antwort erwartet, klein zu sein.

2. Hinzufügen/Subtrahieren von kleinen Zahlen zu/von großen Zahlen. Zum Beispiel, wenn Sie so etwas wie schreiben:

   für (float index = 17000000; Index < 17.000.001; Index ++) {}

Diese Schleife würde nie enden becuase 17.000.000 + 1 bis 17 Millionen abgerundet. Wenn Sie so etwas wie gehabt:

float foo = 10000000 - 10000000.0001 

Der Wert für foo 0 sein würde, nicht -0,0001, wegen Rundungsfehler.

Answer 3

Eine weitere Sache, die zu vermeiden ist, ist das Subtrahieren von Zahlen, die nahezu gleich sind, da dies auch zu einer erhöhten Empfindlichkeit gegenüber einem Rundungsfehler führen kann. Für Werte in der Nähe von 0 ist cos (x) nahe bei 1, also ist 1/cos (x) - 1 eine der Subtraktionen, die Sie möglichst vermeiden möchten. Daher würde ich sagen, dass (a) vermieden werden sollte .

Answer 4

Meine Frage ist, was sind einige andere gemeinsame Situationen, die ich suchen sollte, und was sind als ‚gut‘ Methoden von ihnen nähern?

Es gibt mehrere Möglichkeiten, wie Sie schwere oder gar katastrophale Präzisionsverluste erleiden können.

Der wichtigste Grund ist, dass Fließkommazahlen eine begrenzte Anzahl von Ziffern haben, z. B. doubles 53 Bits haben. Das heißt, wenn Sie "nutzlose" Ziffern haben, die nicht Teil der Lösung sind, sondern gespeichert werden müssen, verlieren Sie die Präzision.

Zum Beispiel (Wir verwenden Dezimaltypen zur Demonstration):

2,598765000000000000000000000100 -

2,598765000000000000000000000099

Der interessante Teil der Antwort 100-99 = 1 ist. Da 2.598765 in beiden Fällen gleich ist, ändert es das Ergebnis nicht, sondern verschwendet 8 Ziffern. Viel schlimmer, weil der Computer nicht weiß, dass die Ziffern nutzlos sind, ist es gezwungen, es zu speichern und 21 Nullen danach zu stopfen, verschwenden alle 29 Ziffern. Leider gibt es keine Möglichkeit, sie für Unterschiede zu umgehen, aber es gibt andere Fälle, z. exp (x) -1 ist eine Funktion, die in der Physik sehr häufig vorkommt.

Die Exp-Funktion in der Nähe von 0 ist fast linear, aber sie erzwingt eine 1 als führende Ziffer. So mit 12 signifikanten Stellen exp (0,001) -1 = 1,00100050017-1 = 1.00050017e-3

Wenn wir stattdessen eine Funktion expm1() verwenden, verwenden Sie die Taylor-Reihe:

1 + x + x^2/2 + x^3/6 ...-1 =

x + x^2/2 + x^3/6 =: expm1 (x)

expm1 (0,001) = 1.00500166667e-3

viel besser.

Das zweite Problem sind Funktionen mit einer sehr steilen Steigung wie Tangens von x in der Nähe von Pi/2. tan (11) hat eine Steigung von 50000 was bedeutet, dass jede kleine Abweichung, die durch Rundungsfehler vorher verursacht wird, um den Faktor 50000 verstärkt wird! Oder Sie haben Singularitäten, wenn z. das Ergebnis nähert sich 0/0, dh es kann einen beliebigen Wert haben.

In beiden Fällen erstellen Sie eine Ersatzfunktion, die die ursprüngliche Funktion vereinfacht. Es macht keinen Sinn, die verschiedenen Lösungsansätze hervorzuheben, denn ohne Training werden Sie das Problem gar nicht "sehen".

Ein sehr gutes Buch zu lernen und zu trainieren: Forman S. Acton: Echtes Rechnen gemacht