1. Rappresentazione
dei
numeri
al calcolatore
I calcolatori oggi in commercio rispettano in genere il medesimo
standard per la rappresentazione dei numeri in virgola mobile ( floating-point ): lo standard
IEEE 754 .
Nello standard IEEE la precisione singola occupa una
parola da 32 bit, mentre la precisione doppia occupa due
parole consecutive da 32 bit. Un numero non-nullo normalizzato "X" ha la seguente
rappresentazione binaria:
X = (-1)^S
* 2^(E-bias) * (1.F)
dove bias = 127 (single) o 1023 (double)
Lo standard richiede che il risultato delle operazioni di addizione,
sottrazione, moltiplicazione e divisione sia arrotondato
esattamente, cioè il risultato deve essere calcolato esattamente e
poi arrotondato al numero in virgola mobile più vicino.
Problemi in tal senso provengono dalla sottrazione (...). Per questo
motivo, nei microprocessori moderni la sottrazione viene effettuata
utilizzando la tecnica bit di guardia :
l'operando più piccolo viene troncato a p+1 cifre binarie,
mentre il risultato della sottrazione viene troncato a p cifre
(binarie). In realtà, il calcolo con un solo bit di guardia non
sempre produce lo stesso risultato che si avrebbe calcolando il
risultato esatto e poi arrotondando a p cifre binarie. Introducendo
un secondo bit di guardia ed un terzo bit sticky , si ottiene il pieno rispetto dello
standard con un extra-costo computazionale relativamente piccolo.
E' possibile esercitarsi con la rappresentazione dei numeri in
virgola mobile utilizzando la seguente calcolatrice_IEEE_754
.
2. Propagazione
degli
errori
di arrotondamento
Ogni calcolatore ha a disposizione un numero finito M di cifre per
rappresentare un numero reale. Se il numero da rappresentare
possiede più di M cifre significative, il calcolatore lo arrotonda
alle M cifre più significative. A causa di questo fatto, le
operazioni aritmetiche di base sono in generale soggette ad un
errore nel risultato, ed è dunque necessario conoscere l’entità di
questo errore e, considerando un intero algoritmo, l’effetto
potenziale della propagazione di questo tipo di errore sul risultato
finale.
In generale, la somma, la divisione e la moltiplicazione producono
un errore relativo piccolo, mentre la sottrazione può anche produrre
un errore relativo grande, rispetto al risultato (ciò avviene quando
i due operandi sono molto vicini tra di loro e si ha dunque una
notevole perdita di cifre significative nel risultato).
Il fatto che l’errore relativo nel risultato sia piccolo non è
comunque una garanzia di accuratezza in generale: la somma tra
due operandi troppo distanti in magnitudo può addirittura far
scomparire dal risultato il più piccolo dei due ed avere comunque un
errore relativo piccolo. Per questo motivo, ad esempio, quando
si deve eseguire una sommatoria, è buona regola eseguirla mettendo
gli operandi in ordine crescente, in modo che la somma parziale ed
il prossimo numero da sommare siano il più vicini possibile in
magnitudo.
Vediamo di seguito alcuni esempi relativi a questi fenomeni:
1. calcolo
delle radici di un’equazione di secondo grado :
vediamo ora un esempio concreto di calcolo in cui introdurre una
sottrazione potenzialmente pericolosa conduca effettivamente a
problemi di instabilità della soluzione, e come rimediare.
Data: a*x^2 + b*x +c , calcolare le sue radici.
La formula classica, x = (- b ± sqrt(b^2 – 4*a*c))/(2*a) , è
potenzialmente instabile a causa della sottrazione tra b/2 e
sqrt(...) . Provare ad implementarla e verificarne la perdita di
accuratezza per opportune scelte dei coefficienti a, b, e c.
Ripetere poi lo stesso tipo di indagine su una formula alternativa,
stabile, che si ottiene calcolando prima la radice positiva ( in cui
non si effettua la sottrazione) e poi calcolando l’altra sapendo che
vale : c = a * x_1 * x_2 . eq_2grado.py
( facoltativo: per chi fosse interessato, eq_2grado.m )
2.
approssimazione di pigreco :
è un altro esempio di sottrazione pericolosa, questa volta in un
metodo numerico iterativo per l’approssimazione di pi-greco. Provare
ad implementare i seguenti tre metodi iterativi ed a graficarne
l’errore relativo, in scala logaritmica, per le prime 100 iterate
(un valore molto accurato di pi-greco in Matlab/Octave è contenuto
nella variabile di sistema “pi”). Per n=2,3,4,.... calcolare le tre
approssimazioni di pi-greco, y(n), w(n) e z(n) :
1) s(2)=1+1/4;
s(n+1)=s(n)+1/((n+1)^2); y(n+1)=
sqrt(6*s(n+1));
2)
w(2)=2;
w(n+1)=2^(n-1/2)*sqrt(1-sqrt(1-4^(1-n)*w(n)^2));
3) z(2)=2;
z(n+1)=(sqrt(2)*z(n))/(sqrt(1+sqrt(1-4^(1-n)*z(n)^2)));
Commentare i risultati ottenuti. succ_pigreco.py
( facoltativo: per chi fosse interessato, succ_pigreco.m )
3.
successioni calcolabili praticamente :
Si consideri la seguente successione:
y(0)=1/e*(e-1);
y(n+1)=1-(n+1)*y(n);
essa converge (in aritmetica con infinite cifre) a zero per
n->inf. Implementarla e verificare cosa accade nel calcolatore,
cercando di giustificare i risultati.
Inoltre, sapendo che y(n) è circa =0 per n sufficientemente grande,
provare ad implementarla all'indietro e vedere cosa risulta per
y(0). Perchè?
succ_avanti_indietro.py
( facoltativo: per chi fosse interessato, succ_avanti_indietro.m )