Stabilità numerica
La stabilità numerica (anche algoritmica o computazionale), nell'ambito dell'analisi numerica, è una proprietà desiderabile degli algoritmi numerici. Il significato esatto del termine varia ma, in generale, riflette l'accuratezza del risultato.
Non esistono metodi generali per valutare la stabilità di un algoritmo. Solitamente, si ricercano, tramite appositi metodi - come il metodo del simplesso - all'interno del dominio di un algoritmo, quei valori per cui l'algoritmo stesso diventa instabile: ossia la minima variazione dei dati porta a grandi scostamenti nell'errore.
Un esempio classico è il calcolo dell'area del triangolo con la formula di Erone, instabile per angoli molto piccoli.
Un altro esempio classico è il caso dell'overflow/underflow: basta pensare alle due operazioni
dove 10-a è pari o inferiore all'epsilon di macchina, e 10b al massimo numero rappresentabile.
Un errore, una volta che è stato generato, generalmente si propagherà attraverso il calcolo. Questo conduce al concetto di stabilità numerica: un algoritmo si dice numericamente stabile se un errore, una volta che sia stato generato, non cresce troppo durante il calcolo.
Stabilità nell'algebra lineare[modifica | modifica wikitesto]
Esistono vari modi di formalizzare il concetto di stabilità: stabilità in avanti, stabilità all'indietro e stabilità mista sono usualmente usate nell'algebra lineare numerica.
Consideriamo un problema risolto da un algoritmo che consiste in una funzione ƒ che mappa gli input x nelle soluzioni y. Il risultato dell'algoritmo, che chiameremo y*, devia dalla "vera" soluzione y. Le principali cause di queste deviazioni sono gli errori di arrotondamento e gli errori di troncamento. L'errore in avanti dell'algoritmo è la differenza tra il risultato y* e la soluzione y, ovvero Δy = y* − y. L'errore all'indietro è il più piccolo Δx tale che f (x + Δx) = y*; in altre parole, l'errore all'indietro ci indica quale problema ha risolto l'algoritmo. I due errori sono legati al numero di condizionamento: l'errore in avanti è grande al più, in magnitudine, al numero di condizionamento moltiplicato la magnitudine dell'errore all'indietro.
In molti casi si preferisce considerare l'errore relativo |Δx| / |x| piuttosto che l'errore assoluto Δx.
Un algoritmo si dice stabile all'indietro se l'errore all'indietro è piccolo per ogni input x; con piccolo in genere si intende dello stesso ordine di grandezza, o inferiore, rispetto all'errore macchina (errore di arrotondamento).
Un algoritmo si dice stabile in avanti se l'errore in avanti diviso il numero di condizionamento del problema è piccolo. Questo vuol dire che un algoritmo è stabile in avanti se ha un errore in avanti di grandezza comparabile ad alcune algoritmi stabili all'indietro.
La stabilità mista è invece un concetto più generale, che combina l'errore in avanti e l'errore all'indietro. Un algoritmo è stabile in questo senso se risolve un problema vicino in modo approssimato, cioè se esiste un Δx tale che entrambi Δx e f(x + Δx) − y* siano entrambi piccoli. In base a questa definizione, un algoritmo stabile all'indietro è sempre stabile.
