E-book Calcolo Numerico: algebra lineare per universitari

E-book Calcolo Numerico

Università di Napoli Parthenope Dipartimento di Scienze e Tecnologie Corsi di Laurea in INFORMATICA e in SCIENZE NAUTICHE E AERONAUTICHE 2014, release 1

E-BOOK CALCOLO NUMERICO Giulio Giunta

L'e-book è ancora in fase di revisione ed è soggetto a modifiche anche sostanziali. Gli allievi sono invitati a comunicare al docente per email eventuali errori e imprecisioni rilevati nel testo. L'e-book è distribuito con licenza Creative Commons Attribuzione - non commerciale - non opere derivate (vedi http://creativecommons .org/licenses/by-nc-nd/3.0/it)

1e-book Calcolo Numerico - Giulio Giunta 2014

Sommario

Premessa

3

Sistema Aritmetico di un computer (Lez 1)

4

I numeri f-p

4

Operazioni aritmetiche con numeri f-p

5

Errore assoluto ed errore relativo

5

Epsilon macchina

....... 6

Risoluzione numerica di una equazione e del problema del punto fisso (Lez 2 e 2bis)

7

Il problema f(x)=0

7

Metodo di bisezione

8

Metodo di Newton

9

Metodo delle secanti

12

Metodi ibridi

13

Il problema del punto fisso g(x)=x

14

Determinazione di minimi locali di una funzione (Lez 3)

16

Il problema min f(x)

16

Metodo di Newton per la minimizzazione

17

fminbnd

18

Minimo di funzioni unimodali

19

Fibonacci search e Golden search

20

Algebra lineare numerica (Lez 4 e 5)

22

Le operazioni di base con vettori e matrici

22

Algoritmi per la risoluzione di sistemi lineari: Ax=b

25

Fattorizzazione LU

28

Interpolazione di dati (Lez 6 e 7)

30

Il problema di interpolazione

30

33

Approssimazione di dati e sistemi lineari sovradeterminati (Lez 8 e 8bis)

38

Il problema di approssimazione

38

Minimi Quadrati

..... 39

Interpolazione con polinomi a tratti

Sistemi sovra-determinati 41

2e-book Calcolo Numerico - Giulio Giunta 2014

Premessa

L'e-book è costituito dalle "sintesi delle lezioni" del Corso di Calcolo Numerico, tenute dal prof. Giulio Giunta presso il Corso di Laurea in Informatica e il Corso di Laurea in Scienze Nautiche e Aeronautiche di Uniparthenope. Le "sintesi delle lezioni" contengono i punti essenziali di ogni lezione. La sintesi delle lezioni 9-10 e 11-12 è in via di redazione e sarà aggiunta nella release 2 dell'e-book. Come tutto il materiale didattico del Corso (video-lezioni, pdf e pps delle slide, quiz online, esercizi, prove di esame, et cetera), le "sintesi" sono anche scaricabili in formato pdf dalla piattaforma di e- learning del DiST ( http://e-dist.uniparthenope.it )

3e-book Calcolo Numerico - Giulio Giunta 2014

Sistema Aritmetico di un computer (Lez 1)

I numeri f-p

In tutti computer (e in tutti i dispositivi digitali) i numeri sono rappresentati in modo standard e sono detti numeri floating-point (f-p). Il formato standard di un numero f-p è:

• base 2 (solo due cifre: 0,1);
• mantissa (normalizzata, cioè con parte intera sempre uguale a 1 e seguita dalla parte frazionaria, detta frazione) per base elevata a esponente (intero);
• a precisione finita (sia la mantissa, sia l'esponente hanno un numero prefissato di cifre).

Il numero di bit (cifre binarie) per la mantissa (più precisamente, per la frazione), chiamiamolo t, è prefissato ed è detto precisione; anche il numero di bit per l'esponente è prefissato. Nella mantissa c'è l'informazione relativa alle (prime t) cifre significative del numero. La mantissa è del tipo 1.frazione dove frazione è una sequenza di t bit; in memoria si memorizza solo la frazione, in quanto sia il primo bit (sempre 1) sia il . punto frazionario non devono essere memorizzati perché sempre in posizione fissa. Nell'esponente c'è l'informazione relativa all'ordine di grandezza del numero. L'esponente è memorizzato nella forma esponente + bias, in modo da memorizzare sempre un numero positivo. Il numero 0 è rappresentato come una sequenza di bit nulli. Perché è stato scelto di rappresentare così i numeri f-p in un computer? il motivo è quello di simulare, con un errore piccolo (che dipende dalla precisione t), un grande intervallo di numeri reali. Si ricorda che per rappresentare esattamente un numero reale, a meno che non si tratti di un intero o di un razionale, è necessaria una mantissa a precisione infinita. In doppia precisione, che è quella usata da Matlab, tale intervallo è (-10308, 10308 ). Per avere un'idea della grandezza di tale intervallo, si tenga presente che il numero stimato di atomi nell'universo è (solo!) 1080. Ogni volta che si inserisce un numero in un calcolatore, tale numero viene memorizzato come numero f-p. In generale, ciò comporta un errore (sulla mantissa) che è minore di 2-t-1, dove t è il numero di bit della frazione (precisone). In doppia precisione t=52, quindi l'errore sulla mantissa è <2-53 ~ 10-16. Si noti che questo significa che se il numero è espresso in base 10 (cioè nel modo usuale in cui scriviamo i numeri), allora la sedicesima cifra significativa (cioè l'ultima) del numero f-p può essere sbagliata per meno di mezza unità. Si noti anche che questo errore grava sulla mantissa del numero f- p (come vedremo, è un errore relativo). Per avere l'errore assoluto, bisogna moltiplicare tale errore per l'ordine di grandezza del numero, cioè per 2 elevato all'esponente del numero.

4e-book Calcolo Numerico - Giulio Giunta 2014

Per esempio, usando per semplicità la base 10 e una precisione 2, si ha che l'errore sulla mantissa (errore relativo) del numero 6.78*105 è < 0.5*10-2 (cioè meno di mezza unità nell'ultima cifra), mentre l'errore assoluto è < 0.5*10-2 *105 = 0.5* 103, cioè è minore di 500.

Operazioni aritmetiche con numeri f-p

L'unità aritmetica di ogni computer è in grado di eseguire solo le quattro operazioni aritmetiche (+,- ,*,/) su numeri f-p. Il risultato di un'operazione aritmetica eseguita da un computer (operazione f-p) è ancora un numero f-p, che è la rappresentazione f-p del risultato dell'operazione aritmetica eseguita sugli operandi. Per esempio, usando per semplicità la base 10 e una precisione 2, 6.78*105 * 7.21 = 4888380 che viene rappresentato in forma f-p come 4.89*106 . Si noti che in generale ogni volta che si effettua una operazione aritmetica in un computer, sul risultato grava un errore che ha le stesse caratteristiche dell'errore legato all'immissione di un nuovo numero, cioè errore sulla mantissa <2-53 ~ 10-16 ed errore assoluto < 10-16 per l'ordine di grandezza del risultato.

Errore assoluto ed errore relativo

Sia x un numero qualunque e X un numero che lo approssima, allora l'errore assoluto tra x e X è |x - X|; l'errore relativo tra x e X è |x - X| / |x| , cioè l'errore relativo è dato dall'errore assoluto diviso per il numero stesso (in valore assoluto). Basta un po' di attenzione per convincersi che l'errore assoluto coinvolge, per così dire, tutta l'informazione sui due numeri, mentre l'errore relativo coinvolge solo le loro mantisse, cioè solo le cifre significative e non l'ordine di grandezza. Infatti, poiché X è circa uguale a x, allora x e X hanno (quasi sicuramente) lo stesso esponente e l'errore relativo può scriversi come | mantissa di x - mantissa di X | *base elevata a esponente / | mantissa di x| *base elevata a esponente semplificando e notando che la mantissa è sempre compresa tra 1 e 2 (in generale tra 1 e la base), si ha che l'errore relativo è minore o uguale di | mantissa di x - mantissa di X|, ovvero dell'errore assoluto tra le mantisse. E' utile ricordare il teorema dell'errore assoluto: se x e X hanno uguali sia le loro parti intere sia le prime m cifre delle loro parti frazionarie, allora l'errore assoluto è tale che |x - X| < 10-m . E' utile ricordare il teorema dell'errore relativo: se x e X hanno uguali le prime m cifre significative, allora l'errore relativo è tale che |x - X |/|x| < 10-m. Da questo teorema discende che il numero di

5 5e-book Calcolo Numerico - Giulio Giunta 2014

cifre (in base 10) significative uguali tra x e X è stimato dal valore assoluto del logaritmo in base 10 dell'errore relativo.

Epsilon macchina

Un semplice esempio può convincerci che, nell'operazione di addizione, alcuni numeri f-p hanno un comportamento che nei numeri reali è proprio solo dello 0, che l'unico numero neutro rispetto all'addizione tra numeri reali : x + 0 = x. Infatti, l'operazione di addizione f-p, nel solito sistema di esempio con base 10 e precisione 2, 2.47*105 + 3.21* 101 fornisce: 247000.0 + 32.1 = 247032.1 = 2.470321*105, che in forma f-p diventa: 2.47*105, cioè il primo addendo! L'informazione fondamentale che consente di gestire tali situazioni è il numero detto epsilon macchina. Epsilon macchina è il più piccolo numero f-p che sommato (addizione f-p) a 1 fornisce come risultato un numero f-p maggiore di 1. Si noti che un qualunque numero x strettamente minore di epsilon macchina è tale che 1 + x fornisce 1 come risultato f-p. In altri termini, epsilon macchina permette di definire l'intervallo [0, epsilon macchina) di numeri che si comportano come il numero 0 nell'addizione f-p con il numero 1. Nel solito sistema di esempio con base 10 e precisione 2, l'epsilon macchina è 0.5*(successivo_ di_ 1 - 1) = 0.5*10-2 = 5.0*10-3 . Il comportamento neutro rispetto all'addizione f-p con 1 si riscontra anche nel caso di addizione f-p con un qualunque numero z. Tutti i numeri y appartenenti all'intervallo [0, z* epsilon macchina) sono tali che z + y = z . Se si considera l'esempio di prima, 2.47*105 + 3.21* 101 che fornisce il risultato 2.47*105, si può osservare che 3.21* 101 è neutro nell'addizione con 2.47*105, perché 3.21* 101 appartiene all'intervallo [0, 2.47*105 * epsilon macchina = 2.47*105 *5.0*10-3 = 1.23*103).

6e-book Calcolo Numerico - Giulio Giunta 2014

Risoluzione numerica di una equazione e del problema del punto fisso (Lez 2 e 2bis)

Il problema f(x)=0

Il problema è detto "risoluzione di una equazione" oppure "determinazione di uno zero di una funzione". Ci siamo occupati solo di soluzioni che sono numeri reali, e non del caso più generale in cui le soluzioni possono essere numeri complessi. Un numero r è una soluzione del problema f(x) = 0 se si ha che f(r) = 0. Il problema può ammettere nessuna soluzione, una o più soluzioni, o anche infinite soluzioni, a seconda della natura della f e del dominio a cui si è interessati. Gli algoritmi (metodi) che abbiamo trattato permettono di determinare una sola soluzione alla volta. Quindi, se il problema ammette più soluzioni, l'algoritmo deve essere eseguito tante volte quante sono le soluzioni che si vogliono calcolare. I dati che devono essere noti sono: la funzione f e poi una informazione che consente di localizzare una soluzione. Tale informazione può essere un intervallo (incluso nel dominio di f) che contiene la soluzione o un numero che rappresenta una approssimazione iniziale della soluzione. In genere, la localizzazione avviene esaminando il grafico della f o usando altre informazioni sul problema. Si ricorda che la f si ritiene nota se si conosce la sua espressione esplicita (per es. f(x)=sin(3x)/(1+(log(x2))2) ), oppure se si ha un programma che consente di calcolare il valore di f(x) per qualunque valore fissato x. Un importante aspetto teorico del problema f(x) = 0 è che, anche se esiste una soluzione, può non esistere una formula (chiusa) per calcolarla. Si ricorda che per formula chiusa si intende una formula che contiene un numero finito di operazioni aritmetiche e di valutazioni di funzioni elementari. Un esempio in tal senso è dato dal teorema di Ruffini-Abel-Galois che afferma l'impossibilità di esprimere mediante formula chiusa (che coinvolga i coefficienti del polinomio) gli zeri di un qualunque polinomio di grado maggiore o uguale di 5: per esempio, non esiste una formula per risolvere 3x5-8x4-x+1=0. Ne consegue che un algoritmo per risolvere il problema f(x) = 0 deve necessariamente essere di tipo iterativo. Un algoritmo iterativo è in grado di generare una successione che, sotto opportune ipotesi, converge alla soluzione del problema. E' chiaro che un algoritmo iterativo deve contenere un criterio di arresto che stabilisce le condizioni che si devono verificare per terminare, a un certo passo p, il processo iterativo, in modo che il p-simo elemento della successione (detto approssimazione al passo p) sia una approssimazione soddisfacente della soluzione (ovvero del limite della successione).

7