Fondamenti della matematica numerica

C’è da notare il fatto che la lunghezza finita della locazione di memoria implica l’esistenza di un massimo (e

di un minimo) intero rappresentabile. Per cui x∈Z è rappresentabile se e solo se |x|≤imax. Inoltre tentativo

di memorizzazione di un |x|>imax produce una situazione eccezionale di overflow. Questo fenomeno si

verifica quando il risultato di un’operazione aritmetica esce dall’intervallo rappresentabile con i bit

disponibili, ne consegue che il numero non può essere rappresentato nel formato scelto.

Il sistema dei numeri floating point Rappresentazione di reale

- numero

un

Immagina di dover risolvere al computer un problema di calcolo numerico, ad esempio simulare il moto

di un pianeta intorno al Sole o trovare le radici di un polinomio di alto grado. In questi casi, i numeri che

compaiono possono spaziare da valori enormemente grandi (distanze astronomiche) a cifre infinitesimali

(voci di una matrice quasi singolare). Senza un meccanismo che sappia “allargare e restringere” la scala

dei valori, ci ritroveremmo con trasbordamenti o con zeri inattesi, vanificando ogni accuratezza. Ed è qui

che entra in gioco il sistema di numeri in virgola mobile (floating‑point). A differenza della virgola fissa —

dove si decide in partenza quanti bit riservare alla parte intera e quanti alla parte frazionaria — con la

virgola mobile ogni valore viene scritto in modo simile alla notazione scientifica: esiste una mantissa, che

porta le cifre significative, e un esponente, che sposta la “virgola” (in binario) verso l’alto o verso il basso

a seconda delle necessità.

Tipicamente sui calcolatori sono disponibili due formati per la rappresentazione floating-point dei numeri: la

singola e la doppia precisione. Nel caso di rappresentazione binaria, questi formati corrispondono nella

versione standard alla rappresentazione con N = 32 bits (singola precisione) e con N = 64 bits (doppia

precisione)

Errore di arrotondamento - errore round off

Si immagina di avere due numeri decimali, ad esempio 0,1 e 0,2, e di volerli sommare. In aritmetica esatta

il risultato è 0,3, ma in virgola mobile il processo non è così immediato: 0,1 e 0,2 non si rappresentano

esattamente in binario, così il calcolatore utilizza approssimazioni. Il numero “reale” della somma, quindi,

non corrisponde mai esattamente a un pattern di bit disponibile, e bisogna arrotondare al bit più vicino:

questo scarto tra il valore ideale e quello effettivamente memorizzato è l’errore di arrotondamento, o

round‑off error. Pertanto quest’ultimo rappresenta la differenza tra il valore reale e la sua rappresentazione

in virgola mobile. Per esempio, il numero 1/3 ≈ 0,333… in base 10 (e il corrispondente periodo infinito in

binario) non può essere memorizzato con precisione finita: il processore sceglie la sequenza di bit più

vicina e “arrotonda” al valore rappresentabile, generando un piccolo scarto. L’approssimazione è dovuta

essenzialmente al fatto che la memoria di un calcolatore è finita e non è possibile rappresentare con

esattezza tutti i numeri reali.

Propagazione dell’errore

Quando si eseguono operazioni aritmetiche successive—somme, prodotti, divisioni, radici…—ciascun

passaggio introduce un nuovo round‑off error. Sebbene ogni singolo errore sia minuscolo, l’accumulo e la

propagazione di milioni di tali scarti possono dare luogo a un errore complessivo significativo. Inoltre ogni

algoritmo numerico include un’analisi dell’errore. L’analisi della propagazione dell’errore di roundoff riveste

un ruolo fondamentale nella progettazione e sviluppo di un algoritmo. Per valutare gli effetti di tale errore

sulla soluzione calcolata da un algoritmo (eseguito in aritmetica a precisione finita) sono disponibili due

metodi di analisi della propagazione dell’errore di roundoff:

• la forward error analysis (FEA)

• la backward error analysis (BEA).

Stabilità di un algoritmo

Un algoritmo numerico si definisce stabile quando gli effetti degli errori di arrotondamento (round‑off) e degli

eventuali errori nei dati di input non si amplificano in modo sproporzionato, ma rimangono dello stesso

ordine di grandezza sul risultato finale. In altre parole, anche se ogni operazione in virgola mobile introduce

un piccolo scarto, un algoritmo stabile garantisce che la somma di tutti questi scarti non cresca in modo

incontrollato man mano che procediamo nei calcoli. Al contrario, un algoritmo è instabile se, pur partendo da

dati di input con errori molto piccoli, le operazioni successive ne moltiplicano la portata, producendo un

“effetto valanga” di arrotondamenti: l’errore sul risultato finale diventa di un ordine di grandezza (o più)

maggiore rispetto a quello iniziale. In pratica significa che piccole incertezze sui dati portano a grandi

imprecisioni nel risultato, rendendo l’algoritmo inaffidabile.

U)

(B t

IF L

, ,

,

a

Epsilon macchina

L’epsilon macchina rappresenta la distanza fra il numero 1 ed il successivo numero floating-point, ed è

dunque il più piccolo numero di F per cui 1 + ϵM > 1. In parole povere esso è il più piccolo “passo” che

la macchina riesce a percepire attorno al numero 1. Se provi a sommare a 1 un numero più piccolo di

questo passo, il risultato rimarrà 1: succede perché quel piccolo scarto non rientra nella risoluzione dei

bit disponibili. Inoltre l’epsilon macchina funge da misura per l’accuratezza nei calcoli poiché se serve

un’accuratezza di 10⁻¹², la single precision (ε≈10⁻⁷) è evidentemente troppo rozza e conviene passare

alla double (ε≈10⁻¹⁶) o persino a precisioni più elevate. & Direttamente

Collegati

Massima accuratezza relativa V

la massima accuratezza relativa in floating‑point è il metro con cui misuriamo il confine tra ciò che un

calcolatore potrebbe teoricamente fare e ciò che riuscirà effettivamente a garantire. Per cui essa è

definita come a differenza tra il valore reale e quello approssimato, divisa per il valore reale. gli algoritmi

numerici cercano di ridurre al minimo questa quantità durante le operazioni aritmetiche.

NORME VETTORIALI E MATRICIALI

Spesso in calcolo numerico per quantificare errori o calcolare delle distanze è necessario misurare la

grandezza di vettori e matrici. Per tal motivo si ricorre all’utilizzo di concetti quali norme vettoriali e norme

matriciali, che rappresentano funzioni le quali a partire da un determinato spazio (vettoriale o matriciale)

associano numeri reali.

1.1 Norma vettoriale n M N

→R+

Una norma vettoriale su R è una funzione R che associa ad ogni vettore x R , di

∥·∥: ∪{0}, ∈

componenti xi , i= 1,...,n, uno scalare, in modo che valgano le seguenti proprietà:

M

• per ogni x ;

∥x∥≥0 ∈R

1.

• 0 x = 0 (se non vale tale proprietà si parla di seminorma);

∥x∥=

2 . M

• |α|∥x∥ e (Proprietà di omogeneità);

∥αx∥= ∀α∈R ∀x ∈R

3.

• + y triangolare).

∥x ∥≤∥x∥+ ∥y ∥(disuguaglianza

4 .

Segue che: ∥x−y ∥≥|∥x∥−∥y ∥|.

In R si definiscono le seguenti norme:

En Xi ATA

Il XII2 NORMA EUCLIDEA

· >

=

= /

IXi NORMA INFINITO

· m assocuto

valore

= > il max

misura

, tra le di

componenti vettore

un

NORMA 11 Allr

Le

> = misurala sommadi delle

valori componenti

assoluti

, vettore

zel

Si dimostra che queste funzioni godono delle proprietà delle norme (ossia sono norme).

M

n

La coppia (R ,∥ · si dice spazio normato. Nel caso in cui una applicazione |·| da R in R verifichi le

∥)

proprietà 1, 3 e 4 diremo tale applicazione una seminorma. Chiameremo infine vettore unitario un vettore

con norma pari ad uno.

Per la norma euclidea vale la seguente proprietà:

IRM

=

Inoltre ogni norma è caratterizzata da una rappresentazione geometrica che può essere

visualizzata come una sfera unitaria:

Sè un insieme convesso, ossia se x,y anche αx + (1−α)y per α∈(0,1). Infatti

∈S, ∈S,

+ (1−α)y (1−α)∥y

∥αx ∥≤α∥x∥+ ∥≤1.

Inoltre si dice che la norma è una funzione strettamente convessa se + y x = αy

∥x ∥= ∥x∥+ ∥y ∥

La norma euclidea è una funzione strettamente convessa, la norma 1 e ∞ non lo sono (si veda norma 1

T

T

T

con x = (0,1) , y = (1,0) , x + y = (1,1) ). La norma è una funzione uniformemente continua delle sue

componenti.

Convergenza di una successione di vettori

-

M

EIR componenti del rispettivi

bettor

spe

↑ e

*

1.2 Norma matriciale

Poiché una matrice m ×n si può pensare come un vettore di m·n componenti (ordinando gli elementi della

matrice per righe o per colonne), segue che una norma matriciale generalizzata è un’applicaIone ∥·∥:

nxm →R+

R tale che:

∪{0},

Di conseguenza, una norma matriciale generalizzata è una funzione uniformemente continua delle

sue componenti, tutte le norme matriciali generalizzate sono equivalenti e vale che

Una norma matriciale generalizzata è una norma matriciale se vale la seguente proprietà submoltiplicativa

o proprietà di consistenza:

ove A e B sono matrici moltiplicabili.

Norma naturale

Siamo interessati a introdurre norme matriciali indotte da una norma vettoriale Una norma di questo

∥·∥V.

tipo è detta norma naturale o norma indotta dalla norma vettoriale. Essa viene definita come la più piccola

costante C per cui vale la condizione:

Pertanto la definizione di norma naturale è la seguente:

Lo scalare non cambia se si sostituisce x con un suo multiplo. Allora si può prendere un versore

y= x/∥x∥V , dove y ha norma unitaria. Tenendo conto che S= {y |∥y = 1}è un compatto e la

∥V

norma è funzione uniformemente continua, l’estremo superiore è un massimo:

Si dimostra che è una norma matriciale, che è compatibile con e che tale norma

∥A∥N ∥·∥V

(per come è definita) è la più piccola norma matriciale compatibile con la norma ∥·∥V.

Pertanto il significato della norma naturale risiede nel fatto che le applicazioni

lineari che trasformano dati in risultati sono lineari e dunque associabili a una

matrice. La esprime la massima pe