martedì 31 maggio 2011

A volte i computer non ce la fanno — 2

Anche se noi pensiamo di utilizzare una calcolatrice con tanta memoria, o un computer che memorizza i numeri reali utilizzando molto spazio, potremmo sempre incappare in qualche problema.

Per esempio, consideriamo l'equazione seguente:

(x-1)(x-2)(x-3)…(x-19)(x-20) = 0.

Non è difficile capire che ha venti soluzioni, i numeri naturali da 1 a 20. Basta sostituirli per vedere che risulta sempre 0.

Se noi svolgiamo quelle 19 moltiplicazioni tra binomi, otteniamo questa espressione:

x20 - 210x19 + 20615x18 - 1256850x17 + 53327946x16 -
1672280820x15 + 40171771630x14 - 756111184500x13 +
11310276995381x12 - 135585182899530x11 + 1307535010540395x10 -
10142299865511450x9 + 63030812099294896x8 -
311333643161390640x7 + 1206647803780373360x6 -
3599979517947607200x5 + 8037811822645051776x4 -
12870931245150988800x3 + 13803759753640704000x2 -
8752948036761600000x + 2432902008176640000.

Un po' meno bella della precedente, ma è sempre lei.

Ora, supponiamo che un errore di approssimazione modifichi leggermente una delle cifre di questo lungo polinomio. Immaginiamo, ad esempio, che il computer che stiamo utilizzando abbia a disposizione 30 bit per memorizzare le cifre significative.

Diamo un'occhiata al coefficiente di x19, cioè -210; servono 8 bit per memorizzarlo, e ci rimangono così 22 bit per la parte decimale, che è tutta a zero.

Modifichiamo quel coefficiente di un'inezia: lo diminuiamo di 2-23, un numero molto piccolo. Ora è diventato uguale a circa -210.0000001192: ci aspettiamo che le soluzioni dell'equazione così perturbata non siano molto diverse da quelle dell'equazione iniziale. Il nostro computer con 30 cifre significative, in effetti, non è in grado di distinguere tra -210 e -210-2-23, perché questi due numeri sono diversi a partire dal trentunesimo bit. Per lui l'equazione perturbata e quella iniziale sono uguali.

Vediamo invece che succede: se nell'equazione perturbata sostituiamo 20 al posto di x, invece di ottenere 0 abbiamo la bellezza di −6.25×1017, un numero grandicello. Le venti soluzioni dell'equazione iniziale sono ora queste (approssimate alla quinta cifra dopo la virgola):

1.00000, 2.00000, 3.00000, 4.00000, 5.00000,
6.00001, 6.99970, 8.00727, 8.91725, 20.84691.

Se le contate, non sono venti, ma solo dieci! Le altre dieci spariscono (o diventano complesse coniugate, se ci mettiamo nei numeri complessi).

Dunque una piccola modifica in un coefficiente produce un errore gigantesco nelle soluzioni. E questo, per uno che si affida ai computer per risolvere le equazioni, è Male.

Si può pensare che sui polinomi non ci sia più nulla da scoprire, ma il comportamento imprevedibile di questo particolare polinomio è stato scoperto solo nel 1984, in un un articolo dal meraviglioso titolo The perfidious polynomial.

In cui Wilkinson, l'autore, scrive:

Speaking for myself I regard it as the most traumatic experience in my career as a numerical analyst.

10 commenti:

Piscu ha detto...

insomma, finché qualcuno non inventa una calcolatrice euristica non potremmo mai stare sicuri?

zar ha detto...

Eh, bisogna fare un'analisi di stabilità, non fidarsi così dei conti...

Anonimo ha detto...

l'Analisi Numerica esiste per questo e se fatta bene è una materia estremamente interessante :)

zar ha detto...

Già

juhan ha detto...

Io sono rimasto indietro a commentare il post precedente. Colpa mia certo ma da condividere in parte con Telecom che mi ha tagliato fuori dalla Rete per 20 giorni. Probabilmente ci faccio un post, sulle approssimazioni non sulla disavventura: per quella temo teh claud prossima ventura

zar ha detto...

Bene, bene, posta.

tetrapharmakon ha detto...

Mah, non si puo' piuttosto affermare che e' l'analisi numerica ad essere male? Studiate geometria aritmetica, e i vostri spazi di Banach p-adici saranno la culla di sonni tranquilli.

nico ha detto...

Io sono un matematico per natura, e un informatico per lavoro. Proprio per questo il tuo post mi è piaciuto veramente parecchio! Complimenti!

zar ha detto...

Grazie.

Marco_Panino ha detto...

Stano... sul mio funziona! (tm)