Salta al contenuto
Note per Studenti Esercizio - Problema ben condizionato e algoritmo instabile, ex - 1 per x piccolo

Esercizio - Problema ben condizionato e algoritmo instabile, e^x - 1 per x piccolo

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 →; cancellazione in Aritmetica di macchina - floating point, precisione di macchina e cancellazioneUn calcolatore rappresenta solo un insieme finito di numeri F(β,t,L,U); ogni numero reale viene arrotondato con errore relativo al più u = ½β^(1−t) (u ≈ 1,1·10⁻¹⁶ in doppia precisione) e ogni operazione è esatta più un errore (1+δ), |δ| ≤ u. Conseguenze: overflow e underflow, somma non associativa, assorbimento, e soprattutto la cancellazione numerica nella differenza di numeri quasi uguali, che si evita riformulando l'espressione.Aritmetica di macchina - floating point, precisione di macchina e cancellazione →; sviluppo in Sviluppi di Mac-Laurin notevoliTabella degli sviluppi di Mac-Laurin da sapere a memoria (e^x, sin, cos, log(1+x), (1+x)^alpha, arctan, sinh, cosh, tan) e regole per combinarli: algebra degli o piccoli, prodotti, funzioni composte, quanti termini tenere.Sviluppi di Mac-Laurin notevoli →.

Testo

Si vuole calcolare g(x)=ex−1g(x) = e^x - 1 per xx piccolo e positivo.

  • (a) Calcolare il numero di condizionamento K(x)K(x) di gg e il suo limite per x→0x \to 0.
  • (b) Calcolare g(x)g(x) come "esponenziale meno 11" in aritmetica a 55 cifre significative per x=2⋅10−3x = 2\cdot 10^{-3}, 2⋅10−42\cdot 10^{-4}, 2⋅10−52\cdot 10^{-5}.
  • (c) Ricavare un algoritmo stabile e ripetere il calcolo.
  • (d) Domanda teorica: il problema è mal condizionato? L'algoritmo ex−1e^x - 1 è stabile? Spiegare.

Soluzione

(a) Condizionamento

g′(x)=exg'(x) = e^x, quindi K(x)=∣x g′(x)g(x)∣=x exex−1.K(x) = \left|\frac{x\,g'(x)}{g(x)}\right| = \frac{x\,e^x}{e^x - 1}. Per x→0x \to 0, ex−1∼xe^x - 1 \sim x e ex→1e^x \to 1, quindi K→x⋅1x=1K \to \dfrac{x \cdot 1}{x} = 1. Valori: K(2⋅10−3)=1,0010K(2\cdot 10^{-3}) = 1{,}0010, K(2⋅10−4)=1,0001K(2\cdot 10^{-4}) = 1{,}0001. Il problema è ben condizionato: un errore relativo sul dato xx resta un errore relativo dello stesso ordine sul risultato.

(b) Algoritmo "exp(x) - 1"

Si calcola exe^x, si arrotonda a 55 cifre, si sottrae 11.

xx exe^x esatto exe^x a 5 cifre ex−1e^x - 1 calcolato g(x)g(x) esatto errore relativo
2⋅10−32\cdot 10^{-3} 1,002002001{,}00200200 1,00201{,}0020 0,00200000{,}0020000 2,0020013⋅10−32{,}0020013\cdot 10^{-3} 1,0⋅10−31{,}0\cdot 10^{-3}
2⋅10−42\cdot 10^{-4} 1,000200021{,}00020002 1,00021{,}0002 0,000200000{,}00020000 2,0002000⋅10−42{,}0002000\cdot 10^{-4} 1,0⋅10−41{,}0\cdot 10^{-4}
2⋅10−52\cdot 10^{-5} 1,000020001{,}00002000 1,00001{,}0000 00 2,0000200⋅10−52{,}0000200\cdot 10^{-5} 100%100\%

Gli errori di arrotondamento del 55-esimo decimale sono ora in primo piano: con x=2⋅10−5x = 2\cdot 10^{-5} tutte le cifre sono perdute.

(c) Algoritmo stabile

Dallo sviluppo di Mac-Laurin ex−1=x+x22+x36+…e^x - 1 = x + \frac{x^2}2 + \frac{x^3}6 + \dots (nessuna sottrazione di numeri vicini: tutti i termini sono positivi):

xx xx x22\frac{x^2}2 x36\frac{x^3}6 somma a 5 cifre
2⋅10−32\cdot 10^{-3} 2,0000⋅10−32{,}0000\cdot 10^{-3} 2,0000⋅10−62{,}0000\cdot 10^{-6} 1,3333⋅10−91{,}3333\cdot 10^{-9} 2,0020⋅10−3\mathbf{2{,}0020\cdot 10^{-3}}
2⋅10−42\cdot 10^{-4} 2,0000⋅10−42{,}0000\cdot 10^{-4} 2,0000⋅10−82{,}0000\cdot 10^{-8} 1,3333⋅10−121{,}3333\cdot 10^{-12} 2,0002⋅10−4\mathbf{2{,}0002\cdot 10^{-4}}
2⋅10−52\cdot 10^{-5} 2,0000⋅10−52{,}0000\cdot 10^{-5} 2,0000⋅10−102{,}0000\cdot 10^{-10} 1,3333⋅10−151{,}3333\cdot 10^{-15} 2,0000⋅10−5\mathbf{2{,}0000\cdot 10^{-5}}

Tutte le cifre a disposizione sono corrette (per x=2⋅10−5x = 2\cdot 10^{-5} l'esatto è 2,00002⋅10−52{,}00002\cdot 10^{-5}, che a 55 cifre è 2,0000⋅10−52{,}0000\cdot 10^{-5}: scarto relativo 10−510^{-5}, cioè l'ultima cifra). Il termine x36\frac{x^3}{6} è inutile sotto x≈10−3x \approx 10^{-3}. In doppia precisione esiste la funzione dedicata expm1, che applica lo stesso principio per ogni xx.

(d) Domanda teorica

Il problema è ben condizionato (K→1K \to 1): non è colpa dei dati. L'algoritmo "calcola exe^x, sottrai 11" è instabile per xx piccolo: ex≈1+xe^x \approx 1 + x è calcolato con errore relativo uu, cioè con errore assoluto ≈u\approx u, comparabile con xx quando x≈ux \approx u; la sottrazione (esatta) lascia solo il rumore. Errore relativo sul risultato ≈u/x\approx u/x, molto più di K⋅uK\cdot u. Controllo in doppia precisione con x=10−10x = 10^{-10}: np.exp(x) - 1 dà 1,00000008274⋅10−101{,}00000008274\cdot 10^{-10} invece di 1,00000000005⋅10−101{,}00000000005\cdot 10^{-10} (errore relativo 8,3⋅10−88{,}3\cdot 10^{-8}, sotto il maggiorante u/x≈1,1⋅10−6u/x \approx 1{,}1\cdot 10^{-6}), e per x=10−16x = 10^{-16} dà 00 invece di 10−1610^{-16}; np.expm1(x) è esatta in entrambi i casi.

Risultati. K→1K \to \mathbf{1} (problema ben condizionato); con 55 cifre la formula ex−1e^x - 1 perde tutto per x=2⋅10−5x = 2\cdot 10^{-5}; la serie dà 2,0000⋅10−5\mathbf{2{,}0000\cdot 10^{-5}}.

Errori tipici

Versione ripasso

(a) K=xexex−1→1K=\frac{x e^x}{e^x-1}\to1 per x→0x\to0 (K(2⋅10−3)=1,0010K(2\cdot10^{-3})=1{,}0010): problema ben condizionato (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 →).

(b) Algoritmo ex−1e^x-1 a 55 cifre:

xx exe^x a 5 cifre calcolato esatto errore
2⋅10−32\cdot10^{-3} 1,00201{,}0020 0,00200000{,}0020000 2,0020013⋅10−32{,}0020013\cdot10^{-3} 10−310^{-3}
2⋅10−42\cdot10^{-4} 1,00021{,}0002 0,000200000{,}00020000 2,0002000⋅10−42{,}0002000\cdot10^{-4} 10−410^{-4}
2⋅10−52\cdot10^{-5} 1,00001{,}0000 00 2,00002⋅10−52{,}00002\cdot10^{-5} 100%100\%

(c) ex−1=x+x22+x36+…e^x-1=x+\frac{x^2}2+\frac{x^3}6+\dots (termini positivi): 2,0020⋅10−32{,}0020\cdot10^{-3}, 2,0002⋅10−42{,}0002\cdot10^{-4}, 2,0000⋅10−52{,}0000\cdot10^{-5}, tutte cifre corrette. In doppia: expm1.

(d) Problema ben condizionato, algoritmo instabile (errore assoluto ≈u\approx u su ex≈1e^x\approx1, relativo ≈u/x\approx u/x). Doppia precisione, x=10−10x=10^{-10}: exp(x)-1 =1,00000008274⋅10−10=1{,}00000008274\cdot10^{-10} (errore 8,3⋅10−88{,}3\cdot10^{-8}); x=10−16x=10^{-16}: 00.

Errori tipici: dedurre il cattivo condizionamento dall'errore (va calcolato KK); arrestare la serie troppo presto per xx non piccolo.

Teoria collegata