Estratto del documento

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

Anteprima
Vedrai una selezione di 6 pagine su 25
Appunti completi di Calcolo numerico Pag. 1 Appunti completi di Calcolo numerico Pag. 2
Anteprima di 6 pagg. su 25.
Scarica il documento per vederlo tutto.
Appunti completi di Calcolo numerico Pag. 6
Anteprima di 6 pagg. su 25.
Scarica il documento per vederlo tutto.
Appunti completi di Calcolo numerico Pag. 11
Anteprima di 6 pagg. su 25.
Scarica il documento per vederlo tutto.
Appunti completi di Calcolo numerico Pag. 16
Anteprima di 6 pagg. su 25.
Scarica il documento per vederlo tutto.
Appunti completi di Calcolo numerico Pag. 21
1 su 25
D/illustrazione/soddisfatti o rimborsati
Acquista con carta o PayPal
Scarica i documenti tutte le volte che vuoi
Dettagli
SSD
Scienze matematiche e informatiche MAT/08 Analisi numerica

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher maurizio.costa.03 di informazioni apprese con la frequenza delle lezioni di Calcolo numerico e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Torino o del prof Casnati Gianfranco.

Domande e risposte

Hai bisogno di aiuto?
Chiedi alla community