Salta al contenuto
Note per Studenti Esercizio - Ricorrenza p(n+1) = (10/3) p(n) - p(n-1) instabile

Esercizio - Ricorrenza p(n+1) = (10ᐟ3) p(n) - p(n-1) instabile

In questa pagina 3

Teoria: Condizionamento di un problema e stabilità di un algoritmoL'errore finale ha tre origini (dati, troncamento, arrotondamento). Un problema è ben posto se la soluzione esiste, è unica e dipende con continuità dai dati; il numero di condizionamento K = |x f'(x)/f(x)| misura di quanto un errore relativo sui dati si amplifica nel risultato (si perdono circa log10 K cifre). La stabilità riguarda invece l'algoritmo: un algoritmo instabile amplifica gli errori anche su un problema ben condizionato (ricorrenza I_n = 1 − n I_{n−1}); un problema mal condizionato non si salva con nessun algoritmo. Uno schema numerico converge se è consistente e stabile (derivata numerica: troncamento contro arrotondamento).Condizionamento di un problema e stabilità di un algoritmo →.

Testo

La successione pn=(13)np_n = \left(\frac13\right)^n soddisfa la ricorrenza a tre termini pn+1=103 pn−pn−1,p0=1,p1=13.p_{n+1} = \frac{10}{3}\,p_n - p_{n-1}, \qquad p_0 = 1,\quad p_1 = \frac13.

  • (a) Mostrare che la ricorrenza ha come soluzione generale pn=α 3−n+β 3np_n = \alpha\,3^{-n} + \beta\,3^{n} e determinare α\alpha, β\beta per i dati assegnati.
  • (b) Calcolare p2,…,p6p_2, \dots, p_6 in un'aritmetica a 44 cifre significative (con 13→0,3333\frac13 \to 0{,}3333, 103→3,333\frac{10}3 \to 3{,}333) e confrontare con i valori esatti.
  • (c) Spiegare l'andamento dell'errore e dire se il problema "calcolare pnp_n" è mal condizionato o se è l'algoritmo a essere instabile.
  • (d) Proporre un algoritmo stabile.

Soluzione

(a) Soluzione generale

Si cerca pn=rnp_n = r^n: sostituendo, rn+1=103rn−rn−1r^{n+1} = \frac{10}3r^n - r^{n-1}, cioè (dividendo per rn−1r^{n-1}) r2−103r+1=0r^2 - \frac{10}3r + 1 = 0, che ha radici r=103±1009−42=103±832r = \frac{\frac{10}3 \pm \sqrt{\frac{100}9 - 4}}{2} = \frac{\frac{10}3 \pm \frac83}{2}, cioè r=3r = 3 e r=13r = \frac13. Quindi pn=α 3−n+β 3np_n = \alpha\,3^{-n} + \beta\,3^n. Le condizioni iniziali: p0=α+β=1p_0 = \alpha + \beta = 1 e p1=α3+3β=13p_1 = \frac\alpha3 + 3\beta = \frac13. Dalla prima α=1−β\alpha = 1 - \beta; nella seconda 1−β3+3β=13⇒83β=0⇒β=0\frac{1-\beta}3 + 3\beta = \frac13 \Rightarrow \frac{8}{3}\beta = 0 \Rightarrow \beta = 0, α=1\alpha = 1. La soluzione cercata è la sola che non contiene la componente crescente 3n3^n.

(b) Calcolo a 44 cifre

Si arrotonda a 44 cifre significative dopo ogni operazione.

  • p2=3,333⋅0,3333−1p_2 = 3{,}333 \cdot 0{,}3333 - 1: il prodotto è 1,110889→1,1111{,}110889 \to 1{,}111, quindi p2=1,111−1=0,1110p_2 = 1{,}111 - 1 = 0{,}1110.
  • p3=3,333⋅0,1110−0,3333=0,3700−0,3333=0,0367p_3 = 3{,}333 \cdot 0{,}1110 - 0{,}3333 = 0{,}3700 - 0{,}3333 = 0{,}0367.
  • p4=3,333⋅0,0367−0,1110=0,1223−0,1110=0,0113p_4 = 3{,}333 \cdot 0{,}0367 - 0{,}1110 = 0{,}1223 - 0{,}1110 = 0{,}0113.
  • p5=3,333⋅0,0113−0,0367=0,03766−0,0367=0,00096p_5 = 3{,}333 \cdot 0{,}0113 - 0{,}0367 = 0{,}03766 - 0{,}0367 = 0{,}00096.
  • p6=3,333⋅0,00096−0,0113=0,003200−0,0113=−0,0081p_6 = 3{,}333 \cdot 0{,}00096 - 0{,}0113 = 0{,}003200 - 0{,}0113 = -0{,}0081.
nn pnp_n calcolato pnp_n esatto errore assoluto errore relativo
11 0,33330{,}3333 0,3333330{,}333333 3,3⋅10−53{,}3\cdot 10^{-5} 10−410^{-4}
22 0,11100{,}1110 0,1111110{,}111111 1,1⋅10−41{,}1\cdot 10^{-4} 10−310^{-3}
33 0,03670{,}0367 0,0370370{,}037037 3,4⋅10−43{,}4\cdot 10^{-4} 9⋅10−39\cdot 10^{-3}
44 0,01130{,}0113 0,0123460{,}012346 1,05⋅10−31{,}05\cdot 10^{-3} 8,5⋅10−28{,}5\cdot 10^{-2}
55 0,000960{,}00096 0,0041150{,}004115 3,2⋅10−33{,}2\cdot 10^{-3} 0,770{,}77
66 −0,0081-0{,}0081 0,0013720{,}001372 9,5⋅10−39{,}5\cdot 10^{-3} 6,96{,}9

(c) Andamento dell'errore

L'errore assoluto cresce di un fattore circa 33 a ogni passo (3,3⋅10−5→1,1⋅10−4→3,4⋅10−4→1,05⋅10−3…3{,}3\cdot 10^{-5} \to 1{,}1\cdot 10^{-4} \to 3{,}4\cdot 10^{-4} \to 1{,}05\cdot 10^{-3}\ldots), mentre il valore esatto decresce come 3−n3^{-n}: l'errore relativo cresce come 9n9^n e già a n=6n = 6 il risultato ha il segno sbagliato. Il motivo è nella parte (a): l'arrotondamento di 103\frac{10}3 e di p1p_1 introduce una piccola componente β≠0\beta \ne 0, e questa cresce come 3n3^n mentre la soluzione voluta decresce come 3−n3^{-n}. Il problema "calcolare (13)n\left(\frac13\right)^n" è invece ben condizionato (una potenza con errore relativo K=nK = n sul dato 13\frac13). Quindi l'algoritmo è instabile. In doppia precisione, dove l'errore iniziale è ∼10−16\sim 10^{-16}, la ricorrenza dà p20≈3⋅10−8p_{20} \approx 3\cdot 10^{-8} invece di 2,9⋅10−102{,}9\cdot 10^{-10}, e p30≈1,8⋅10−3p_{30} \approx 1{,}8\cdot 10^{-3} invece di 4,9⋅10−154{,}9\cdot 10^{-15}.

(d) Algoritmo stabile

Si usa la ricorrenza a due termini pn+1=13pnp_{n+1} = \frac13p_n (una divisione per 33 a ogni passo): gli errori relativi si sommano solo linearmente, ≈nu\approx n u, non esplodono. Equivale a calcolare 3−n3^{-n} con una potenza.

Risultato. pn=3−np_n = \mathbf{3^{-n}} (α=1\alpha = 1, β=0\beta = 0); la ricorrenza a tre termini in aritmetica finita porta β≠0\beta \ne 0 e dà errore relativo ∼9n\sim 9^n.

Errori tipici

  • Concludere che "il problema è mal condizionato" perché il risultato è sbagliato: bisogna prima chiedersi se un'altra formula dà lo stesso valore in modo accurato.
  • Sperare che aumentare le cifre risolva: sposta solo di qualche passo il momento in cui la componente 3n3^n prende il sopravvento.

Versione ripasso

(a) r2−103r+1=0⇒r=3, 13r^2-\frac{10}3r+1=0\Rightarrow r=3,\ \frac13; pn=α3−n+β3np_n=\alpha3^{-n}+\beta3^n; p0=α+β=1p_0=\alpha+\beta=1, p1=α3+3β=13⇒β=0p_1=\frac\alpha3+3\beta=\frac13\Rightarrow\beta=0, α=1\alpha=1.

(b) 44 cifre, 103→3,333\frac{10}3\to3{,}333:

  • p2=1,111−1=0,1110p_2=1{,}111-1=0{,}1110; p3=0,3700−0,3333=0,0367p_3=0{,}3700-0{,}3333=0{,}0367; p4=0,1223−0,1110=0,0113p_4=0{,}1223-0{,}1110=0{,}0113;
  • p5=0,03766−0,0367=0,00096p_5=0{,}03766-0{,}0367=0{,}00096; p6=0,003200−0,0113=−0,0081p_6=0{,}003200-0{,}0113=-0{,}0081. Esatti: 0,111111, 0,037037, 0,012346, 0,004115, 0,0013720{,}111111,\ 0{,}037037,\ 0{,}012346,\ 0{,}004115,\ 0{,}001372. Errore relativo da 10−310^{-3} (n=2n=2) a 6,96{,}9 (n=6n=6).

(c) L'errore assoluto cresce di ≈3\approx3 a passo (componente β3n\beta3^n), il valore esatto decresce come 3−n3^{-n}: errore relativo ∼9n\sim9^n. Il problema ((13)n\left(\frac13\right)^n, K=nK=n) è ben condizionato, l'algoritmo è instabile. Doppia precisione: p30≈1,8⋅10−3p_{30}\approx1{,}8\cdot10^{-3} invece di 4,9⋅10−154{,}9\cdot10^{-15}.

(d) Stabile: pn+1=13pnp_{n+1}=\frac13p_n (errore ≈nu\approx nu).

Errori tipici: incolpare il problema senza cercare un altro algoritmo; sperare nelle cifre in più (si sposta solo il passo del crollo).

Teoria collegata