Capitolo 1 I NUMERI 1.1 Basi di numerazionemichela/12.pdf · 2 Capitolo 1. I numeri b cifre 2 0 1 8...

Capitolo 1

I NUMERI

1.1 Basi di numerazione

Un numero e una sequenza finita di simboli detti cifre. I simboli utilizzatidipendono dal sistema di numerazione utilizzato.

Il sistema di numerazione usualmente utilizzato e detto posizionaledecimale, dove posizionale indica che il valore di una cifra dipende dallaposizione che essa ha all’interno di un certo numero, e decimale indicache la base utilizzata e b = 10. I simboli utilizzati in base 10 sono0, 1, 2, 3, 4, 5, 6, 7, 8 e 9.Ad esempio, se scriviamo il numero 9102.917 intendiamo esprimere ilnumero

9 × 103 + 1 × 102 + 0 × 101 + 2 × 100 + 9 × 10−1 + 1 × 10−2 + 7 × 10−3

Si noti che la notazione posizionale non e l’unica esistente. Esistonoanche altri sistemi di numerazione, ad esempio la numerazione romana,in cui ogni cifra del numero rappresenta sempre il proprio valore (M =1000, X = 10, V = 5, I = 1, . . .).

Nulla vieta, per rappresentare un numero reale a ∈ R, di utilizzarebasi diverse dalla decimale. Sia dunque b ∈ N una base qualsiasi. Perrappresentare i numeri in base b sono necessari esattamente b simboli.Se 2 ≤ b ≤ 10 si usano come simboli le prime b cifre della base decimale,ovvero i simboli 0, 1, . . . ,b − 1.Se b > 10, si aggiungono alle 10 cifre decimali le lettere maiuscoledell’alfabeto.Ad esempio:

1

2 Capitolo 1. I numeri

b cifre2 0 18 0 1 2 3 4 5 6 716 0 1 2 3 4 5 6 7 8 9 A B C D E F

Quindi, generalizzando, un numero a ∈ R puo essere espresso in baseb nella forma

a = ± (anan−1an−2 . . . a1a0 . a−1a−2 . . .)b

= ±n∑

i=−∞

aibi

con ai cifre della base b.La parte che precede il punto di radice viene detta parte intera e quellache segue il punto di radice viene detta parte frazionaria.

Se lavoriamo con una base generica b, e importante indicare in qualebase e espresso un numero dato, in quanto il suo valore varia al variaredi b. Quando vi possono essere ambiguita nella scrittura, e opportunoindicare come pedice il valore di b.Ad esempio:

123.110 = 1 × 102 + 2 × 101 + 3 × 100 + 1 × 10−1 = 123.110

123.17 = 1 × 72 + 2 × 71 + 3 × 70 + 1 × 7−1 = 66.142857142 . . .10

123.14 = 1 × 42 + 2 × 41 + 3 × 40 + 1 × 4−1 = 27.2510

E anche evidente che lo stesso numero necessita di un numero di cifremaggiore o uguale, al diminuire della base b.Ad esempio:

25310 = FD16

= 3758

= 111111012

1.1.1 Cambiamento di base

Si e visto che lo stesso numero reale puo essere rappresentato rispetto adifferenti basi. Noi siamo ovviamente abituati ad operare in base 10, ma,ad esempio, i computer lavorano con numeri espressi in base 2 e quindi eimportante conoscere le modalita di passaggio da una base all’altra e leproblematiche che tali cambiamenti di base possono creare.

E noto che i numeri reali si possono suddividere in due sottoinsiemi: inumeri razionali (insieme Q) ed i numeri irrazionali (insieme I). A lorovolta i numeri razionali possono essere divisi in due categorie: i numeria parte frazionaria finita ed i numeri periodici (e come tali illimitati).

1.1. Basi di numerazione 3

Per ambedue le categorie e possibile trovare la frazione generatrice (cioe

la frazionen

mtale che a =

n

m, con n ed m interi, espressi in base b):

Numeri finiti: Dato un numero a, rappresentato in base b, con partefrazionaria finita, la frazione generatrice ha come numeratore tuttoil numero (privato del punto di radice e degli zeri davanti alla primacifra significativa) e, come denominatore, un 1 seguito da tanti zeriquante sono le cifre che formano la parte frazionaria.Ad esempio calcoliamo la frazione generatrice del numero 73.4568

ed anche la corrispondente frazione generatrice decimale (ottenutaconvertendo numeratore e denominatore in base 10):

73.4568 = 734568 × 8−3 =

(73456

1000

)

8

=

(30510

512

)

10

=

(15255

256

)

10

Numeri periodici: Dato un numero a, periodico in base b, la frazionegeneratrice ha per numeratore tutto il numero (privato del puntodi radice e degli zeri davanti alla prima cifra significativa) menoil numero ottenuto togliendo le cifre del periodo (e trascurando ilpunto di radice) e per denominatore il numero formato da tantecifre b − 1 quante sono le cifre del periodo, seguite da tanti zeriquante sono le cifre dell’antiperiodo (che e la parte che segue ilpunto di radice e che precede il periodo).Ad esempio:Sia b = 16. Calcoliamo le frazioni generatrici dei numeri 0.2D16 e0.AE16 ed anche le corrispondenti frazioni generatrici decimali:

Primo numero:

0.2D16 =

(2D − 2

F0

)

16

=

(2B

F0

)

16

=

(43

240

)

10

Secondo numero:

0.AE16 =

(AE − A

F0

)

16

=

(A4

F0

)

16

=

(41

60

)

10

Il passaggio da una base b1 ad una base b2 non conserva necessaria-mente la tipologia del numero e questo, come vedremo, fara parte di unadelle caratteristiche da tener presente quando si lavora con i computer.Vediamo alcune regole da ricordare relativamente al cambiamento di basedi un numero:


• Se un numero e illimitato non periodico in una certa base, lo eanche in tutte le altri basi possibili.

• Un numero finito in una certa base, puo essere finito oppure perio-dico in un’altra base.

• Un numero periodico in una certa base, puo essere periodico oppurefinito in un’altra base.

Dato un numero razionale a espresso in base b1, e possibile sapereanticipatamente se esso e, o meno, finito in base b2:

Si calcola la frazione generatrice decimale, ovvero a =n

mcon n ed m

espressi in base 10. Se m risulta essere una potenza di b2 (ovvero m = be2

con e ∈ N) allora in base b2 il numero sara finito.Ad esempio:

Esempio 1

Controlliamo se il numero decimale finito 872.4310 e finito anche in base2.

872.4310 =

(87243

100

)

10

=

(87243

22 · 52

)

10

e poiche tale frazione e irriducibile, il numero finito in base decimale nonlo e certamente in base binaria.

Esempio 2

Calcoliamo in quale/i base/i il numero decimale periodico 0.410 e finito.

0.410 =

(4

9

)

10

=

(4

32

)

10

pertanto il numero e finito in base 3 ed in base 9 e si ha

0.410 = 0.113 = 0.49

Vediamo ora come convertire un numero reale da una base b1 ad unabase b2. Vi sono differenti modalita per effettuare la conversione a se-conda dei valori assunti da b1 e da b2.

Caso b2 = 10

Numero finito: Vi sono due possibili algoritmi per calcolare il valoredecimale (che potrebbe non essere finito) di un numero reale (finito)espresso in base qualsiasi b1:


1. Utilizzo della notazione posizionale: si calcola il valore utilizzandola definizione

a = ± (anan−1an−2 . . . a1a0.a−1a−2 . . . a−m)b

= ±n∑

i=−m

aibi

Vediamo alcuni esempi:Esempio 1

2401.23145 = 2 × 53 + 4 × 52 + 1 +2

5+

3

52+

1

53+

4

54= 351.534410

Esempio 2

110110.1012 = 1× 25 + 1× 24 + 1× 22 + 1× 2 +1

2+

1

23= 54.62510

Esempio 3

21.213 = 2 × 3 + 1 +2

3+

1

32= 7.710

2. Utilizzo dell’Algoritmo di Horner: si considerano separatamentela parte intera e la parte frazionaria del numero e poi si procedecome segue:Parte intera: Partendo dalla prima cifra significativa alla sinistra,verso destra, si moltiplica il valore per la base b1 e si aggiunge lacifra successiva. Il risultato si moltiplica per la base b1 e si aggiungela cifra successiva, e cosı via sino all’esaurimento delle cifre. Ovvero

(anan−1an−2 . . . a1a0)b =((· · · ((an×b1+an−1)×b1+an−2)×b1+· · · )×b1+a1)×b1+a0

Parte frazionaria: Partendo dalla prima cifra significativa alladestra della parte frazionaria, verso sinistra, fino al punto di radicesi divide il valore per la base b1 e si aggiunge la cifra precedente.Il risultato si divide per la base b1 e si aggiunge la cifra precedentee cosı via sino all’esaurimento delle cifre, terminando con una divi-sione per b1. Ovvero

(0.a−1a−2a−3 . . . a−m+1a−m)b

=((· · · ((a−m : b1+a−m+1) : b1+a−m+2) : b1+· · · ) : b1+a−1) : b1


Vediamo un esempio:

110110.0012 =

parte intera → ((((1×2 +1)× 2 +0)× 2 +1)× 2 +1)× 2 + 0→ 5410

parte frazionaria → ((1 : 2 + 0) : 2 + 0) : 2→ 0.12510

= 54.12510

Numero periodico: Supponiamo ora che il numero espresso in baseb1 abbia parte frazionaria periodica. Come possiamo procedere per cal-colare la parte frazionaria decimale, visto che essendo illimitata la partefrazionaria in base b1, non possiamo utilizzare ne la notazione posizionalene l’algoritmo di Horner? Possiamo far uso della regola di determinazionedella frazione generatrice decimale di un numero periodico in base qual-siasi precedentemente indicata.Vediamo qualche esempio:

Esempio 1

Convertiamo il numero 0.14 in base b2 = 10:

0.14 =

(1

3

)

4

=

(1

3

)

10

=

(3

9

)

10

= 0.310

Esempio 2

Convertiamo il numero 0.2D16 in base b2 = 10:

0.2D16 =

(2D − 2

F0

)

16

=

(2B

F0

)

16

=

(43

240

)

10

= 0.1791610

Esempio 3


4.315 =

(431 − 43

40

)

5

=

(333

40

)

5

=

(93

20

)

10

= 4.6510

Caso b1 = 10

Numero finito: Sia dato un numero decimale finito che si vuole con-vertire in base b2 (e in tale base potrebbe essere non finito). Bisognaanzitutto distinguere la parte intera dalla parte frazionaria ed operare inmodo differente:


Parte intera: L’algoritmo di conversione ha sempre termine e consistenell’effettuare iterativamente delle divisioni per la nuova base b2,fermandosi solo quando si ottiene un quoziente nullo. I resti delledivisioni effettuate, presi in ordine inverso a quello con cui sonostati calcolati, formano la parte intera del numero convertito. Ov-viamente i resti ottenuti sono dei numeri decimali il cui valore e< b2. Se b2 > 10, per formare il numero nella nuova base, ai restidecimali vanno sostituiti (se necessario) i corrispondenti simbolidella nuova base di numerazione.

Parte frazionaria: Si moltiplica ripetutamente per la base b2 e si tol-gono le parti intere che, prese nell’ordine, formeranno la partefrazionaria del numero espresso nella nuova base b2. Anche in talcaso le parti intere ottenute sono dei numeri decimali il cui valore e< b2 e, quando b2 > 10, per formare il numero nella nuova base adessi vanno sostituiti (se necessario) i corrispondenti simboli dellanuova base di numerazione.Come e facilmente intuibile, non e assolutamente certo che tale pro-cedura termini dopo un numero finito di passi. Vi sono infatti duepossibilita:

1. Ad un certo passo si ottiene come valore del prodotto un nu-mero con parte frazionaria nulla. In questo caso il procedi-mento si arresta ed il numero nella nuova base sara finito.

2. Ad un certo passo si ottiene come valore del prodotto un nu-mero con parte frazionaria precedentemente gia trovata du-rante i passi precedenti. In questo caso si e individuato il pe-riodo della parte frazionaria del numero espresso nella nuovabase b2.

Vediamo ora alcuni esempi, utilizzando le seguenti convenzioni grafiche:Nella procedura di divisione per la parte intera del numero da convertire,con una freccia ascendente si indica che i resti ottenuti devono essereconsiderati in ordine inverso. Nella procedura di moltiplicazione per laparte frazionaria, con una freccia discendente si indica che le parti in-tere dedotte dai risultati delle moltiplicazioni devono essere consideratenell’ordine con il quale esse sono state ottenute; tali parti intere risultanoevidenziate nel prodotto tramite una sottolineatura delle stesse e vengonoovviamente sottratte dal prodotto prima di effettuare la successiva molti-plicazione; i caratteri ? posti a fianco di un certo numero di parti intere


contigue indicano che tali cifre formeranno il periodo del numero con-vertito; l’eventuale periodo viene individuato quando si trova un valoreda moltiplicare che sia gia stato considerato e i due valori coincidentivengono indicati da un simbolo ◦ che li precede.

Esempio 1


Divisioni Quozienti Resti

967 ÷ 16 60 710 = 716

60 ÷ 16 3 1210 = C16

3 ÷ 16 0 310 = 316

6

Moltiplicazione Parti intere

0.78125 ×16 = 12.5 1210 = C16

0.5 ×16 = 8.0 810 = 816

0.0?

Quindi967.7812510 = 3C7.C816 = 3.C7C816 × 162

Esempio 2



93 ÷ 2 46 146 ÷ 2 23 023 ÷ 2 11 111 ÷ 2 5 15 ÷ 2 2 12 ÷ 2 1 01 ÷ 2 0 1

6


0.625 ×2 = 1.25 10.25 ×2 = 0.5 00.5 ×2 = 1.0 10.0

?

Quindi si ottiene

93.62510 = 1011101.1012 = 0.10111011012 × 27


Esempio 3



20 ÷ 2 10 010 ÷ 2 5 05 ÷ 2 2 12 ÷ 2 1 01 ÷ 2 0 1

6


0.025 ×2 = 0.05 00.05 ×2 = 0.1 00.1 ×2 = 0.2 0

◦ 0.2 ×2 = 0.4 0 ?0.4 ×2 = 0.8 0 ?0.8 ×2 = 1.6 1 ?0.6 ×2 = 1.2 1 ?

◦ 0.2?

Avendo trovato un valore frazionario da moltiplicare, precedentementegia considerato (il valore 0.2), la parte frazionaria finita del numero datorisulta essere periodica in base 2.Si ottiene quindi

20.02510 = 10100.00000112

Esempio 4



7 ÷ 7 1 01 ÷ 7 0 1

6


◦ 0.76 ×7 = 5.32 5 ?0.32 ×7 = 2.24 2 ?0.24 ×7 = 1.68 1 ?0.68 ×7 = 4.76 4 ?

◦ 0.76?


Avendo trovato un valore frazionario considerato in precedenza (il valore0.76), la parte frazionaria finita del numero dato risulta essere periodicain base 7.Quindi si ottiene

7.7610 = 10.52147

Numero periodico: Supponiamo ora che il numero decimale abbiaparte frazionaria periodica. Per la parte intera possiamo procedere comenel caso del numero finito. Ma come possiamo procedere per calcolare laparte frazionaria nella nuova base b2? Possiamo ancora usare il prece-dente algoritmo di moltiplicazione, ma lavorando con i cosiddetti numerimisti (intero+frazione propria).Vediamo qualche esempio:

Esempio 1



◦ 1

3×2 =

2

3= 0 +

2

30 ?

2

3×2 =

4

3= 1 +

1

31 ?

◦ 1

3

?

ottenendo0.310 = 0.012

Esempio 2



◦ 2

3×2 =

4

3= 1 +

1

31 ?

1

3×2 =

2

3= 0 +

2

30 ?

◦ 2

3

?

ottenendo0.610 = 0.102


Caso generale

Non vi sono algoritmi particolari qualora b1 o b2 non siano uguali a 10.In tale caso la conversione deve essere fatta in due tappe, passando at-traverso la base 10 (ovvero b1 → 10 → b2).La base 2 e le sue potenze sono molto utilizzate in informatica. Nelcaso in cui si debba passare dalla base 2 alla base 2k (o viceversa) esisteuna procedura pressoche immediata (senza dover passare per la base 10).Quando la base considerata e 2k, per rappresentare le sue 2k−1 cifre sononecessarie, in base 2, delle k-uple di cifre binarie. Ad esempio se b = 4 =22 le cifre 0, 1, 2, 3 in tale base sono rappresentabili dalle 4 coppie binarie(00)2, (01)2, (10)2 e (11)2. Se b = 16 = 24 le cifre in tale base sono rappre-sentabili dalle 16 quaterne binarie (0000)2, (0001)2, (0010)2, . . . , (1110)2 e(1111)2.Dato quindi un numero in base 2, per trasformarlo in base 2k e suffi-ciente, a partire dal punto di radice, verso sinistra per la parte intera everso destra per la parte frazionaria (aggiungendo eventualmente gli zerinecessari), raggruppare delle k-uple di cifre binarie e poi sostituire adesse la corrispondente cifra nella nuova base.Ad esempio:

Convertiamo il numero 10001.1101110112 in base b2 = 16 = 24:

0001︸︷︷︸

0001︸︷︷︸

. 1101︸︷︷︸

1101︸︷︷︸

1000︸︷︷︸

↓ ↓ ↓ ↓ ↓1 1 . D D 8

e si ha10001.1101110112 = 11.DD816 = 0.11DD816 × 162

Il procedimento inverso di passaggio da una base 2k alla base 2 e simi-lare, ma in tal caso si costruiscono, a partire dalle cifre della base 2k, lek-uple di cifre binarie.Ad esempio:


2 1 . 6 7 3↓ ↓ ↓ ↓ ↓

︷︸︸︷

010︷︸︸︷

001 .︷︸︸︷

110︷︸︸︷

111︷︸︸︷

011

e si ottiene

21.6738 = 10001.1101110112 = 0.10001110111011 × 25


Naturalmente tale procedimento puo essere utilizzato anche per pas-sare da una base b1 = 2k1 ad una base b2 = 2k2 , con due passi: prima dipassa dalla base b1 alla base 2 e poi dalla base 2 alla base b2.

Un altro vantaggio di tale conversione pressoche immediata si notain presenza di numeri con parte frazionaria periodica in quanto, in talcaso, anche nella nuova base il numero sara periodico ed il suo periodo efacilmente identificabile.Ad esempio:


1 6 3 2 . 6 3 1 4↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

︷︸︸︷

001︷︸︸︷

110︷︸︸︷

011︷︸︸︷

010 .︷︸︸︷

110︷︸︸︷

011︷︸︸︷

001︷︸︸︷

100

e quindi

1632.63148 = 1110011010.11002 = 0.111001101011002 × 210

1.1.2 Normalizzazione ed approssimazione

Un numero a ∈ R, rappresentato in base b, non ha una rappresentazioneunica. Infatti, ricordiamo che quando si sposta il punto di radice a destradi una posizione, il numero risulta moltiplicato per la base, e che quandosi sposta il punto di radice a sinistra di una posizione, il numero risultadiviso per la base.Ad esempio, per uno stesso numero espresso in base b ≥ 8, si hanno leseguenti rappresentazioni:

1234.57b × b5 = 0.123457b × b9 = 123457b × b3 = 1.23457b × b8

= 123457000b × b0 = 0.00123457b × b11 = · · ·

E possibile decidere che tutti i numeri vengano rappresentati in unastessa forma (ovvero in forma normalizzata). Ad esempio si puo decideredi adottare la convenzione che il numero debba essere rappresentato sem-pre con prima cifra significativa (ovvero cifra non nulla) alla destra delpunto di radice ovvero nella forma

a = ±(0.a1a2a3 . . .)b × be = ± (0.m)b × be

con a1 6= 0.e viene detto esponente o caratteristica ed m viene detta mantissa.


Con questa normalizzazione e possibile rappresentare tutti i numeri reali,eccettuato lo 0.

La normalizzazione non modifica la natura del numero reale. Pertantoi numeri scritti in forma normalizzata possono avere mantissa finita, op-pure periodica, oppure illimitata (ad esempio a = π).

Prima di proseguire, si desidera sottolineare quanto segue: consideria-mo un certo numero a ∈ Q espresso, ad esempio, in base 10. La suarappresentazione, anche se si fissa la normalizzazione, puo non essereunivoca. Vediamo questo esempio:Sia dato il numero 0.11910. Apparentemente e un numero periodico conparte frazionaria illimitata (0.119999999 . . .). Calcoliamo la sua frazionegeneratrice.

0.11910 =

(119 − 11

900

)

10

=

(108

900

)

10

= 0.1210

Questo significa che 0.11910 e 0.1210 sono due rappresentazioni, con lamedesima normalizzazione, dello stesso numero.

Esiste una regola generale per tale fenomeno: la rappresentazione nor-malizzata non e unica per tutti i numeri reali decimali il cui periodo sia9 e, se i numeri sono espressi in base b, per tutti i numeri reali il cuiperiodo sia uguale a b − 1. In tutti gli altri casi, la normalizzazionedetermina univocamente m ed e.

Supponiamo ora di poter conservare solo un numero t di cifre signi-ficative della mantissa di a (escludendo il punto di radice e lo zero che loprecede) e quindi di considerare una approssimazione di a del tipo:

a∗ = ±(0.a1a2a3 . . . at)b × be = ± (0.m∗)b × be = ±m∗

b× be−t

dove m e un intero formato dalle t cifre a1a2a3 . . . at.

Vi sono due modi per approssimare un numero conservando solo t cifredi mantissa:

Troncamento: Vengono banalmente trascurate nella mantissa m, tuttele cifre successive ad at.Ad esempio:a t a∗

(0.4567894251 . . .)10 3 0.45610

6 0.45678910

8 0.4567894210


Arrotondamento: Si usa la seguente regola:

a∗ = ±(0.a1a2a3 . . . at)b ·be dove at =

{at se at+1 < b/2at + 1 se at+1 ≥ b/2

at+1 e ovviamente la cifra che segue at, ovvero la prima cifra trascu-rata della mantissa.Ad esempio:a t a∗

(0.4567894251 . . .)10 3 0.45710

6 0.45678910

8 0.4567894310

1.1.3 Errore assoluto e relativo

Dato un numero reale decimale a ed una sua approssimazione a∗ sidefinisce

Errore assoluto: la quantita

εa = |a − a∗|

Errore relativo: la quantita

εr =|a − a∗|

|a| , con a 6= 0

In generale, l’errore relativo fornisce un’indicazione piu realistica di“quanto si sbaglia” considerando a∗ al posto di a, in quanto esso nonviene influenzato dall’ordine di grandezza dei numeri che si stanno con-siderando ed e legato unicamente al numero di cifre di a∗, a partire dallaprima, che coincidono con quelle di a.

Per conoscere quante cifre significative decimali in comune vi sono traun numero a ed una sua approssimazione a∗, e sufficiente calcolare ilvalore

− log10 εr.

Consideriamo il seguente esempio (errori e logaritmo decimale sonoapprossimati a 3 cifre significative):

a a∗

εa εr −log10 εr

0.456789425 × 10−30 0.4567895 × 10−30 7.5 × 10−38 1.64 × 10−7 6.790.456789425 × 10−30 0.6 × 10−30 1.43 × 10−31 3.14 × 10−1 0.5

1.2. Algoritmi 15

I valori di a e di a∗ sono molto piccoli. Nel secondo caso l’approssimazionea∗ non ha nessuna cifra significativa in comune con a, ma guardandol’errore assoluto esso sembrerebbe essere piccolo (dell’ordine di 10−31).L’errore relativo mette giustamente in luce la scarsa accuratezza dell’ap-prossimazione.

Si consideri ora l’esempio seguente

a a∗

εa εr −log10 εr

0.456789425 × 10+30 0.4567895 × 10+30 7.5 × 10+22 1.64 × 10−7 6.790.456789425 × 10+30 0.6 × 10+30 1.43 × 10+29 3.14 × 10−1 0.5

Sia a che a∗ sono valori molto grandi. Guardando gli errori assoluti(che sono grandi), sembrerebbe che entrambe le approssimazioni nonfossero buone. L’errore relativo (ed il logaritmo), invece, mostrano comela prima approssimazione sia accettabile. Si noti anche che gli errorirelativi di questo esempio coincidono esattamente con quelli dell’esempioprecedente.

Se consideriamo come approssimazione a∗ il valore ottenuto per tron-camento o arrotondamento a t cifre della mantissa normalizzata si hannole seguenti relazioni

Errore assoluto:

εa = |a − a∗| ≤ c × be−t

Errore relativo:

εr =|a − a∗|

|a| ≤ c × b1−t

con c =1

2se si lavora per arrotondamento e c = 1 se si lavora per

troncamento.

1.2 Algoritmi

1.2.1 Conversione da base 10 a base b di un numero intero

Siano dati a ∈ Z (in base 10) e b ≥ 2. Si desidera convertire in base b ilvalore assoluto di a. Applichiamo il procedimento delle divisioni ripetutead |a| ed otteniamo il seguente algoritmo.


read a ∈ Z

read b ≥ 2a = |a|while a 6= 0 do

q =⌊ a

b

⌋

r = a − q × b

print ra = q

end while

dove

⌊x

y

⌋

indica la parte intera della divisione tra x ed y. I resti in-

teri stampati, presi nell’ordine inverso (sostituendo eventualmente il cor-rispondente simbolo per le basi b > 10), danno le cifre del numero con-vertito in base b.

1.2.2 Conversione da base b a base 10 di un numero intero,

con l’algoritmo di Horner

Siano dati a ∈ Z, con |a| = (anan−1 . . . a0)b (rappresentato con n+1 cifredella base b). Si desidera calcolare il valore decimale del numero dato,utilizzando l’algoritmo di Horner.

read a ∈ Z

read n ∈ N

read b ≥ 2x = an

for i = n − 1, . . . , 0 step −1x = x × b + ai

end for

print sign(a)x

dove sign(a) rappresenta il segno di a. Le varie cifre del numero a vannofornite, per le basi b > 10, sostituendo eventualmente il corrispondentevalore decimale delle cifre non numeriche. Il valore sign(a)x corrispondeal numero convertito in base decimale.

1.2.3 Calcolo del valore di un polinomio in un punto

Sia dato un polinomio P di grado al piu n (P ∈ Pn) scritto nella forma

P (x) = α0xn + α1x

n−1 + · · · + αn−1x + αn, (1.1)

1.3. Esercizi 17

ed un punto x. Si vuole valutare P (x) ovvero il valore del polinomio nelpunto x.Possiamo applicare l’espressione (1.1) ovvero calcolare

P (x) =n∑

i=0

αixn−i

effettuando j − 1 moltiplicazioni per ogni potenza xj (j = 1, . . . , n), nmoltiplicazioni per i prodotti relativi ai coefficienti ed infine n addizioni,ovvero, in totale, n2 + n/2 moltiplicazioni ed n addizioni.In alternativa possiamo utilizzare il seguente schema iterativo

{β0 = α0

βi = x βi−1 + αi, i = 1, . . . , n

ottenendo βn = P (x). Con tale procedimento vengono eseguite solamenten moltiplicazioni ed n addizioni.Tale algoritmo corrisponde esattamente alla regola di Ruffini per trovareil polinomio quoziente Q(x) ed il resto r della divisione di P (x) per (x−x),con P (x) = Q(x)(x− x)+r, Q(x) = β0x

n−1+β1xn−2+ · · ·+βn−2x+βn−1,

r = P (x) ed anche all’algoritmo di Horner gia illustrato nelle conversionidella parte intera da base b a base 10. Si ha quindi

read nread αi, i = 0, . . . , nread xβ = α0

for i = 1, . . . , nβ = x × β + αi

end for

print β

1.3 Esercizi

Esercizio 1.1 Si scriva un algoritmo per la conversione da base 10 abase b della parte frazionaria di un numero.

Esercizio 1.2 Si scriva un algoritmo per la conversione da base b a base10 della parte frazionaria di un numero, con l’algoritmo di Horner.

Esercizio 1.3 Sapendo che se P (x) = Q(x)(x − x) + r, allora P ′(x) =Q′(x)(x − x) + Q(x) e quindi P ′(x) = Q(x) si scriva un algoritmo checalcoli il valore della derivata prima del polinomio P (x) nel punto x.

Capitolo 2

ARITMETICA DEL COMPUTER

2.1 Rappresentazione ed aritmetica dei numeri in-

teri

In questo contesto non ci interessa dare una trattazione completa dellevarie forme di rappresentazione degli interi nel computer. Ci limitiamoa dare alcune indicazioni che valgono per la quasi totalita dei computerattuali.

In un computer i numeri interi vengono memorizzati come numeri bi-nari in rappresentazione complemento a due. Per tale memorizzazionesono a disposizione un certo numero finito k di cifre binarie (bit = binarydigit), compreso il bit per rappresentare il segno del numero intero. Nontutti i numeri interi sono quindi rappresentabili, ma solo quelli compresitra nmin = −2k−1 e nmax = 2k−1 − 1.Gruppi di 8 bit vengono chiamati byte. Una word (o parola) puo es-sere di 16 bit (2 byte) o di 32 bit (4 byte), e la sua lunghezza dipendedall’architettura del computer. La maggior parte dei computer e in gradodi utilizzare k = 16 bit oppure k = 32 bit per memorizzare i numeri in-teri, qualsiasi sia la lunghezza della word. Con taluni linguaggi e possibilerichiedere altri valori per k (ad esempio k = 8 o k = 64).

Gli interi che appartengono all’intervallo [nmin, nmax] sono rappresentatiesattamente (nessun errore). Se si cerca erroneamente di memorizzare unnumero n < nmin (n > nmax) si ha la cosiddetta situazione di underflow(rispettivamente overflow).

Gli intervalli di interi rappresentabili per k = 16 e k = 32, con unarappresentazione complemento a due, sono:

19

20 Capitolo 2. Aritmetica del computer

byte bit nmin nmax

2 16 −215 = −32 768 215 − 1 = 32 7674 32 −231 = −2 147 483 648 231 − 1 = 2 147 483 647

Per quanto riguarda le operazioni aritmetiche tra interi (addizione, sot-trazione, moltiplicazione e divisione intera) esse danno sempre luogo adun risultato esatto. L’unico caso di errore puo avvenire qualora il risul-tato dell’operazione sia un numero esterno all’intervallo [nmin, nmax], conimpossibilita di rappresentare tale risultato e quindi con situazione diunderflow o di overflow.

2.2 Rappresentazione dei numeri reali

Come vedremo, l’utilizzo dei numeri reali su di un computer puo essere,a differenza dei numeri interi, causa di numerosi problemi.Usualmente i computer utilizzano per i numeri reali una rappresenta-zione normalizzata in base binaria (b = 2). Talvolta viene usata unanormalizzazione in base esadecimale (b = 16), anche se poi la mantissaviene memorizzata sul computer trasformando in binario le rispettivecifre esadecimali.

Sia fissata una certa normalizzazione ed una certa base b per il numeroreale a, ad esempio

a = ± (0.a1a2a3 . . .)b × be = ± (0.m)b × be

(la normalizzazione puo comunque variare da un computer ad un altro).Il numero di bit che sono a disposizione in un computer per rappre-

sentare un numero reale e sempre finito. Esso viene suddiviso logica-mente in tre parti in cui vengono rappresentati, rispettivamente, il segnodel numero (sempre un solo bit che viene posto uguale a zero, per i nu-meri positivi, ed uguale a uno, per i numeri negativi), l’esponente e lamantissa:

± esponente mantissa

Il numero di cifre a disposizione per la mantissa e per l’esponente interonon possono superare un certo limite prefissato. Questo porta a dueimportanti conseguenze:

1. Poiche il numero di cifre della mantissa m del numero a puo essereillimitato, oppure finito ma superiore al numero di cifre t messe a

2.2. Rappresentazione dei numeri reali 21

disposizione nella rappresentazione del computer, solo un numerofinito di numeri reali a possono essere esattamente rappresenta-ti esattamente all’interno del computer. Tutti gli altri verrannorappresentati con una loro approssimazione a∗.Il numero massimo t di cifre binarie, disponibile per la mantissa m,definisce la precisione del numero.

2. Il rango dei numeri reali normalizzati rappresentabili, presi in valoreassoluto, e compreso tra un valore minimo amin = bL−1 ed un valoremassimo amax = bU(1 − b−t), dove L < 0 e il minimo esponenterappresentabile e U > 0 e il massimo esponente rappresentabile.Quindi i numeri con |a| < amin non sono rappresentabili in formanormalizzata e si ha una condizione di underflow; il numero a intal caso viene trattato come zero oppure, se possibile, memorizzatocome numero denormalizzato (anche detto subnormalizzato) ed intal caso si parla di gradual underflow. I numeri con |a| > amax

danno luogo al cosiddetto overflow; il numero a in tal caso assumeil valore della rappresentazione al calcolatore dell’infinito (+Inf op-pure -Inf).

Pertanto solo un sottoinsieme dell’insieme R dei reali puo essere rappre-sentato in un computer. Tale sottoinsieme viene chiamato insieme deinumeri floating point (o numeri macchina, o numeri in virgola mobile)e, con la nostra ipotesi di normalizzazione, puo essere definito in questomodo:

F={0}∪{

a∗∈R : a

∗= ±(0.a1a2a3 . . . at)b×be =±b

e

t∑

i=1

aib−i =±m

∗

b×b

e−t

}

con b ≥ 2, 0 ≤ ai ≤ b − 1, a1 6= 0, L ≤ e ≤ U ed m∗

b= a1a2a3 . . . at.

Quindi all’interno di un computer noi memorizziamo solamente i numeri

± e m∗

b

con e a r cifre binarie e m∗

ba t cifre binarie.

Per memorizzare i numeri floating point, si usano usualmente 4 byte(semplice precisione) oppure 8 byte (doppia precisione). Su taluni com-puter e con certi linguaggi si possono chiedere anche 10 o 16 byte (pre-cisione estesa) oppure 6 byte. Il numero di bit dedicati alle due parti(esponente e mantissa) possono variare ed anche il tipo di rappresenta-zione binaria dell’esponente intero relativo e.


Con 4 byte (qualsiasi sia l’architettura del computer) si riescono a rap-presentare almeno 7 cifre decimali significative. Con 8 byte, tale numeroviene elevato a circa 16 cifre decimali.

Gli intervalli [−amax,−amin] e [amin, amax] della retta reale possonoessere molto grandi (se vi sono molte cifre binarie a disposizione perl’esponente e), ma i numeri di F (in valore assoluto) sono molto densivicino ad amin e piu radi verso amax.Ad esempio, con 4 byte, vi sono circa 8 388 607 numeri floating point tra1.0 e 2.0 e solo circa 8 191 tra 1023.0 e 1024.0.Si veda nella figura 2.1 una schematizzazione della cosiddetta floatingpoint real line.

min− a a amaxminmax 0

rango utilizzabile rango utilizzabile

zoom

denormalizzati

− a

overflowflow flow

overflowunderunder

Figura 2.1: Floating point real line

Utilizzando una notazione abituale che si ritrova in molti testi, datoun numero a ∈ R, indichiamo con fl(a) ∈ F la sua approssimazione cheviene rappresentata all’interno del computer.

E importante, a fronte di tale approssimazione, riuscire a dare unalimitazione superiore all’errore commesso (che in tal caso prende in nomedi errore di assegnazione). Utilizzando le relazioni viste nel capitoloprecedente, e tenuto presente che oramai la quasi totalita dei computerlavora con l’arrotondamento, avremo:

Errore assoluto:

εa = |a − fl(a)| ≤ 1

2× be−t.

Si ha quindifl(a) = a + ε1

con |ε1| = εa.

2.2. Rappresentazione dei numeri reali 23

Errore relativo:

εr =|a − fl(a)|

|a| ≤ 1

2× b1−t = eps. (2.1)

La quantita eps che, come si vede, dipende unicamente dalla base b

e dal numero di cifre t (e quindi non dal numero che si vuole rappre-sentare) viene chiamata precisione di macchina ed e una caratteri-stica dell’architettura del computer su cui si sta lavorando. Dipendenaturalmente anche dal numero di byte utilizzati nella rappresenta-zione dei numeri macchina, in quanto tale valore influisce sul valoredi t. Se la base utilizzata e 2, si ha eps = fl(2−t). Il valore eps

rappresenta il piu piccolo numero macchina positivo tale che

fl(1 + eps) > 1

Si ha anche

fl(a) = a (1 + ε2)

con |ε2| = εr ≤ eps.

Vediamo alcuni esempi di un programma dove viene letto un valorereale a, usando la semplice precisione, e poi viene immediatamente stam-pato a∗ = fl(a). I valori di εa ed εr vengono calcolati con un programmache usa la doppia precisione, utilizzando i valori a ed a∗ della tabella.

a a∗ εa εr

123456789.0 123456792.0 3.0 2.43 × 10−8

1.23456789 × 1013 1.2345679 × 1013 1.0 × 105 8.1 × 10−9

3.34567891 3.34567881 1.0 × 10−7 2.99 × 10−8

3.34567891 × 1010 3.34567895 × 1010 4.0 × 102 1.2 × 10−8

0.1 0.100000001 1.0 × 10−9 1.0 × 10−8

0.01 0.00999999978 2.2 × 10−10 2.2 × 10−8

0.001 0.00100000005 5.0 × 10−11 5.0 × 10−8

Dai risultati si evince che, sia la conversione in binario del numero deci-male, sia il numero limitato t di cifre della mantissa binaria che si possonomemorizzare, gia in fase di assegnazione, non ci permettono di lavorarecon l’esatto valore a, ma con una sua approssimazione che puo presentareun elevato errore assoluto. Resta comunque valida, per εr, la relazione(2.1) (eps nel caso della semplice precisione vale all’incirca 1.2 × 10−7).


La singola precisione puo in molti casi essere insufficiente a garantireuna sufficiente affidabilita dei calcoli (soprattutto nelle operazioni arit-metiche floating-point, come vedremo in seguito). In tal caso e sempreopportuno utilizzare almeno la doppia precisione, anche se cio provocaun allungamento dei tempi di calcolo e comunque non ci garantisce com-pletamente dell’esattezza dei calcoli (si veda la sezione 2.7).

2.3 Rappresentazione IEEE 754

Lo standard IEEE 754 per il calcolo in virgola mobile (per esteso, IEEEStandard for Binary Floating-Point Arithmetic, ANSI/IEEE Std 754-1985) e il piu diffuso. Il formato di rappresentazione dei numeri floatingpoint e piu complesso di quanto e stato descritto nella sezione prece-dente. Inoltre, con tale standard, possono essere rappresentati sia lo zeropositivo che lo zero negativo ed anche i seguenti valori speciali: infinitopositivo (Inf o +Inf), infinito negativo (-Inf), ±NaN (Not a Number).Il NaN viene utilizzato per rappresentare un valore che non e un numeroreale. Esso viene assegnato, ad esempio, come risultato di operazioniindeterminate quali ±0/± 0, ±∞/±∞, ∞−∞ e ±∞ · ±0.

La base per l’esponente e b = 2 e la normalizzazione viene fatta con-siderando un valore compreso tra 1 e 2, ovvero i numeri normalizzatihanno la forma

a∗ = ±(1.a1a2a3 . . . at)2 × 2e = ±(1 + 0.a1a2a3 . . . at)2 × 2e.

La cifra 1 a sinistra del punto di radice non viene rappresentata (hiddenbit, o bit nascosto, o bit implicito) e la mantissa corrisponde al numerobinario m∗ = a1a2a3 . . . at (t numero di bit disponibili). L’esponenteintero relativo e viene rappresentato eccesso 2r−1 − 1, dove r e il numerodi bit disponibili per l’esponente, al fine di non dover utilizzare un bit permemorizzare il segno dell’esponente. Viene quindi memorizzato il valoreintero binario positivo e∗ = e + 2r−1 − 1, ovvero si ha

± e∗ m∗

con a∗ = ±(1.m∗)2 × 2e∗−(2r−1−1).Per quanto riguarda il rango dei numeri reali normalizzati, presi in va-lore assoluto, rappresentabili con tale standard, esso e compreso tra unminimo amin = 2L ed un massimo amax = 2U(2 − 2−t), dove L < 0 e

2.3. Rappresentazione IEEE 754 25

il minimo esponente rappresentabile e U > 0 e il massimo esponenterappresentabile.

Il numero di bit dedicati alle varie parti (segno, esponente e mantissa)per la semplice e la doppia precisione sono i seguenti

byte bit segno esponente mantissa4 32 1 r = 8 t = 238 64 1 r = 11 t = 52

Il minimo esponente e = e∗ − (2r−1 − 1) corrisponderebbe ad una rap-presentazione in eccesso con tutti gli r bit uguali allo zero, ovvero e =0 − (2r−1 − 1) (in semplice precisione 0 − 127 = −127, ed in doppia pre-cisione 0− 1023 = −1023) ed il massimo esponente corrisponderebbe aduna rappresentazione in eccesso con tutti gli r bit uguali ad uno, ovveroe = 2r − 1 − (2r−1 − 1) (in semplice precisione 255 − 127 = 128, ed indoppia precisione 2047 − 1023 = 1024). In realta tali particolari confi-gurazioni assunte dall’esponente e∗ (tutti i bit uguali a zero oppure tuttii bit uguali ad uno) vengono riservate per indicare dei valori particolari(zero, Inf, NaN ed anche i numeri denormalizzati).

Quindi, riassumendo, per i numeri normalizzati si ha

byte bit L U4 32 −126 1278 64 −1022 1023

byte bit amin amax

4 32 1.17549435 × 10−38 3.40282347 × 1038

8 64 2.2250738585072014 × 10−308 1.7976931348623157 × 10308

e, per i valori particolari,

±0 ± tutti i bit uguali ad 0 tutti i bit uguali a 0

±Inf ± tutti i bit uguali ad 1 tutti i bit uguali a 0

±Nan ± tutti i bit uguali ad 1 almeno un bit diverso da 0

Restano da definire i numeri denormalizzati che corrispondono ad unarappresentazione del tipo

± tutti i bit uguali ad 0 m∗ qualsiasi non nullo


Tali rappresentazioni corrispondono a dei numeri reali per i quali il bitimplicito alla sinistra e uguale a zero (anziche ad uno), e l’esponente esempre L, ovvero ai numeri

a∗ = ±(0.m∗)2 × 2L

che sono, in valore assoluto, minori di amin.Il numero reale denormalizzato piu piccolo rappresentabile in valore as-soluto diventa quindi 2L−t (in semplice precisione 1.40129846× 10−45 ed,in doppia precisione, 4.9406564584124654 × 10−324). Si veda ancora lafigura 2.1.

Relativamente alla precisione di macchina si ha

byte bit eps

4 32 fl(2−23) ' 1.19209290 × 10−7

8 64 fl(2−52) ' 2.2204460492503131 × 10−16

Nell’agosto del 2008 e stata pubblicata una revisione dello standardIEEE 754-1985, chiamata IEEE 754-2008, che estende, completa e sosti-tuisce la precedente versione.

2.4 Operazioni aritmetiche floating-point

Come si e visto, quello che viene rappresentato all’interno di un computere solo un sottoinsieme di R. Vediamo ora cosa accade alle operazio-ni aritmetiche elementari quando gli operandi sono numeri macchina.Indichiamo le operazioni macchina (per distinguerle dalle operazioni a-ritmetiche) con i simboli ⊕,ª,⊗,®.

Anzitutto si ricordi che le operazioni vengono eseguite utilizzando ap-posite zone di memoria della ALU (Arithmetic and Logic Unit), detteaccumulatori o registri. Se in memoria centrale vi sono a disposizione tcifre per la mantissa, negli accumulatori di norma ve ne e un numero su-periore (talvolta anche il doppio) in modo da aumentare la precisione delcalcolo. Ma anche questa accortezza, in certe condizioni, non puo evitareche nel calcolo si producono degli errori, talvolta anche grossolani.

Supponiamo di dover eseguire, utilizzando il computer, l’operazionex+y che indichiamo con x⊕y. Anzitutto quello che sara memorizzato, perquanto riguarda gli operandi, e una loro approssimazione, ovvero fl(x) efl(y). Inoltre, il risultato della somma tra fl(x) e fl(y) verra ulteriormenteapprossimato in quanto nella restituzione del risultato, si ritornera adavere t cifre per la mantissa. Pertanto:

2.4. Operazioni aritmetiche floating-point 27

x ⊕ y = fl(fl(x) + fl(y)) = (fl(x) + fl(y))(1 + ε1)

con |ε1| ≤ eps. Questo significa che, oltre agli errori di assegnazione,ad ogni addizione macchina si introduce un ulteriore errore. Cio e veroanche per le altre operazioni, ovvero si ha

x ª y = fl(fl(x) − fl(y)) = (fl(x) − fl(y))(1 + ε2)x ⊗ y = fl(fl(x) × fl(y)) = (fl(x) × fl(y))(1 + ε3)x ® y = fl(fl(x)/fl(y)) = (fl(x) / fl(y))(1 + ε4)

con |ε2|, |ε3|, |ε4| ≤ eps.

2.4.1 Proprieta

Le operazioni su F non godono di tutte le proprieta delle corrispondentioperazioni su R.L’unica proprieta che resta valida e la proprieta commutativa ovvero

x ⊕ y = y ⊕ xx ⊗ y = y ⊗ x

La proprieta associativa e la distributiva non sono piu valide! Si ha infatti

x ⊕ (y ⊕ z) 6= (x ⊕ y) ⊕ zx ⊗ (y ⊗ z) 6= (x ⊗ y) ⊗ zx ⊗ (y ⊕ z) 6= (x ⊗ y) ⊕ (x ⊗ z)x ⊗ (y ª z) 6= (x ⊗ y) ª (x ⊗ z)

Anche altre proprieta risultano non piu valide

(x ⊗ y) ® y 6= x(x ® y) ⊗ y 6= x(x ⊗ y) ® z 6= (x ® z) ⊗ y

Relazione anomala. Un’altra violazione importante e data dalla cosid-detta relazione anomala che sancisce la non unicita dell’elemento neutrodell’addizione e della sottrazione (ovvero dello zero). Tale relazione puoessere cosı espressa:

Se|fl(y)||fl(x)| < eps, allora x ⊕ y = fl(x)

x ª y = fl(x).

Cio accade quando x ed y hanno ordini di grandezza molto diversi.


13 13.5 14 14.5 15 15.5 16 16.5

0

0.5

1

1.5

2

q

((x+y)−x)/y

Figura 2.2: Effetti dell’aritmetica del computer

Vediamo un esempio: consideriamo la seguente espressione algebrica

(x + y) − x

y(2.2)

che nell’insieme R fornisce 1.0 come risultato, qualsiasi sia y 6= 0. Seprendiamo x = 1.0 ed y < eps, utilizzando un computer otterremo 0,a causa della relazione anomala. Se applichiamo in (2.2) la proprietacommutativa prima e l’associativa poi, otteniamo la seguente espressione(anch’essa matematicamente uguale ad 1.0)

y + (x − x)

y,

e con il computer otterremo, con gli stessi valori di x e di y, il risultatoesatto 1.

Ma il fenomeno e ben piu complicato. Infatti, diamo a y dei valorivicini alla precisione macchina (supponendo di lavorare con 8 byte), eprecisamente y = 10−q con q = 13.0 + k × 0.01 per k = 0, . . . , 350. Siottengono per l’espressione (2.2) i risultati della figura 2.2. Si vede che,


a seconda del valore di q, il risultato dell’espressione varia nell’intervallo[0, 2]. I valori di y sono decrescenti e, a partire da quando si realizza larelazione anomala, si ottiene sempre zero.

La non validita della proprieta associativa assume particolare rilevanzaquando si opera con numeri vicini ad amin oppure a amax. Vediamo,ad esempio, cosa accade alle seguenti espressioni algebriche equivalentiquando assegnamo ad x, y e a z, valori elevati come ordine di grandezza(utilizzando 4 byte e quindi con amax dell’ordine di 1038):

x × y

z=

x × y

z

Sia x ' 1030, y ' 1030, z ' 1025. Con la prima formula otteniamo unrisultato numerico dell’ordine di 1035, mentre con la seconda abbiamouna condizione di overflow ed otteniamo Inf.

Analogamente assegnamo dei valori aventi ordine di grandezza moltopiccolo (amin e dell’ordine di 10−38). Sia x ' 10−30, y ' 10−30, z ' 10−25.Con la prima formula otteniamo un risultato numerico dell’ordine di10−35, mentre con la seconda abbiamo una condizione di underflow edotteniamo 0.

2.4.2 Errori

Consideriamo ora l’errore relativo, e cambiamo leggermente notazione.Indichiamo

εr(x) =|x − fl(x)|

|x|per ogni x ∈ R.Sia

ε⊕r (x, y) =|(x + y) − (x ⊕ y)|

|x + y| , con x, y ∈ R,

l’errore commesso nel calcolo della somma di due numeri. In modo simi-lare si possono definire εªr (x, y), ε⊗r (x, y), ε®r (x, y).E possibile dimostrare che solamente le operazioni macchina ⊗ e ® sonostabili rispetto agli errori di arrotondamento, ovvero se εr(x) e εr(y) sonopiccoli, allora lo sono anche ε⊗r (x, y) ed ε®r (x, y). Un’operazione macchinasi dice stabile quando

∃ c > 0, tale che ε¯r (x, y) ≤ c (εr(x) + εr(y)) , ∀x, y ∈ R

dove ¯ rappresenta una qualsiasi operazione macchina.


Vediamo cosa accade quando deve essere eseguita una moltiplicazione(o una divisione). Si debba eseguire z = x × y (oppure z = x / y),con x, y, z ∈ R. Anzitutto i due valori reali a seguito dell’assegnazionein memoria, divengono fl(x) e fl(y). Poi il computer trasferisce dallamemoria agli accumulatori i due valori fl(x) ed fl(y) senza modificarela normalizzazione ma solamente aggiungendo degli zeri alla destra percompletare i bit addizionali a disposizione degli accumulatori. Successiva-mente viene effettuata l’operazione tra le mantisse e separatamente vienecalcolato l’esponente del risultato. Il risultato viene poi trasferito nuo-vamente in memoria, effettuando la normalizzazione e l’arrotondamentonecessari per ricondursi a t cifre di mantissa.

Di seguito riportiamo alcuni esempi, supponendo di lavorare (solo ascopo esplicativo) in un sistema a base decimale (con la base binariail discorso sara analogo), con t = 8 cifre decimali a disposizione perla mantissa in memoria e 2t = 16 cifre decimali a disposizione per lamantissa negli accumulatori.

Esempio 1

Sia x = 0.27531012 × 10−2 ed y = 0.35720021 × 104.

Memoria Accumulatore

fl(x) = 0.27531012 × 10−2 → 0.2753101200000000 × 10−2 ×fl(y) = 0.35720021 × 104 → 0.3572002100000000 × 104

fl(z) = 0.98340833 × 101 ← 0.0983408326791252 × 102

Con tali valori si ha x = fl(x) ed y = fl(y). Nel caso di una molti-plicazione, il prodotto di due mantisse di lunghezza massima t fornisceun risultato di lunghezza al massimo 2t. Pertanto il risultato e esattonell’accumulatore. L’unico errore che viene commesso e quello di asse-gnazione durante la restituzione in memoria quando il risultato vienenormalizzato e ridotto a t cifre di mantissa.

Esempio 2

Sia x = 0.57203146 × 10−1 ed y = 0.27001052 × 102.


fl(x) = 0.57203146 × 10−1 → 0.5720314600000000 × 10−1 /fl(y) = 0.27001052 × 102 → 0.2700105200000000 × 102

fl(z) = 0.21185525 × 10−2 ← 2.118552491954754 × 10−3


Anche in questo esempio non vi e errore di assegnazione, ovvero x = fl(x)ed y = fl(y). Nel caso della divisione, il risultato nell’accumulatore none sempre esatto (in quanto possono prodursi piu di 2t cifre). Vi e quindiun errore nel risultato dell’accumulatore in quanto sara arrotondato a 2tcifre. Nella restituzione in memoria l’errore di assegnazione sara almenonella t-esima cifra, a causa dell’arrotondamento e della normalizzazione.

Errore di cancellazione. Gli esempi mostrano che le moltiplicazionie le divisioni macchina non producono errori molto elevati. Purtroppocio non e sempre vero per le operazioni macchina ⊕ e ª. In talunecondizioni si puo realizzare uno degli errori piu deleteri, chiamato l’erroredi cancellazione. Esso si verifica quando si sommano tra loro numeri quasiuguali in modulo (ma di segno diverso) oppure quando si sottraggononumeri quasi uguali tra loro.E possibile infatti dimostrare che

ε⊕r (x, y) ≤ eps + (1 + eps)

(

εr(x)|x|

|x + y| + εr(y)|y|

|x + y|

)

con x, y ∈ R. Pertanto, quando y ' −x, il termine a destra (la maggio-razione) puo essere anche molto grande e puo permettere ad ε⊕r (x, y) diessere molto elevato. Un discorso analogo vale per la sottrazione ª.

Cerchiamo ora di descrivere cosa accade quando deve essere eseguitauna somma (o una differenza) tra due numeri in modo da capire perchetale operazione puo essere cosı imprecisa. Si debba eseguire z = x + y.Il computer trasferisce dalla memoria agli accumulatori i due valori fl(x)ed fl(y) senza modificare quello tra i due operandi che risulta essere ilmaggiore in valore assoluto, e modificando l’altro operando in modo cheabbia lo stesso esponente di quello maggiore in valore assoluto (vengonoquindi eventualmente aggiunti degli zeri davanti alla prima cifra a1).Anche in tal caso, in tale trasferimento, vengono aggiunti degli zeri alladestra per completare i bit addizionali a disposizione degli accumula-tori. Successivamente viene effettuata l’operazione ed il risultato vienepoi trasferito nuovamente in memoria, effettuando la normalizzazione el’arrotondamento necessari per ricondursi a t cifre di mantissa.

Riportiamo alcuni esempi supponendo ancora di lavorare in un sistemaa base decimale, con t = 8 cifre decimali per la mantissa in memoria e2t = 16 cifre decimali per la mantissa negli accumulatori. Per un sistemadi questo tipo, utilizzando la formula (2.1), si ha eps = 0.5 × 10−7.


Esempio 1

Sia x = 0.23487757 × 103 ed y = 0.56799442.


fl(x) = 0.23487757 × 103 → 0.2348775700000000 × 103 +fl(y) = 0.56799442 × 100 → 0.0005679944200000 × 103

fl(z) = 0.23544556 × 103 ← 0.2354455644200000 × 103

Abbiamo x = fl(x) ed y = fl(y). Per quanto riguarda l’addizione, essaviene eseguita nell’accumulatore in modo esatto (ovvero conservandoesattamente i valori fl(x) ed fl(y)) e l’unico errore introdotto risulta esserequello di assegnazione durante la restituzione del risultato in memoria(poiche dobbiamo conservare solo t = 8 cifre della mantissa).

Esempio 2

Sia x = 0.56543451 × 106 ed y = 0.21554623 × 10−4.


fl(x) = 0.56543451 × 106 → 0.5654345100000000 × 106 +fl(y) = 0.21554623 × 10−4 → 0.0000000000215546 × 106

fl(z) = 0.56543451 × 106 ← 0.5654345100215546 × 106

In questo esempio, poiche la grandezza dei due operandi e abbastanzadiversa (sono distanti tra loro) il trasferimento di fl(y) nell’accumulatoreproduce un errore (si perdono due cifre). Pertanto la somma calcolatanell’accumulatore non sara esatta (ovvero non verra calcolato esatta-mente fl(x) + fl(y)). Inoltre, restituendo il risultato in memoria (poichedobbiamo conservare solo t = 8 cifre della mantissa) si ottiene fl(z) =fl(x), ovvero si realizza la relazione anomala. Infatti |fl(y)| / |fl(x)| edell’ordine di 10−10 e quindi minore di eps.

Esempio 3

Sia x = 1.0 ed y = 0.5 × 10−7.


fl(x) = 0.10000000 × 101 → 0.1000000000000000 × 101 +fl(y) = 0.50000000 × 10−7 → 0.0000000050000000 × 101

fl(z) = 0.10000001 × 101 ← 0.1000000050000000 × 101

In questo esempio abbiamo x = fl(x) = 1 e y = fl(y) = eps. Si vede chela somma viene eseguita correttamente negli accumulatori e, nella resti-


tuzione del risultato in memoria, a causa dell’arrotondamento si ottienefl(z) = 1.0000001. Se avessimo utilizzato per y il valore 0.4 × 10−7 sisarebbe realizzata la relazione anomala. Dunque eps e effettivamente ilpiu piccolo valore per il quale fl(1 + eps) > 1.

Esempio 4

Sia x = 0.5654328749876 ed y = −0.5654328510104.


fl(x) = 0.56543287 × 100 → 0.5654328700000000 × 100 +fl(y) = −0.56543285 × 100 → −0.5654328500000000 × 100

fl(z) = 0.20000000 × 10−7 ← 0.0000000200000000 × 100

In questo esempio, abbiamo espressamente inserito del valori x 6= fl(x) edy 6= fl(y), per enfatizzare quanto accade. L’addizione negli accumulatoriviene eseguita in modo esatto (ovvero conservando esattamente i valorifl(x) ed fl(y)). Tuttavia, nella restituzione del risultato in memoria, glizeri che seguono la cifra 2 non hanno alcun significato! Essi provengonosolo dal fatto che negli accumulatori abbiamo aggiunto degli zeri alladestra della mantissa. Gli zeri del risultato non hanno significato comenon ne avrebbe avuto qualsiasi altra cifra decimale che avessimo messoal loro posto. Infatti, la somma x + y darebbe 0.239772 × 10−7 e quindil’errore relativo (approssimato a 3 cifre decimali) e εr(z) = 0.166, chee elevato. Nei calcoli successivi, utilizzando fl(z) (anziche z) e come selavorassimo con solo 1 cifra decimale esatta. E l’errore di cancellazione.

Regola per l’errore di cancellazione. Siano mx ed my le mantisse didue numeri x ed y aventi lo stesso segno (rispettivamente segno opposto)che hanno coincidenti le prime r cifre. La differenza (rispettivamente lasomma) tra questi due numeri ha solamente le prime (t − r) cifre delrisultato che possono considerarsi significative (t rappresenta il numerodi cifre significative che possono essere rappresentate in memoria). Tuttele altre cifre non hanno alcun significato.

Diamo ora alcuni esempi utilizzando la semplice e la doppia precisioneper mettere in luce come i calcoli in semplice precisione siano affetti daerrori anche rilevanti. Questi risultati sono stati ottenuti su di un com-puter, mentre gli esempi precedenti, svolti a mano, servivano unicamentea mostrare come vengono effettuate le operazioni.


semplice precisionex y x ª y x ⊕ y

123456789.0 123456788.0 8.0 246913568.0123456789.0 123456790.0 0.0 246913584.00.56543451×106 0.21554623×10−4 565434.5 565434.51.0 0.5 × 10−6 0.999999523 1.000000480.5654328749876 0.5654328510104 0.0 1.130865690.3333333333 0.1111111111 0.222222239 0.444444448

doppia precisionex y x ª y x ⊕ y

123456789.0 123456788.0 1.0 246913577.0123456789.0 123456790.0 −1.0 246913579.00.56543451×106 0.21554623×10−4 565434.509978 565434.5100221.0 0.5 × 10−6 0.9999995 1.00000050.5654328749876 0.5654328510104 0.239772000032×10−7 1.1308657260.3333333333 0.1111111111 0.2222222222 0.4444444444

2.4.3 Esempi sull’errore di cancellazione

Talvolta e possibile modificare le proprie espressioni in modo da caute-larsi nei confronti di un possibile errore di cancellazione. Semplici trasfor-mazioni di tipo algebrico o modifiche nell’algoritmo possono aiutarci adevitare tale errore.Vediamo alcuni esempi.

Calcolo delle radici di un polinomio di secondo grado

A tutti e noto che le radici del polinomio ax2 + bx + c = 0 sono date da

x1 =−b −

√b2 − 4ac

2a

x2 =−b +

√b2 − 4ac

2a.

(2.3)

Se |4ac| << b2 una delle due soluzioni sara mal calcolata, in quanto√b2 − 4ac ' |b| e quindi si verifichera un errore di cancellazione a causa

della differenza di due numeri quasi uguali.Ad esempio, se a = 10−3, b = 0.8 et c = −1.2 × 10−5, le soluzioni esattesono

x1 = −800

x2 = 1.5 × 10−5.


La prima soluzione, fl(x1), su di un computer, e ben calcolata mentreper la seconda si ha fl(x2) = 2.980232 × 10−5, con εr(x2) ' 0.9868. Perevitare tale errore, utilizziamo il fatto che, data una soluzione x1 dellanostra equazione, la seconda soluzione puo essere calcolata come

x2 =c

ax1

. (2.4)

Pertanto, sapendo che la soluzione ben calcolata e quella che evita l’e-ventuale errore di cancellazione, ovvero e sempre data da

x1 =−b − sign(b)

√b2 − 4ac

2a(2.5)

dove sign(b) rappresenta il segno del numero b, anziche utilizzare le for-mule (2.3), sara meglio usare le formule (2.4) e (2.5).Vediamo nella figura 2.3 i risultati ottenuti per la soluzione x2 (quellache puo essere mal calcolata) con le formule (2.3) (linea continua) e quelliottenuti con le formule (2.4, 2.5) (linea tratteggiata) nel caso in cui siabbia a = 10−3, b = 0.8 et c = −(1+ k× 0.05)× 10−5 per k = 0, . . . , 100.

0

1

2

3

4

5

6

7

8

9x10-5

-6 -5.5 -5 -4.5 -4 -3.5 -3 -2.5 -2 -1.5 -1

x10-5valore di c

x

_2

Figura 2.3: Calcolo degli zeri di ax2 + bx + c


Formule alternative

Vediamo ora alcuni esempi di espressioni che potenzialmente potrebberoessere affette dall’errore di cancellazione. Semplici modifiche di tipo alge-brico, ci permettono di considerare delle espressioni equivalenti che nonpresentano tale problema.

Esempio 1

Sia |δ| << |x|.√

x + δ −√

x =δ√

x + δ +√

x

Esempio 2

Sia |δ| << |x|.

cos(x + δ) − cos(x) = −2 sinδ

2sin

(

x +δ

2

)

Esempio 3

Sia |x| grande.1

x− 1

x + 1=

1

x(x + 1)

2.5 Stabilita 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 stabilita numerica di un algoritmo. Sono dueconcetti 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 (dettaperturbazione) di tale modello, porti ad una soluzione molto lontana daquella del problema non perturbato.Diamo un esempio molto semplice:

Sia dato il seguente sistema lineare a due incognite

{2.1x + 3.5y = 8.04.19x + 7.0y = 15.0

2.5. Stabilita e condizionamento 37

che ammette per soluzioni

x = 100.0y = −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 relativodovuto a tale perturbazione e all’incirca 4.77 × 10−4.Se risolviamo ora il sistema perturbato otteniamo come soluzioni

x = 125.0y = −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 utilizzatoma dal problema in se stesso (trattandosi geometricamente di due rettequasi parallele, e naturale che una piccola variazione di inclinazione diuna delle due rette, provochi uno spostamento notevole del punto diintersezione). Tenendo presente che, utilizzando un computer, abbiamovisto che anche solo a causa dell’errore di assegnazione non si lavora coni dati esatti, ma con una loro approssimazione, la risoluzione del sistemaci portera 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 piccoleperturbazioni (errori relativi) sui dati di ingresso, corrispondono pertur-bazioni (errori relativi) sui risultati piccole (ovvero dello stesso ordine digrandezza).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 edil risultato r. Supponiamo che una variazione ∆d dei dati provochi unavariazione ∆r del risultato. E possibile definire il numero di condiziona-mento di un problema P (indicato con cond(P)) come una limitazionesuperiore del fattore di amplificazione degli errori relativi, ovvero

‖∆r‖‖r‖ ≤ cond(P)

‖∆d‖‖d‖ ,


dove con ‖ · ‖ indichiamo una funzione (norma) che misura le entitacoinvolte (si veda l’appendice, sezione A.7).

Un altro esempio di problema mal condizionato e dato dalla ricercadelle radici di un polinomio quando vi sono radici α grandi e la derivatadel polinomio calcolata in tali α e piccola, oppure quando vi sono dueradici molto vicine oppure multiple.Un esempio classico di tale problema e dato dal Polinomio di WilkinsonP20 = (x + 1)(x + 2) · · · (x + 20) = x20 + 210x19 + · · ·+ 20! . Pur avendoradici ben separate (αi = −i, i = 1, . . . , 20), si riescono a calcolare benele prime 15, ma non le ultime 5.

Vediamo ora di definire il secondo concetto. Per risolvere un certoproblema noi usiamo un certo algoritmo ed il programma corrispondentesul computer. Vi saranno quindi necessariamente degli errori dovutiall’aritmetica del computer che potranno propagarsi in modo piu o menorilevante sui risultati. Quindi un problema puo essere per natura bencondizionato, ma l’algoritmo utilizzato per risolverlo puo essere numeri-camente instabile. In tal caso, e necessario usare (o trovare) un algoritmostabile.

Un esempio di algoritmo instabile e di un algoritmo alternativo stabile(in quanto evita gli eventuali problemi di cancellazione) lo abbiamo vistonella sezione 2.4.3.

Diamo una definizione di stabilita numerica di un algoritmo:

Stabilita: Un algoritmo si dice stabile se a piccole perturbazioni (errorirelativi) sui dati, corrispondono perturbazioni (errori relativi) sui risultatidello stesso ordine di grandezza.Un algoritmo si dice instabile se gli errori piccoli iniziali (o presenti ad uncerto momento) anziche compensarsi mediamente (o mantenersi limitati)tendono a crescere in modo incontrollato sino a degradare completamenteil risultato finale.

Vediamo un esempio classico di due algoritmi, che risolvono lo stessoproblema, l’uno stabile e l’altro instabile.

Sia da calcolare l’integrale

In =1

e

∫ 1

0

xnex dx con n ≥ 0

2.5. Stabilita e condizionamento 39

Integrando per parti si ha

In =1

e

(

[xnex]10 − n

∫ 1

0

xn−1ex dx

)

= 1 − n In−1

Poiche I0 =1

e

∫ 1

0

ex dx =e − 1

e, si ha I1 =

1

eed il seguente schema

ricorsivo {

I1 =1

eIi = 1 − i Ii−1, i = 2, . . . , n

E possibile dimostrare che, ∀i, 0 < Ii <

∫ 1

0

xi dx =1

i + 1. Pertanto

limi→∞

Ii = 0 ed i valori devono essere decrescenti in valore assoluto.

Dimostriamo ora che tale algoritmo per il calcolo dell’integrale In einstabile.

Indichiamo con Ii il valore esatto e con I′i il valore approssimato alpasso i-esimo.Si ha I′i = Ii + εi, con |εi| uguale all’errore assoluto al passo i. Analoga-mente I′i−1 = Ii−1 + εi−1 e quindi, dalla formula ricorsiva I′i = 1 − i I′i−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 alpasso (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 contodegli errori di aritmetica, εn aumenta 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 piu visibile l’instabilita, checomunque si presenta anche in doppia precisione). Si ha I1 = e−1 eI′1 = 3.6787945 × 10−1. Utilizzando lo schema ricorsivo in avanti, otte-niamo i risultati della seguente tabella. Essi mostrano come il valore I′ntenda ad aumentare rapidamente, anziche convergere verso lo zero, otte-nendo per I′21 un numero dell’ordine di 1011. In doppia precisione si haI′21 = −2.201076724843952 × 103.


n I′n n I′n2 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 poneIN uguale ad un valore arbitrario qualsiasi, oppure a zero (commettendocertamente 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 I′′i = Ii + εi, e I′′i−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’erroreper l’indice i.Supponendo di aver commesso (assegnando il valore di partenza IN = a)un errore εN = I′′N − 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

2.6. Analisi degli errori 41

Quindi il fattoriale di N al denominatore abbatte rapidamente l’erroreiniziale εN , che puo anche essere elevato.

Sia ad esempio N = 13 ed I13 = 1000. Si ottiene

i I′′i i I′′i12 −7.6846153 × 101 6 1.2668674 × 10−1

11 6.4871793 × 100 5 1.4555222 × 10−1

10 −4.9883449 × 10−1 4 1.7088956 × 10−1

9 1.4988345 × 10−1 3 2.0727761 × 10−1

8 9.4457395 × 10−2 2 2.6424080 × 10−1

7 1.1319283 × 10−1 1 3.6787960 × 10−1

con |I′1 − I′′1| = 1.4901161× 10−7 (I′1 e l’approssimazione del valore esattoI1 = e−1). Come si vede, pur partendo da un valore iniziale completa-mente arbitrario, l’integrale I′′1 (approssimazione di I1) risulta essere ac-curato per almeno 6 cifre significative decimali. Qualora l’errore |I′1 − I′′1|fosse stato troppo elevato, ovvero maggiore di una certa tolleranza toll

prefissata, si aumenta il valore di N e si ripete il procedimento sino adottenere la precisione desiderata.

Naturalmente i primi integrali calcolati, rispetto agli integrali esatti,saranno affetti da un errore non trascurabile. Nella tabella precedente sivede, ad esempio, che l’effetto di diminuzione dell’errore inizia solamentenel calcolo di I′′8. Ripetiamo il procedimento prendendo N = 20 ed ancoraI20 = 1000 e mostrando solo gli integrali a partire da I′′12.

i I′′i i I′′i12 7.1773447 × 10−2 6 1.2680236 × 10−1

11 7.7352211 × 10−2 5 1.4553294 × 10−1

10 8.3877072 × 10−2 4 1.7089342 × 10−1

9 9.1612294 × 10−2 3 2.0727664 × 10−1

8 1.0093196 × 10−1 2 2.6424113 × 10−1

7 1.1238351 × 10−1 1 3.6787945 × 10−1

In tal caso, I′′1 coincide esattamente con I′1.

2.6 Analisi degli errori

Abbiamo visto quante problematiche possono essere presenti quandovogliamo risolvere un problema matematico utilizzando un computer


(condizionamento, errori di assegnazione, dovuti alle operazioni macchina,stabilita dell’algoritmo, . . . ). A tutte queste si aggiunge anche il fattoche, per produrre il modello numerico di un problema matematico, siamotalvolta obbligati a ricorrere a metodi numerici che forniscono solo unasoluzione approssimata del problema matematico (ad esempio nell’inte-grazione finita).

Quando possibile, puo essere interessante studiare la propagazionedegli errori. E quanto in effetti e stato fatto nell’esempio dell’integraledella sezione precedente. Non intendiamo approfondire tale argomento,ma molti semplici esempi possono essere trovati nei vari testi della let-teratura.

Quando si studia come l’errore si propaga per effetto dell’errore diassegnazione e delle successive operazioni, si parla di analisi dell’errore inavanti. Nei casi reali tale analisi risulta difficilmente realizzabile (a causasoprattutto del numero importante delle operazioni che vengono svolte).Inoltre si effettuano delle semplificazioni dei calcoli che conducono spessoa delle stime poco accurate dell’errore finale.

Una tecnica alternativa, molto usata, e quella dell’analisi dell’erroreall’indietro. In tale caso si considera la soluzione approssimata ottenuta,come se fosse soluzione esatta di un problema P che sia modificatorispetto al problema iniziale P. Poi si studia quanto sia grande la mo-difica del problema iniziale al fine di ottenere tale soluzione. Il risultatofinale ottenuto sara accettabile solo se esso e soluzione esatta di un pro-blema modificato che possa essere considerato prossimo a quello originale.In termini di errori, si considera quale dovrebbe essere l’errore sui datiiniziali originari per produrre tale risultato finale.

Terminiamo con alcune definizioni che riguardano gli errori:

Sia ε0 l’errore iniziale, ed εn l’errore dopo n passi di un certo algoritmo.La crescita dell’errore e detta

lineare

se εn ' n ε0

esponenziale

se εn ' cn ε0

Se c > 1 l’errore cresce (εn → ∞, per n → ∞)Se 0 < c < 1 l’errore descresce (εn → 0, per n → ∞)

2.7. Esempi 43

2.7 Esempi

In questa sezione vogliamo fornire alcuni esempi tratti dalla letteraturaper illustrare maggiormente le varie problematiche, soprattutto quellerelative alla precisione finita dell’aritmetica del computer.

2.7.1 Esempio 1

Spesso si ritiene che se un risultato calcolato con precisioni diverse restainvariato, e obbligatoriamente ben calcolato. Questo esempio mostra chetale convinzione e errata.Sia da calcolare il valore di

333.75b6 + a2(11a2b2 − b6 − 121b4 − 2) + 5.5b8 +a

2b. (2.6)

Per a2 − 1 = 11b2/2 l’espressione vale analiticamente −2 + a/2b.Consideriamo i valori a = 77617.0 e b = 33096.0 tali che a2 −1 = 11b2/2.Calcolando numericamente l’espressione (2.6) si ottiene

Semplice precisione Doppia precisione Precisione estesa

0.5764607×1018 0.5764607523034235×1018 0.57646075230342350345×1018

Tuttavia il risultato con tali valori dovrebbe essere

−2 + a/2b = −0.82739605994682 . . .

I risultati in tale problema dipendono fortemente anche dal computer sucui si lavora e dal modo in cui si programma la formula. Infatti, su di unaltro computer si e ottenuto circa −9.87 × 1029 in semplice precisione, ecirca −1.18 × 1021 in doppia precisione!

2.7.2 Esempio 2

Consideriamo il polinomio

x3 − 111x2 + 1130x − 3000.

Le sue radici sono 5, 6 e 100. E possibile dimostrare che la successione

xn+1 = 111 − 1130

xn

+3000

xnxn−1

, n = 0, 1, . . .

converge a 6 se si prendono come valori iniziali

x−1 =11

2= 5.5 e x0 =

61

11= 5.54


0 5 10 15 20 25−600

−500

−400

−300

−200

−100

0

100

200

n

xn

Figura 2.4: xn+1 = 111 − 1130

xn

+3000

xnxn−1

In figura 2.4 si vede invece che, utilizzando un computer, la successioneconverge al valore 100 anziche a 6. Questo fenomeno sembra prodursi sututti i computer. Infatti, ad esempio, se si prendono come valori iniziali

x−1 = 2.0 e x0 = −4.0

facendo i calcoli con 100 cifre decimali si trova

x89 = 99.999804031654181616554 . . .

mentre il valore esatto dovrebbe essere 6.0000000996842706 . . ..

2.7.3 Esempio 3

Consideriamo la seguente successione che converge al valore x = 1

x0 = 1.510005072136258

xn+1 =3x4

n − 20x3n + 35x2

n − 24

4x3n − 30x2

n + 70xn − 50, n = 0, 1, . . .

A seconda del numero di cifre decimali k utilizzate nei calcoli, si otten-gono risultati molto diversi.

2.7. Esempi 45

k Valore di convergenza

10 4.00000003312 1.0000000000014 3.000000000000016 4.00000000000003318 1.00000000000000000

2.7.4 Esempio 4

Si consideri il seguente schema iterativo

x0 assegnato

y0 =√

1 − x20

t0 = x20 + y2

0 = 1

xn+1 = 2xnyn

yn+1 = x2n − y2

n

tn+1 = x2n+1 + y2

n+1

per n = 0, 1, . . .

Matematicamente si ha tn+1 = (x2n + y2

n)2 = t2n = 1 (per induzione,essendo t0 = 1).

In figura 2.5, si sono visualizzate le curve ottenute su di un computer,nei due casi:

x0 = 0.6 tn linea continuax0 = 0.8 tn linea tratteggiata

Come si vede, dopo essersi mantenuto uguale a 1, nel primo caso tn cresce,mentre nel secondo tende a zero.

2.7.5 Esempio 5

Consideriamo la successione {xn} calcolata come

xn+1 = 2.25 xn − 0.5 xn−1, n = 2, 3, . . . (2.7)

con x1 e x2 assegnati. La teoria delle equazioni alle differenze lineariomogenee, a coefficienti costanti, ci dice che

xn = a 0.25n + b 2n, n = 1, 2, . . . (2.8)

dove a e b sono delle costanti i cui valori sono determinati da x1 e x2.Se noi prendiamo x1 = 1/3 e x2 = 1/12, si ha a = 4/3 et b = 0. Di


0.6

0.8

1

1.2

1.4

1.6

1.8

2

2.2

2.4

0 5 10 15 20 25

n

t_n

Figura 2.5: tn+1 = (x2n + y2

n)2 = t2n

10-12

10-9

10-6

10-3

100

103

106

109

0 10 20 30 40 50 60 70

Figura 2.6: xn+1 = 2.25xn − 0.5xn−1

2.8. Algoritmi 47

conseguenza da (2.8) si ha xn = 41−n/3 e tale quantita tende a zeroquando n tende verso l’infinito.I risultati ottenuti su computer, utilizzando la formula (2.7) sono visua-lizzati in figura 2.6.

Cerchiamo di capire cosa e accaduto. A causa degli errori di assegna-zione iniziali su x1 e x2, il valore b implicitamente definito da (2.7) non eesattamente nullo, ma solo molto piccolo. Nella prima parte della curva,l’apporto del termine b 2n e trascurabile, ma diviene preponderante nellaparte destra della curva.

2.8 Algoritmi

2.8.1 Stima di eps

Un semplice algoritmo (dovuto a Cleve Moler) per la stima del valoreeps e il seguente:

x = 4.0/3.0y = x − 1.0z = y + y + yeps = |z − 1.0|

2.8.2 Calcolo della base

Abbiamo gia detto che non tutti i computer lavorano con normalizzazionenella base 2. Se si lavora con computer che utilizzano basi diverse, none inusuale che i risultati di uno stesso programma risultino essere diversi(anche di molto) su computer differenti.Un semplice algoritmo per il calcolo della base utilizzata da un computere il seguente:

a = 1.0b = 1.0while ((a + 1.0) − a) − 1.0 = 0.0 do

a = 2.0 × aend while

while ((a + b) − a) − b 6= 0.0 do

b = b + 1.0end while

print b

Il valore di b rappresenta la base interna utilizzata dal computer.


2.8.3 Equazione di secondo grado

Si vuole un algoritmo che permetta di risolvere un’equazione di secondogrado, i cui coefficienti reali sono indicati con a, b e c, effettuando tuttii possibili controlli. Nel caso di due soluzioni reali distinte, l’algoritmoutilizza la formula usuale. Come si e detto (vedi sezione 2.4.3), perevitare eventuali errori di cancellazione, e preferibile utilizzare le formulealternative. L’algoritmo proposto puo essere facilmente modificato in talsenso come esercizio.

[x1, x2] = Eq grado2 (a, b, c)

if a = 0 then

if b = 0 then

if c = 0 then

print Equazione indeterminataelse

print Equazione impossibileend if

else

x1 = −c/bprint Equazione di grado 1 (unica soluzione x1)

end if

else

∆ = b2 − 4acif ∆ < 0 then

print Nessuna soluzione realeelse if ∆ = 0 then

print Due soluzioni coincidenti (x1 = x2)x1 = −b/(2a)x2 = x1

else

print Due soluzioni distinte (x1 6= x2)

x1 = (−b −√

∆)/(2a)

x2 = (−b +√

∆)/(2a)end if

end if

2.9. Esercizi 49

2.9 Esercizi

Esercizio 2.1 Si scriva un algoritmo ed il relativo programma che, datiamin e amax, calcoli il primo numero positivo a ∈ F che sia maggiore diamin, ed il primo numero positivo a ∈ F che sia minore di amax, sia insemplice che in doppia precisione..

Esercizio 2.2 Si deve eseguire la somma di n numeri reali x1, . . . xn dicui non si conoscono a priori ne i segni ne l’ordine di grandezza. Se silavorasse con precisione infinita un possibile algoritmo sarebbe

for i = 1, . . . , nread xi

end for

somma = x1

for i = 2, . . . , nsomma = somma + xi

end for

print somma

Si scriva un algoritmo che esegua la somma in modo da evitare i possibilierrori dovuti all’aritmetica del computer. Si realizzi poi il programma checalcola la somma nei due modi, e si confrontino i risultati.

Esercizio 2.3 Si scriva un algoritmo per il calcolo del valore reale dellaseguente espressione (algebricamente uguale ad 1 per ogni valore di n),senza effettuare alcuna semplificazione:

(√

n

n − 1× n − 1

n − 2× · · · × n − (n − 2)

n − (n − 1)× n − (n − 1)

1

)2

× n − 1

n× n − 2

n − 1× · · · × n − (n − 1)

n − (n − 2)× 1

n − (n − 1).

Si realizzi poi un programma che effettui tale calcolo per n = 2, . . . , 100,sia in semplice che in doppia precisione, calcolando anche, per ogni n,l’errore assoluto, l’errore relativo ed il numero di cifre significative esatte.Si analizzino poi i risultati trovati e si dica quali di essi sono affetti daerrore dovuto all’aritmetica del computer e quali sono le possibili ragioni.


Esercizio 2.4 Si realizzi un programma che, utilizzando due funzionicorrispondenti ai due algoritmi di calcolo (diretto ed Horner), calcoli ilvalore di un polinomio P (x) in un punto x (si veda la sezione 1.2.3).Si confrontino i due risultati ottenuti al variare di x ed al variare deicoefficienti del polinomio P (x).

Esercizio 2.5 Modificando opportunamente l’algoritmo proposto nellasezione 2.8.3, si introducano le formule stabili per la determinazione dellesoluzioni reali di un’equazione di secondo grado a coefficienti reali (vedisezione 2.4.3). Si scrivano poi i relativi programmi e si ritrovino i risul-tati della Figura 2.3.

Esercizio 2.6 Prendendo spunto dall’algoritmo proposto nella sezione2.8.3, si scriva un algoritmo per il calcolo delle soluzioni (reali e/o com-plesse) di un’equazione di secondo grado a coefficienti reali.

Capitolo 1 I NUMERI 1.1 Basi di numerazionemichela/12.pdf · 2 Capitolo 1. I numeri b cifre 2 0 1 8...

Documents

Transcript of Capitolo 1 I NUMERI 1.1 Basi di numerazionemichela/12.pdf · 2 Capitolo 1. I numeri b cifre 2 0 1 8...