Miglior algoritmo per evitare perdita di precisione?

Question

Un recente compito a casa che ho ricevuto ci chiede di prendere espressioni che potrebbero creare una perdita di precisione quando eseguite sul computer e modificarle in modo da evitare questa perdita.

Sfortunatamente, le istruzioni per farlo non sono state rese molto chiare. Dall'osservare vari esempi che vengono eseguiti, so che ci sono alcuni metodi per farlo: usare la serie di Taylor, usare i coniugati se le radici quadrate sono coinvolte, o trovare un denominatore comune quando si sottraggono due frazioni.

Tuttavia, ho qualche problema a notare esattamente quando si verificherà una perdita di precisione. Finora l'unica cosa che so per certo è che quando si sottraggono due numeri che sono vicini ad essere uguali, si verifica una perdita di precisione poiché le cifre di ordine elevato sono significative e si perdono quelle da arrotondare.

La mia domanda è quali sono alcune altre situazioni comuni che dovrei cercare e quali sono considerati metodi "buoni" per avvicinarli?

Per esempio, qui è un problema:

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

Qual è l'algoritmo meglio e il peggio per valutare questo fuori di queste tre scelte:

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

Capisco che quando x è vicino a zero, tan (x) e sin (x) sono quasi la stessa cosa. Non capisco come o perché uno di questi algoritmi sia migliore o peggiore per risolvere il problema.

Answer 1

Un'altra regola empirica solitamente utilizzata è questa: quando si aggiunge una lunga serie di numeri, iniziare ad aggiungere dai numeri più vicini allo zero e terminare con i numeri più grandi.

Spiegare perché questo è buono è un po 'complicato. quando aggiungi numeri piccoli a numeri grandi, c'è la possibilità che vengano completamente scartati perché sono più piccoli della cifra più bassa nella mantissa corrente di un numero elevato. Prendete per esempio questa situazione:

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

se 0.01 è inferiore al più basso cifre mantissa, quindi il ciclo non fa nulla e il risultato finale è un == 1.000.000 ma se fate questo in questo modo:

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

Rispetto al numero basso, cresce lentamente ed è più probabile che si arrivi a qualcosa di simile a == 2.000.000, che è la risposta giusta.
Questo è naturalmente un esempio estremo ma spero che tu abbia ottenuto l'idea.

Answer 2

Ho dovuto prendere una lezione di matematica quando ero uno studente ed è stato molto doloroso. In ogni caso, lo standard IEEE 754 è lo standard in virgola mobile implementato dalle moderne CPU. È utile comprenderne le basi, poiché questo ti dà molta intuizione su cosa non fare. La spiegazione semplificata di ciò è che i computer memorizzano numeri in virgola mobile in qualcosa come la notazione scientifica di base-2 con un numero fisso di cifre (bit) per l'esponente e per la mantissa. Ciò significa che maggiore è il valore assoluto di un numero, meno preciso può essere rappresentato. Per i float a 32 bit in IEEE 754, la metà dei possibili pattern di bit rappresenta tra -1 e 1, anche se i numeri fino a circa 10^38 sono rappresentabili con un float a 32 bit. Per valori superiori a 2^24 (circa 16,7 milioni) un float a 32 bit non può rappresentare esattamente tutti gli interi.

cosa questo significa per voi è che in genere vuole evitare il seguente:

1. con valori intermedi essere grandi quando la risposta finale è previsto per essere piccolo.

2. Aggiunta/sottrazione di numeri piccoli a/da numeri grandi. Ad esempio, se hai scritto qualcosa di simile:

   per (indice float = 17000000; indice < 17.000.001; indice ++) {}

Questo ciclo non sarebbe mai interrompere becuase 17.000.000 + 1 viene arrotondato a 17.000.000. Se tu avessi qualcosa di simile:

float foo = 10000000 - 10000000.0001 

Il valore per foo sarebbe 0, non -0,0001, a causa di errore di arrotondamento.

Answer 3

Un'altra cosa da evitare è sottrarre numeri che sono quasi uguali, in quanto ciò può anche portare ad una maggiore sensibilità all'errore di arrotondamento. Per valori vicino a 0, cos (x) sarà vicino a 1, quindi 1/cos (x) - 1 è una di quelle sottrazioni che vorresti evitare se possibile, quindi direi che (a) dovrebbe essere evitato .

Answer 4

La mia domanda è che cosa sono alcuni altri situazioni comuni che dovrebbero essere alla ricerca , e quali sono considerati 'buoni' metodi di loro si avvicina?

Ci sono diversi modi in cui è possibile avere una perdita di precisione grave o addirittura catastrofica.

Il motivo più importante è che i numeri in virgola mobile hanno un numero limitato di cifre, ad esempio i numeri hanno 53 bit. Ciò significa che se hai cifre "inutili" che non fanno parte della soluzione ma devono essere memorizzate, perdi precisione.

Per esempio (Stiamo utilizzando tipi decimali per la dimostrazione):

2,598765000000000000000000000100 -

2,598765000000000000000000000099

La parte interessante è la risposta 100-99 = 1. Dato che 2.598.765 è uguale in entrambi i casi, lo non modifica il risultato, ma spreca 8 cifre. Molto peggio, perché il computer non riconosce che le cifre sono inutili, è costretto a memorizzarle e ne contamina 21 zero dopo lo sprecando tutte e 29 le cifre. Sfortunatamente non c'è modo di aggirarlo per differenze, ma ci sono altri casi, ad es. exp (x) -1 che è una funzione che si verifica molto spesso in fisica.

La funzione di exp vicino a 0 è quasi lineare, ma impone un 1 come cifra iniziale. Quindi, con 12 cifre significative exp (0.001) -1 = 1,00100050 mila diciassette - 1 = 1.00050017e-3

Se si usa invece una funzione expm1(), utilizzare la serie di Taylor:

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

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

expm1 (0,001) = 1.00500166667e-3

Molto meglio.

Il secondo problema sono le funzioni con una pendenza molto ripida come la tangente di x vicino pi/2. tan (11) ha una pendenza di 50000 che significa che qualsiasi piccola deviazione causata dagli errori di arrotondamento prima verrà amplificata dal fattore 50000! O hai singolarità se ad es. il risultato si avvicina a 0/0, ciò significa che può avere qualsiasi valore.

In entrambi i casi si crea una funzione sostitutiva, semplicemente la funzione originale. È inutile evidenziare i diversi approcci alla soluzione, perché senza un addestramento semplicemente non "vedrai" il problema in primo luogo.

Un ottimo libro per imparare e allenare: Forman S. Acton: Real Computing reso reale