Algoritmi stabili e instabili
Gli algoritmi possano produrre risultati stabili o instabili a causa della crescita dell'errore nei calcoli. Se l'errore cresce in modo lineare, l'algoritmo è considerato stabile, ma se cresce in modo esponenziale, l'algoritmo è instabile.
La stabilità degli algoritmi numerici riguarda come un algoritmo reagisce quando ci sono errori nei dati di partenza.
In particolare, bisogna vedere se gli errori introdotti durante i calcoli crescono man mano che si fanno più operazioni, influenzando il risultato finale.
- Crescita lineare degli errori
L'algoritmo è stabile se l'errore cresce in modo lineare. Ad esempio, se raddoppia dopo un certo numero di operazioni. La crescita lineare dell'errore è accettabile in molti casi, specialmente se gli errori iniziali sono piccoli. $$ E_n \approx c \cdot n \cdot E_0 $$ Dove $ E_n $ è l'errore dopo $ n $ operazioni, $ c $ è una costante indipendente, $ E_0 $ è l'errore iniziale. - Crescita esponenziale degli errori
L'algoritmo è instabile se l'errore cresce in modo esponenziale. Ad esempio, raddoppia ogni volta che vengono fatte più operazioni. Il che è molto pericoloso perché l'errore può diventare enorme molto rapidamente.Anche se l'errore iniziale è piccolo, l'errore finale può diventare molto grande e compromettere il risultato finale. $$ E_n \approx c^n \cdot n \cdot E_0 $$ Dove $ E_n $ è l'errore dopo $ n $ operazioni, $ c > 1 $ è una costante indipendente maggiore di 1, $ E_0 $ è l'errore iniziale.
In altre parole un algoritmo è considerato stabile se, quando ci sono piccoli errori nei dati iniziali, l'errore nei risultati finali rimane piccolo.
Vicevera, un algoritmo è instabile se un piccolo errore nei dati iniziali provoca un errore molto grande nel risultato finale.
Alcuni algoritmi sono condizionatamente stabili, cioè sono stabili solo se i dati iniziali soddisfano certe condizioni.
E così via.
