DISPENSE
CALCOLO NUMERICO
1
INDICE
1. Aritmetica di macchina 3
1.1 Rappresentazione dei numeri 3
1.2 Numeri di macchina 3
1.3 Errori 5
1.4 Operazioni di macchina 6
1.5 Cancellazione numerica 6
1.6 Condizionamento di un problema numerico 7
1.7 Stabilità di un algoritmo 7
2. Approssimazione di funzioni e dati 8
2.1 Interpolazione 8
2.2 Rappresentazione monomiale del polinomio di interpolazione 8
2.3 Rappresentazione di Lagrange del polinomio di interpolazione 8
2.4 Convergenza del polinomio di interpolazione 9
2.5 Nodi di Chebyshev-Lobatto 10
2.6 Funzioni polinomiali a tratti: spline 10
3. Sistemi lineari 13
3.1 Richiami di Algebra Lineare 13
3.2 Condizionamento di un sistema lineare 15
3.3 Metodi numerici 16
3.4 Fattorizzazione PA=LU e applicazioni 18
3.5 Fattorizzazione di Choleski e applicazioni 19
3.6 Fattorizzazione QR e applicazioni 20
4. Autovalori e valori singolari di matrici 22
4.1 Richiami di Algebra Lineare 22
4.2 Definizioni e metodi 22
4.3 Condizionamento del calcolo degli autovalori 23
4.4 Metodi numerici 24
4.5 Valori singolari e decomposizione SVD 25
2 CAPITOLO 1
ARITMETICA DI MACCHINA
Il calcolo numerico è una disciplina della matematica che propone e analizza metodi che consentono di
ottenere una soluzione numerica di problemi matematici onerosi.
Per ottenere la soluzione numerica si utilizzano algoritmi eseguibili da un calcolatore.
In seguito si analizzeranno metodi di risoluzione di Algebra Lineare, in particolare gli algoritmi saranno basati
sul linguaggio Matlab.
1.1 Rappresentazione dei numeri
1.1.1 Floating-point
Si definisce rappresentazione floating-point di un numero reale la seguente espressione
con detta base del sistema di numerazione e segno.
Se il sistema si dice decimale, se si dice binario.
Ogni numero reale non nullo non ammette un’unica rappresentazione floating point. Tale è univocamente
determinata se si impone la seguente condizione
cio è se si impone che la prima cifra decimale di sia diversa da zero. Ad esempio, per il sistema decimale si
ottiene
1.1.2 Normalizzazione
La rappresentazione floating point del numero reale si dice normalizzata se soddisfa la
condizione
In tal caso e sono univocamente determinati e si definiscono rispettivamente mantissa di ed esponente
di
Fissata la base del sistema, i valori individuano univocamente il numero Pertanto per memorizzare
è sufficiente memorizzare i tre numeri.
Poiché un calcolatore riserva uno spazio finito di memoria, esso può memorizzare solo mantisse con un
numero finito di cifre ed esponenti appartenenti ad un certo intervallo. Si suppone di conseguenza che le
mantisse rappresentabili possano avere al massimo cifre nel sistema scelto e che l’esponente debba
soddisfare dove e sono interi definiti per ogni calcolatore.
1.2 Numeri di macchina
1.2.1 Insieme numeri macchina
È evidente che non tutti i numeri reali soddisfino le suddette condizioni. Pertanto, non tutti i numeri reali sono
esattamente rappresentabili su di un calcolatore.
Si definiscono numeri di macchina i numeri con mantissa ed esponente esattamente rappresentabili negli
spazi a loro riservati del calcolatore. L’insieme dei numeri macchina è costituito da un numero finito di elementi
così definito
con 3
ove è la base del sistema di numerazione, è il segno (0 positivo, 1 negativo), sono interi minori o
uguali a e rappresentano le cifre della mantissa, è il massimo numero di cifre della mantissa
rappresentabili e è l’esponente.
1.2.2 Regioni
La limitazione inferiore sull’esponente comporta che il più piccolo numero positivo rappresentabile in
macchina sia
Si definisce regione di underflow l’insieme dei numeri reali diversi da zero appartenenti a
La limitazione superiore sull’esponente comporta che il più grande numero positivo, rappresentabile in
macchina, sia
Si definisce regione di overflow l’insieme dei numeri appartenenti a
Anche se i dati iniziali e il risultato finale di un calcolo sono numeri macchina, o arrotondabili ad essi, le
operazioni intermedie possono generare numeri appartenenti a queste regioni. Quando succede ciò il
calcolatore invia una
segnalazione: nel primo caso il parziale viene approssimato a zero mentre nel secondo a
1.2.3 Rounding to even
Si esamina ora come vengono rappresentati i reali la cui mantissa ha più di cifre.
Sia normalizzato e sia limitato ma sia anche con più di cifre (impedendo di fatto la memorizzazione
macchina). Per rappresentare in un sistema floating point con cifre occorre arrotondare
Generalmente si ricorre alla tecnica di arrotondamento rounding to even: la mantissa viene approssimata
con la mantissa più vicina e se è equidistante da due mantisse macchina consecutive allora viene
approssimata con quella che ha l’ultima cifra pari.
Si definisce pertanto il numero di macchina arrotondato come ¯ Operativamente per
calcolare si aggiunge a e poi si tronca il risultato alla -esima cifra, con un eccezione nel caso in
cui sia equidistante da due mantisse macchina.
Pertanto se
e
ove
denotano due mantisse macchina consecutive, allora la mantissa è data da
4
1.3 Errori
1.3.1 Tipologie
In seguito con la notazione ¯ verrà indicato il numero di macchina corrispondente ad Se è un numero di
macchina, allora = ¯ altrimenti È evidente che quando e si memorizza si introduce un
errore. Per quantificare tale errore è necessario introdurre una definizione di errore. Sia un’approssimazione
di Si definisce errore assoluto la quantità
ed errore relativo la quantità
Se rappresenta un’entità diversa da uno scalare, come un vettore o una matrice, è necessario sostituire nella
definizione il valore assoluto con un’opportuna norma
Si definisce errore di arrotondamento l’errore che si commette quando si sostituisce il numero reale
con il corrispondente numero macchina Sia normalizzato e suo arrotondamento ottenuto applicando le
tecniche precedentemente descritte; pertanto non ha più di cifre. Tenendo conto che la distanza tra e
è esattamente si ottiene
In qualunque caso di vicinanza alle mantisse macchina, si ottiene la relazione
Pertanto per l’errore assoluto risulta
e, tenendo conto che per l’errore relativo risulta
1.3.2 Valori di macchina
Si definisce epsilon di macchina la quantità
mentre si definisce precisione di macchina la quantità
La precisione di macchina è una costante caratteristica di ogni aritmetica floating point; essa rappresenta il
massimo errore relativo che si commette quando si approssima il numero reale con il corrispondente numero
di macchina
Ponendo = (¯ si deduce l’uguaglianza
M.1 Matlab - Valori di macchina
Matlab implementa le specifiche del sistema standard floating point IEEE- 754 del 1985 (standard
internazionale IEC-559 dal 1989) che in doppia precisione prevede:
• base
• 64 bit per la rappresentazione di cui 1 bit per il segno, 52 per le cifre della mantissa e 11 per l’esponente.
In Matlab sono predefiniti i seguenti valori: 5
• fornisce il valore del più piccolo numero di macchina positivo e non nullo,
• fornisce il valore del più grande numero di macchina
• fornisce il valore dell’epsilon di macchina (pertanto
1.4 Operazioni di macchina
1.4.1 Definizione
Il risultato di un’operazione aritmetica tra due numeri di macchina generalmente non è un numero di macchina.
In un calcolatore non è possibile eseguire le normali operazioni aritmetiche, occorre sostituirle con le
operazioni di macchina e
L’operazione di macchina associa a due numeri di macchina un terzo numero di macchina ottenuto
arrotondando l’esatto risultato dell’operazione in questione.
Si può generalmente scrivere, dati due numeri di macchina:
e di conseguenza
Per le operazioni di macchina rimane valida la proprietà commutativa, ma non valgono in generale le proprietà
associativa e distributiva.
Un ulteriore relazione anomala è
quando
1.4.2 Equivalenza aritmetica
In generale due espressioni ed equivalenti nell’aritmetica esatta, non lo sono nell’aritmetica a precisione
finita. Si può riformulare la definizione così. Due espressioni si dicono equivalenti nell’aritmetica del
calcolatore quando forniscono risultati che differiscono per una tolleranza relativa dell’ordine di o minore,
cio è quando
è dell’ordine di o minore. Ne consegue che rappresenta la massima precisione di calcolo raggiungibile.
1.5 Cancellazione numerica
La cancellazione numerica rappresenta una delle conseguenze più gravi della rappresentazione con precisione
finita dei numeri reali. Si può definire così. Siano
le rappresentazione dei rispettivi numeri reali e
La cancellazione numerica consiste in una perdita di cifre della mantissa e si verifica quando si esegue
l’operazione di sottrazione fra due rappresentazioni di macchina dello stesso segno, circa uguali e almeno una
delle quali sia affetta dall’errore di arrotondamento, ossia quando
6
Talvolta, manipolando opportunamente le espressioni matematiche che definiscono un problema, è possibile
evitare il fenomeno della cancellazione numerica; quando ciò non è possibile si dice che la cancellazione è
insita nel problema
1.6 Condizionamento di un problema numerico
Gli esempi precedenti hanno messo in evidenza che gli errori presenti nei dati possono essere trasmessi e
amplificati nei risultati.
Si introducono di conseguenza le definizioni di problema numerico e algoritmo al fine di definire il loro
condizionamento.
1.6.1 Problema numerico
Si definisce problema numerico una relazione funzionale tra i dati (input) e i risultati (output).
La connessione tra ed può essere esplicita
oppure implicita
1.6.2 Condizionamento
Sia o un generico problema numerico. Si denotano con una perturbazione dei dati di
input e i risultati ottenuti a partire dai dati in precisione infinita di calcolo. Un problema numerico si dice ben
condizionato se accade che l’errore relativo associato ad è dello stesso ordine di grandezza dell’errore
relativo associato a o minore; altrimenti si dice mal condizionato.
Per studiare il condizionamento di un problema si possono determinare stime del tipo
Se i dati di input e/o i risultati sono rappresentati da una funzione, oppure un vettore o una matrice, nella stima
occorre sostituire il valore assoluto con una norma opportuna.
Si definisce numero di condizionamento del problema il più piccolo valore di per cui vale la
disuguaglianza.
Se non è eccessivamente grande, il problema è ben condizionato.
1.7 Stabilità di un algoritmo
1.7.1 Algoritmo
Per algoritmo si intende una sequenza finita di operazioni, aritmetiche e non, che consente di ottenere
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.