Calcolo numerico - Appunti con tutte le esercitazioni svolte

Calcolo numerico

Sommario

Aritmetica ed errori ................................................................................................................................. 2

Rappresentazione dei numeri ........................................................................................................ 2

Numeri di macchina......................................................................................................................... 2

Operazioni di macchina .................................................................................................................. 3

Cancellazione numerica ................................................................................................................ 3

Condizionamento di un problema numerico ............................................................................. 3

Stabilità di un algoritmo .............................................................................................................. 4

Approssimazione di funzioni e di dati...................................................................................................... 4

Rappresentazione monomiale ....................................................................................................... 4

Rappresentazione di Lagrange ...................................................................................................... 6

Convergenza del polinomio di interpolazione .......................................................................... 7

Funzioni polinomiali a tratti: spline ............................................................................................ 9

Applicazione nel calcolo di integrali .........................................................................................11

Sistemi lineari .........................................................................................................................................11

Condizionamento di un sistema lineare.....................................................................................12

Metodi numerici .............................................................................................................................14

Metodo delle eliminazioni di Gauss ............................................................................................14

Fattorizzazione PA=LU e applicazioni ......................................................................................15

Fattorizzazione di Choleski e applicazioni .................................................................................17

Fattorizzazione QR e applicazioni ..............................................................................................18

Autovalori e valori singolari di matrici ...................................................................................................20

Condizionamento del calcolo degli autovalori .........................................................................22

Metodi numerici .............................................................................................................................22

Metodi per l’approssimazione di un autovalore ......................................................................22

Metodi per l’approssimazione di tutti gli autovalori ............................................................23

Valori singolari e decomposizione SVD ......................................................................................24

Proprietà della composizione SVD...............................................................................................25

Applicazioni della decomposizione SVD ......................................................................................27

Esercitazione 0....................................................................................................................................28

Esercitazione 1....................................................................................................................................30

Esercitazione 2....................................................................................................................................32

Esercitazione 3....................................................................................................................................35

Esercitazione 4....................................................................................................................................41

1

Appunti MATLAB

Aritmetica ed errori

Rappresentazione dei numeri

= (−1) ∈ {0,1}, ≥ 0 Rappresentazione floating point dove è la mantissa, è l’esponente, N è la base del sistema di enumerazione e vale 0 (segno positivo) oppure 1 (segno negativo)

−1→ ≤ < 1 la rappresentazione si dice normalizzata se: p e q sono univocamente determinati, cioè la ≠ 0 prima cifra dopo la virgola è e l’unica prima della virgola è 0.

Fissata la base N i valori di s, p, q individuano univocamente il numero reale.

Numeri di macchina

Poiché il calcolatore ha uno spazio di memoria finito, può memorizzare solo mantisse con un numero finito di cifre ed esponenti appartenenti ad un certo intervallo. Non tutti i numeri reali soddisfano le condizioni, quindi 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 dal calcolatore.

{0} = ∪ Insieme dei numeri macchina è un insieme finito di elementi ed è così definito: {(−1) 0. … ∙ , 0 ≤ < , ≠ 0, ≤ ≤ , dove è il massimo numero di cifre della mantissa 1 2 … − 1 rappresentabili e sono interi minori o uguali a 1 2

Regione di underflow (-m,m) con m (più piccolo numero positivo rappresentabile come numero di macchina) → se 0.10000 ∙ < = il risultato viene approssimato a 0

(−∞, ) ∪ (, +∞) Regione di overflow con M (più grande numero positivo rappresentabile come numero → 0. − 1 − 1 … − 1 ∙ > di macchina) = se il risultato viene approssimato al simbolo inf

→ Per ottenere il risultato finale di un’operazione bisogna evitare le regioni di overflow.

→ Nel caso la mantissa abbia più di t cifre bisogna arrotondare. Tecnica di arrotondamento “rounding to ̅ even”: la mantissa viene approssimata con la mantissa di macchina più vicina e se è equidistante da due mantisse di macchina consecutive allora viene approssima con quella delle due che ha l’ultima cifra pari.

Quando si sostituisce il numero reale con il corrispondente numero di macchina si può commettere un errore, chiamato errore di arrotondamento che può compromettere gravemente il risultato delle operazioni. Si può misurare quanto è “grande” questo errore:

| | = − ̅ ≥ 0 Errore assoluto

|−̅ | = , ≠ 0 Errore relativo tiene conto dell’ordine di grandezza della quantità in esame || ∙ ||)(se si è in presenza di vettori o matrici usare la NORMA (|| al posto del valore assoluto 1 − | | | |− ̅ = |(−1) − (−1) ̅ = − ̅ ≤ 2 | |− ̅ 1 1− ≤ || 2 1− = Epsilon di macchina 2

1 1− ɛ = Precisione di macchina è una costante caratteristica di ogni aritmetica floating point; essa 2 rappresenta il massimo errore relativo che si commette quando si approssima il numero reale con il ̅ corrispondente numero di macchina

̅− → ɛ = ̅ = (1 + ɛ), |ɛ| ≤ ɛ

Se MATLAB utilizza la rappresentazione floating point IEE 754 che usa 64 bit: N=2, 1 bit per il segno, 52 bit per la mantissa, 11 bit per l’esponente

• “Realmin” valore + piccolo di macchina, circa 2.2x10^-308
• “Realmax” valore + grande rappresentabile, circa 1.8x10^308
• “Eps” 2.2x10^-16 (dunque precisione di macchina 1.1 x 10^-16)

Operazioni di macchina

Il risultato di un’operazione aritmetica tra due numeri di macchina generalmente non è un numero di macchina. In un calcolatore non è possibile eseguire esattamente le operazioni aritmetiche, ma solo le cosiddette operazioni di macchina, che vengono rappresentate con i simboli ⊕, ⊖, ⊗ ⊘. 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, cioè:

̅̅̅̅̅̅̅̅̅̅̅̅̅⨁̅̅̅ = ̅̅̅ + ̅̅̅ 1 2 1 2

| | | | ̅̅̅⨁ ̅̅̅ = ̅̅̅ ̅̅̅ ≪ |̅̅̅|, ̅̅̅ < |̅̅̅|.

Una relazione anomala è quando in particolare quando Infatti, in 1 2 1 2 1 2 1 | | ̅̅̅ |̅̅̅| tal caso, il valore di è “troppo piccolo” rispetto a e non fornisce alcun contributo nella somma. 2 1

Due espressioni si dicono equivalenti nel calcolatore quando, valutate, nel calcolatore stesso, forniscono ɛ risultati che differiscono per una tolleranza relativa dell’ordine della precisione di macchina o minore, ɛ cioè quando l’errore relativo tra i due è dell’ordine della precisione di macchina o minore.

→ ɛ Ne consegue che rappresenta la massima precisione (relativa) di calcolo raggiungibile: non ha ɛ senso cercare di determinare approssimazioni con precisione relativa inferiore a.

Cancellazione numerica

Cancellazione numerica = perdita di cifre della mantissa che causa amplificazione dell’errore di ̅ ̅ arrotondamento. Operazione di sottrazione fra due rappresentazioni di macchina e dello stesso segno, 1 2 circa uguali e almeno una delle quali sia affetta da errore di arrotondamento = - 1 2 = - 1 2

̅ ≈ ̅ - 1 2

̅ ≠ ̅ ≠ e/o - 1 1 2 2

Modi per evitare il fenomeno della cancellazione numerica:

• Razionalizzazione (se possibile)
• Espansione di Taylor
• Relazioni trigonometriche

Quando non è possibile evitare la cancellazione si dice che essa è insita nel problema.

Condizionamento di un problema numerico

̅ Un problema numerico si dice ben condizionato se l’errore relativo associato a (la soluzione) è dello stesso ̅ ordine di grandezza dell’errore relativo associato a (i dati) o minore; altrimenti si dice mal condizionato.

3

Pertanto, un problema è ben condizionato quando le perturbazioni nei dati non influenzano eccessivamente i risultati.

(, ) Il numero di condizionamento del problema è il più piccolo valore di per cui vale la suddetta |−̅| |−̅ | ≤ (, ) disuguaglianza: . Se K non è eccessivamente grande (cioè circa 1), il problema è ben || || condizionato; se è grande allora il problema potrebbe essere mal condizionato.

+ ≈ 0, In particolare, il problema può essere mal condizionato quando ossia quando i due numeri sono 1 2 di segno opposto e circa uguali in modulo la loro somma può causare un’amplificazione degli errori presenti nei due operandi. Il mal condizionamento fornisce un’interpretazione alternativa del fenomeno della cancellazione numerica.

Stabilità di un algoritmo

̃ Un algoritmo si dice numericamente stabile se accade che l’errore relativo associato al risultato (risultati ̅ dell’algoritmo ottenuti a partire dai dati in precisione finita di calcolo) ha lo stesso ordine di grandezza della |̃−̅| < ɛ precisione di macchina o minore, cioè ; altrimenti si dice instabile. Pertanto, un algoritmo è || numericamente stabile quando la sequenza delle operazioni non amplifica eccessivamente gli errori di arrotondamento presenti nei dati.

Approssimazione di funzioni e di dati

Approssimare una funzione f significa sostituirla con una funzione che le sia vicina e abbia una forma più semplice su cui si possa facilmente operare.

Una funzione sufficientemente regolare f può essere approssimata dal suo polinomio di Taylor. Tale approssimazione, tuttavia, può essere insoddisfacente poiché fornisce una buona approssimazione della funzione solo in un intorno di un punto e il calcolo del polinomio richiede la conoscenza delle derivate della funzione.

, Il criterio dell’interpolazione consiste nello scegliere come approssimante dei dati ( ) una funzione che , imponga il passaggio di f per i punti ( ). Le suddette equazioni sono dette condizioni di interpolazione e , = ( ), i punti sono detti nodi di interpolazione; inoltre, si dice che f interpola i dati ( ), oppure se interpola la funzione f nei punti ., ()

Assegnati n+1 punti ( ) con le ascisse distinte tra loro, esiste uno e un solo polinomio di grado minore o uguale a n interpolante i dati assegnati, ovvero soddisfacente le condizioni di interpolazione.

Rappresentazione monomiale

() Si definisce rappresentazione monomiale del polinomio interpolante l’espressione: −1() = + + ⋯ + + 1 2 +1 () ove i coefficienti di interpolazione , i=1,…,n+1, sono determinati imponendo che soddisfi le condizioni di interpolazione.

Interpolazione polinomiale in MATLAB

• “c=polyfit(x,y,n)=polyfit(x,y,length(x)-1)” calcola e memorizza in c, i coefficienti della rappresentazione monomiale del polinomio di grado n interpolante i dati ( )
• “p=polyval(c,z)” calcola e memorizza nel vettore p, i valori che un qualsiasi polinomio i cui coefficienti sono memorizzati in c, assume nelle componenti del vettore z, restituisce un valore y(f(z))

4

Valuto il polinomio x^3-2x^2+3x+4 nei punti 1 2 3 4 5

x=[1 2 3 4 5]; (punti che voglio valutare)

c= [1 -2 3 4]; (coefficienti polinomio)

y= polyval(c,x)

>>y = 6 10 22 48 94

Esempio 1

Prendo dei dati a caso x,y

x=[0 1 2 3]; oppure x=[0:3]; oppure x=linspace(0,3,4);

y=[-1 0 1 2];

c=polyfit(x,y,length(x)-1); 3 è n-1, e sarà il grado del polinomio, c saranno i coefficienti calcolati inseriti in un vettore

z=linspace(min(x),max(x),100); creo un campo in cui valutare il polinomio con 100 pt equispaziati

p=polyval(c,z); valuto il polinomio di coefficienti c nei punti z

plot(z,p);

Ora verifico che il mio polinomio interpolante passi per i dati assegnati

hold on

plot(x,y,'r*') in questo modo non congiunge i punti ma li contrassegna con asterischi rossi

N.B. Di default il terzo parametro di linspace è 100

Esempio 2

Proviamo a interpolare la funzione x*sen(x)

x = linspace(0,pi,11); genera un vettore a elementi equispaziati tra 0 e pi greco

y = x.*sin(x); ottengo 11 punti di questa funzione tra 0 e pi

c=polyfit(x,y,length(x)-1); ottengo i coefficienti di un polinomio di grado n-1 che passa per questi punti

z=linspace(min(x),max(x)); creo campo in cui valutare la funzione

p=polyval(c,z); calcolo il valore(f(x)) del polinomio interpolante di coefficienti c nei punti z

plot(z,p);

hold on

plot(x,y,'r*')

5

= N.B. polyfit per il calcolo dei coefficienti utilizza il criterio dei minimi quadrati, ma nel momento in cui il polinomio approssimante che si ottiene soddisfa anche il criterio dell’interpolazione.

Esempio 3

f=@(x) x.*sin(x);

z=linspace(0,2*pi);

for n = [5 11]

x = linspace (0,2*pi,n+1);

y=f(x);

c=polyfit(x,y,n);

p=polyval(c,z);

plot(x,y,’ro’,z,f(z),’r’,z,p,’b’)

pause

end

Warning: polynomial is badly conditioned

La determinazione del polinomio interpolante mediante la sua rappresentazione monomiale comporta la risoluzione di un problema mal condizionato. Per grandi il mal condizionamento non è trascurabile, quindi è necessario utilizzare rappresentazioni alternative a quella monomiale.

Rappresentazione di Lagrange

, ≠ Si definisce rappresentazione di Lagrange del polinomio interpolante i dati ( ), i=1,…,n+1 con ≠ , per l’espressione +1() ∑ = () =1 ()

I polinomi di grado n sono detti polinomi fondamentali di Lagrange associati ai nodi: (− )…(− )(− )…(− )1 −1 +1 +1() = = 1, … , + 1 per ( )…( )( )…(− − − − ) 1 −1 +1 +1

Quindi la rappresentazione di Lagrange è una combinazione dei polinomi fondamentali di Lagrange.

() Per esempio, scriviamo la rappresentazione di Lagrange del polinomio interpolante i dati 31 (0,1), (1, −1), (2,1), ( ). (), = 1,2,3,4