Vai al contenuto
Calcolo Numerico

Aritmetica in virgola mobile, errori, condizionamento e stabilità

Lo standard IEEE 754 e la precisione di macchina, cancellazione numerica con esempi, numero di condizionamento, algoritmi stabili e instabili.

4 min di lettura 0 commenti

Il calcolo numerico studia come risolvere al computer i problemi della matematica (equazioni, sistemi, integrali, equazioni differenziali) quando una formula esatta non c’è o è inutilizzabile. Il primo passo è capire con che cosa calcola un computer: non con i numeri reali, ma con un insieme finito di numeri in virgola mobile. Da qui nascono gli errori di arrotondamento, e la differenza tra un problema ben condizionato e un algoritmo stabile.

I numeri in virgola mobile

Un computer rappresenta un numero reale come

    \[ x = \pm\,(1.m_1m_2\dots m_p)_2\times 2^e \]

con un segno, una mantissa di p cifre binarie e un esponente e in un intervallo limitato. Lo standard IEEE 754, usato da tutti i processori moderni, prevede:

FormatoBit totaliMantissaEsponenteCifre decimaliPrecisione di macchina \varepsilon
singola (float)3223 + 18circa 71{,}2\times 10^{-7}
doppia (double)6452 + 111circa 162{,}2\times 10^{-16}

Il bit iniziale della mantissa è sempre 1 e non si memorizza (“bit nascosto”), da cui il “+ 1”.

Distribuzione dei numeri in virgola mobile sulla retta, fitti vicino a zero e radi lontano
I numeri rappresentabili (trattini blu) non sono equidistanti: in ogni intervallo tra due potenze di 2 ce ne sono lo stesso numero, quindi la distanza tra numeri vicini raddoppia a ogni potenza di 2. L’errore relativo resta costante, quello assoluto cresce con il numero.

La precisione di macchina \varepsilon è la distanza tra 1 e il numero rappresentabile successivo. Ogni numero reale x nell’intervallo rappresentabile viene arrotondato al più vicino, con un errore relativo al massimo \varepsilon/2:

    \[ \mathrm{fl}(x) = x(1 + \delta),\qquad |\delta| \le \frac\varepsilon2 \]

E ogni operazione aritmetica ha lo stesso errore: \mathrm{fl}(a + b) = (a + b)(1 + \delta).

Sorprese tipiche.

  • 0{,}1 non è rappresentabile esattamente in binario (come 1/3 in decimale), quindi 0{,}1 + 0{,}2 in doppia precisione dà 0{,}30000000000000004. Mai confrontare numeri in virgola mobile con l’uguaglianza esatta: si usa |a - b| \lt \text{tolleranza}.
  • In singola precisione 16\,777\,216 + 1 = 16\,777\,216: oltre 2^{24} gli interi non sono più tutti rappresentabili.
  • Esistono valori speciali: \pm\infty (per esempio 1/0) e NaN, “non un numero” (per esempio 0/0), che si propagano nei calcoli invece di fermare il programma.

La cancellazione numerica

La sottrazione di due numeri quasi uguali è l’operazione più pericolosa. Se a e b hanno 16 cifre corrette e coincidono nelle prime 12, la differenza ne ha solo 4: le altre sono rumore di arrotondamento.

Esempio: l’equazione di secondo grado. x^2 - 10^8x + 1 = 0 ha radici circa 10^8 e 10^{-8}. La formula classica per la radice piccola, \frac{b - \sqrt{b^2 - 4c}}{2}, sottrae due numeri quasi uguali e in doppia precisione dà circa 7{,}45\times 10^{-9}: errore del 25%. La soluzione è riscrivere la formula: si calcola prima la radice grande, senza cancellazione, e poi la piccola con x_1x_2 = c, cioè x_2 = c/x_1 = 10^{-8}, esatta.

Esempio: 1 - \cos x per x piccolo. Con x = 10^{-8}, \cos x arrotondato vale esattamente 1 e il risultato è 0, mentre il valore vero è 5\times 10^{-17}. Riscrivendo 1 - \cos x = 2\sin^2(x/2) il calcolo è accurato. Le librerie forniscono funzioni apposite, come expm1 e log1p, proprio per questi casi.

Condizionamento di un problema

Il condizionamento misura quanto il risultato esatto di un problema cambia se si perturbano un po’ i dati. Per una funzione f, il numero di condizionamento relativo è

    \[ K = \left|\frac{x\,f'(x)}{f(x)}\right| \]

l’errore relativo sul risultato è circa K volte quello sui dati. Se K è grande il problema è mal condizionato: anche un calcolo perfetto con dati arrotondati dà risultati inaffidabili. È una proprietà del problema, non dell’algoritmo.

Per i sistemi lineari A\mathbf x = \mathbf b il numero di condizionamento è K(A) = \|A\|\,\|A^{-1}\|. Se K(A) \approx 10^k, si perdono circa k cifre significative: con K = 10^{12} in doppia precisione restano solo 4 cifre affidabili. La matrice di Hilbert h_{ij} = 1/(i + j - 1) di ordine 10 ha K \approx 1{,}6\times 10^{13}: è l’esempio classico di sistema quasi irrisolvibile al computer pur essendo invertibile.

Stabilità di un algoritmo

Un algoritmo è stabile se non amplifica gli errori di arrotondamento più di quanto faccia già il problema. Lo stesso problema ben condizionato si può risolvere con un algoritmo stabile o instabile, come nell’esempio dell’equazione di secondo grado.

Esempio di algoritmo instabile. Gli integrali I_n = \int_0^1 x^ne^{x - 1}dx soddisfano I_n = 1 - nI_{n-1}, con I_0 = 1 - 1/e. Usando la ricorrenza in avanti, l’errore iniziale (dell’ordine di 10^{-16}) viene moltiplicato per n!: con n = 20, 20! \approx 2{,}4\times 10^{18}, e il risultato è completamente sbagliato, anche negativo, mentre I_n è sempre tra 0 e 1. Usando la ricorrenza all’indietro, I_{n-1} = (1 - I_n)/n, partendo da un valore qualsiasi per n grande, l’errore viene diviso per n a ogni passo e il risultato è accurato.

Una regola pratica

Errore finale \approx condizionamento \times precisione di macchina, se l’algoritmo è stabile. Nelle lezioni successive, per ogni metodo, ci chiederemo tre cose: se converge, quanto velocemente, e se è stabile. Il famoso esempio storico del razzo Ariane 5, esploso nel 1996 per la conversione di un numero in virgola mobile a 64 bit in un intero a 16 bit che non poteva contenerlo, ricorda che questi dettagli non sono accademici.

Articoli correlati

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x