Esercizio - Radici di un'equazione di secondo grado in F(10,4) senza cancellazione

Teoria: 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 →.

Testo

Si risolve $x^2 - 200x + 1 = 0$ in un'aritmetica decimale che arrotonda ogni risultato a $4$ cifre significative.

• (a) Calcolare le radici con la formula $x_{1,2} = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$ e confrontare con le radici esatte.
• (b) Calcolare la radice grande con la formula e la piccola con la relazione tra le radici. Confrontare.
• (c) Domanda teorica: per quale radice la formula standard soffre di cancellazione, in funzione del segno di $b$?
• (d) Con la stessa idea, risolvere in doppia precisione $x^2 - 10^8x + 1 = 0$ e dire quanto è l'errore della formula standard.

Soluzione

Valori esatti (a $50$ cifre)

$x_{1,2} = 100 \pm \sqrt{9999}$, quindi $x_1 = 199{,}995000\ldots$ e $x_2 = 0{,}005000125\ldots$.

(a) Formula standard

• $b^2 = 40000$ (esatto).
• $4ac = 4$, quindi $b^2 - 4ac = 39996$, che a $4$ cifre significative si arrotonda a $4{,}000 \cdot 10^4 = 40000$.
• $\sqrt{40000} = 200{,}0$.
• $x_1 = \dfrac{200 + 200{,}0}{2} = 200{,}0$: errore relativo $\frac{0{,}005}{199{,}995} \approx 2{,}5 \cdot 10^{-5}$, accettabile.
• $x_2 = \dfrac{200 - 200{,}0}{2} = 0$: sbagliata del 100% (la vera radice è $0{,}005$).

Il discriminante ha perso le sue ultime cifre nell'arrotondamento, e la differenza tra due numeri quasi uguali ($200$ e $\sqrt{39996} = 199{,}990$) azzera tutto quello che resta.

(b) Formula stabile

Per la relazione tra radici $x_1x_2 = \frac ca = 1$ si ha $x_2 = \dfrac{c}{a\,x_1}$. Con $x_1 = 200{,}0$: $$x_2 = \frac{1}{200{,}0} = 0{,}005000.$$ Errore relativo: $\frac{|0{,}005000 - 0{,}005000125|}{0{,}005000125} \approx 2{,}5 \cdot 10^{-5}$, cioè circa $4$–$5$ cifre corrette, come per $x_1$. La divisione non ha cancellazione, e l'errore di $x_1$ si trasmette in modo relativo (una divisione non lo amplifica).

(c) Quale radice soffre

La cancellazione si ha quando $|b| \gg |ac|$, nella somma tra $-b$ e $\pm\sqrt{b^2-4ac} \approx \pm |b|$: se i due termini hanno segno opposto si annullano. Per $b < 0$ (come qui) è la radice con $-$ (la piccola), per $b > 0$ è quella con $+$. Si calcola quindi per prima la radice in cui i due termini hanno lo stesso segno: $$x_1 = \frac{-b - \operatorname{sgn}(b)\sqrt{b^2 - 4ac}}{2a}, \qquad x_2 = \frac{c}{a\,x_1}.$$

(d) Doppia precisione

Con $b = -10^8$, $c = 1$: $b^2 - 4 = 10^{16} - 4$ è un numero di macchina (vicino a $10^{16}$ il passo è $2$) e la sua radice vale $10^8 - 2\cdot 10^{-8}$ circa. Vicino a $10^8$ il passo tra numeri di macchina è $1{,}49\cdot 10^{-8}$, quindi la radice è arrotondata a $10^8 - 1{,}49\cdot 10^{-8}$ (un solo passo sotto $10^8$). Allora

• formula standard: $x_2 = \frac{10^8 - (10^8 - 1{,}49\cdot 10^{-8})}{2} = 7{,}45\cdot 10^{-9}$ invece di $10^{-8}$: errore del $25\%$ (la differenza è esatta, ma il suo unico dato è l'ultimo bit della radice);
• formula stabile: $x_1 = \frac{10^8 + \sqrt{\cdot}}{2} = 10^8$ e $x_2 = 1/10^8 = 10^{-8}$ (corretto fino all'ultima cifra).

Risultato. Formula standard: $x_2 = \mathbf{0}$ (sbagliata); formula stabile: $x_2 = \mathbf{0{,}005000}$ con errore relativo $2{,}5\cdot 10^{-5}$.

Errori tipici

• Pensare che il problema dipenda dal calcolatore: è la formula a essere instabile, non l'equazione (le due radici sono ben condizionate).
• Usare la relazione $x_1x_2 = c/a$ prima di aver calcolato $x_1$ con la formula giusta (cioè senza cancellazione).