¶
Esempio 3 Sia |x| grande.
1 x − 1
x + 1 = 1 x(x + 1)
2.5 Stabilit` a e condizionamento
In questa sezione cercheremo di definire ed illustrare due nozioni fonda-mentali del calcolo numerico: il condizionamento di un modello mate-matico (o numerico) e la stabilit`a numerica di un algoritmo. Sono due concetti che non vanno confusi tra loro.
Supponiamo di avere un certo problema (modello) matematico (o nu-merico) e che una piccola variazione dei dati numerici di ingresso (detta perturbazione) di tale modello, porti ad una soluzione molto lontana da quella del problema non perturbato.
Diamo un esempio molto semplice:
Sia dato il seguente sistema lineare a due incognite
½ 2.1x + 3.5y = 8.0 4.19x + 7.0y = 15.0
2.5. Stabilit`a e condizionamento 37 che ammette per soluzioni
x = 100.0
y = −57.71428571 . . .
Aggiungiamo una piccola perturbazione al coefficiente della x nella secon-da equazione, ovvero al posto di 4.19 scriviamo 4.192. L’errore relativo dovuto a tale perturbazione `e all’incirca 4.77 × 10−4.
Se risolviamo ora il sistema perturbato otteniamo come soluzioni x = 125.0
y = −72.71428571 . . .
con un errore relativo su x di 0.25 e su y di circa 0.26, quindi elevati.
Come si `e visto tale problematica non dipende dall’algoritmo utilizzato ma dal problema in se stesso (trattandosi geometricamente di due rette quasi parallele, `e naturale che una piccola variazione di inclinazione di una delle due rette, provochi uno spostamento notevole del punto di intersezione). Tenendo presente che, utilizzando un computer, abbiamo visto che anche solo a causa dell’errore di assegnazione non si lavora con i dati esatti, ma con una loro approssimazione, la risoluzione del sistema ci porter`a ad avere soluzioni anche molto diverse dalla soluzione esatta (e questo a prescindere dell’algoritmo utilizzato).
Possiamo quindi dare la seguente definizione
Condizionamento: Un problema si dice ben condizionato se a piccole perturbazioni (errori relativi) sui dati di ingresso, corrispondono pertur-bazioni (errori relativi) sui risultati piccole (ovvero dello stesso ordine di grandezza).
Un problema mal condizionato invece amplifica fortemente gli errori re-lativi dai dati ai risultati (non necessariamente tutti i risultati).
Numero di condizionamento: Sia P un problema i cui dati siano d ed il risultato r. Supponiamo che una variazione ∆d dei dati provochi una variazione ∆r del risultato. `E possibile definire il numero di condiziona-mento di un problema P (indicato con cond(P)) come una limitazione superiore del fattore di amplificazione degli errori relativi, ovvero
k∆rk
krk ≤ cond(P)k∆dk kdk ,
dove con k · k indichiamo una funzione (norma) che misura le entit`a coinvolte (si veda l’appendice, sezione A.7).
Un altro esempio di problema mal condizionato `e dato dalla ricerca delle radici di un polinomio quando vi sono radici α grandi e la derivata del polinomio calcolata in tali α `e piccola, oppure quando vi sono due radici molto vicine oppure multiple.
Un esempio classico di tale problema `e dato dal Polinomio di Wilkinson P20 = (x + 1)(x + 2) · · · (x + 20) = x20+ 210x19+ · · · + 20! . Pur avendo radici ben separate (αi = −i, i = 1, . . . , 20), si riescono a calcolare bene le prime 15, ma non le ultime 5.
Vediamo ora di definire il secondo concetto. Per risolvere un certo problema noi usiamo un certo algoritmo ed il programma corrispondente sul computer. Vi saranno quindi necessariamente degli errori dovuti all’aritmetica del computer che potranno propagarsi in modo pi`u o meno rilevante sui risultati. Quindi un problema pu`o essere per natura ben condizionato, ma l’algoritmo utilizzato per risolverlo pu`o essere numeri-camente instabile. In tal caso, `e necessario usare (o trovare) un algoritmo stabile.
Un esempio di algoritmo instabile e di un algoritmo alternativo stabile (in quanto evita gli eventuali problemi di cancellazione) lo abbiamo visto nella sezione 2.4.3.
Diamo una definizione di stabilit`a numerica di un algoritmo:
Stabilit`a: Un algoritmo si dice stabile se a piccole perturbazioni (errori relativi) sui dati, corrispondono perturbazioni (errori relativi) sui risultati dello stesso ordine di grandezza.
Un algoritmo si dice instabile se gli errori piccoli iniziali (o presenti ad un certo momento) anzich`e compensarsi mediamente (o mantenersi limitati) tendono a crescere in modo incontrollato sino a degradare completamente il risultato finale.
Vediamo un esempio classico di due algoritmi, che risolvono lo stesso problema, l’uno stabile e l’altro instabile.
Sia da calcolare l’integrale
In = 1 e
Z 1 0
xnex dx con n ≥ 0
2.5. Stabilit`a e condizionamento 39 Integrando per parti si ha
In= 1
e ed il seguente schema
ricorsivo (
i→∞lim Ii= 0 ed i valori devono essere decrescenti in valore assoluto.
Dimostriamo ora che tale algoritmo per il calcolo dell’integrale In `e instabile.
Indichiamo con Ii il valore esatto e con I0i il valore approssimato al passo i-esimo.
Si ha I0i = Ii+ εi, con |εi| uguale all’errore assoluto al passo i. Analoga-mente I0i−1 = Ii−1+ εi−1 e quindi, dalla formula ricorsiva I0i = 1 − i I0i−1, si ha Ii+ εi = 1 − i (Ii−1+ εi−1) ovvero
εi = −i εi−1
che `e la relazione che lega l’errore al passo i-esimo, rispetto all’errore al passo (i − 1)-esimo.
Calcoliamo ora quanto vale εn rispetto a ε1. Si ha
εn= −n (−(n − 1) εn−2) = · · ·=−n (−(n − 1)) · · · (−2)ε1= (−1)n−1n! ε1. Quindi, anche supposto che ε1 sia molto piccolo, e non tenendo conto degli errori di aritmetica, εnaumenta rapidamente (a causa del fattoriale) e si ha lim
n→∞|εn| = ∞.
Vediamo, a conferma di tale analisi, alcuni risultati ottenuti utiliz-zando la semplice precisione (al fine rendere pi`u visibile l’instabilit`a, che comunque si presenta anche in doppia precisione). Si ha I1 = e−1 e I01 = 3.6787945 × 10−1. Utilizzando lo schema ricorsivo in avanti, otte-niamo i risultati della seguente tabella. Essi mostrano come il valore I0n tenda ad aumentare rapidamente, anzich`e convergere verso lo zero, otte-nendo per I021 un numero dell’ordine di 1011. In doppia precisione si ha I021= −2.201076724843952 × 103.
n I0n n I0n 2 2.6424110 × 10−1 12 −4.3109741 × 100 3 2.0727670 × 10−1 13 5.7042664 × 101 4 1.7089319 × 10−1 14 −7.9759729 × 102 5 1.4553404 × 10−1 15 1.1964959 × 104 6 1.2679577 × 10−1 16 −1.9143834 × 105 7 1.1242962 × 10−1 17 3.2544528 × 106 8 1.0056305 × 10−1 18 −5.8580148 × 107 9 9.4932556 × 10−2 19 1.1130228 × 109 10 5.0674438 × 10−2 20 −2.2260457 × 1010 11 4.4258118 × 10−1 21 4.6746960 × 1011
Diamo ora l’algoritmo stabile (noto come algoritmo di Miller) che co-struisce la famiglia di integrali in senso regressivo, ovvero facendo de-crescere gli indici.
Si fissa un indice N ∈ N (anche non troppo grande) con N > n, si pone IN uguale ad un valore arbitrario qualsiasi, oppure a zero (commettendo certamente un errore εN) e si considera il seguente algoritmo ricorsivo
( IN = a Ii−1 = 1
i (1 − Ii) , i = N, N − 1, . . . , 2 con a ∈ R arbitrario.
Si ha I00i = Ii+ εi, e I00i−1 = Ii−1+ εi−1. Quindi, dalla formula ricorsiva, Ii−1+ εi−1 = 1
i (1 − Ii− εi) ovvero εi−1= −1
iεi
che `e la relazione che lega l’errore per l’indice (i − 1), rispetto all’errore per l’indice i.
Supponendo di aver commesso (assegnando il valore di partenza IN = a) un errore εN = I00N − IN, avremo
εN −1 = −1 N εN
εN −2 = − 1
N − 1εN −1= (−1)2 N (N − 1)εN
... ...
ε1 = (−1)N −1 N ! εN