Appunti Metodi numerici

1 Slides 1

Avvalendosi di un calcolatore si lavora con una aritmetica finita che dà luogo ad ERRORI

ERRORE INERENTE: Si commettono errori rappresentando i dati del problema con un numero finito di

cifre

ERRORE ALGORITMICO: Si commettono errori eseguendo le operazioni aritmetiche richieste dal processo

di calcolo con una aritmetica finita

Un problema è malcondizionato se piccole variazioni sui dati inducono grandi variazioni sui

DEFINIZIONE:

risultati.

La complessità di calcolo (detta anche COMPLESSITA’ COMPUTAZIONALE o COSTO COMPUTAZIONALE)

viene misurata in funzione delle dimensioni del problema che si sta trattando e dà indicazione del numero di

operazioni aritmetiche che necessitano per ottenere il risultato.

1

2 Slides 2

2.1 Rappresentazione Floating Point q

·

x = p N

Dove: ∈

p è un numero reale (p R)

N è la base del sistema di numerazione scelto

q è un intero positivo → →

p MANTISSA q ESPONENTE

−5

·

Esempio: x = 0.12345 = 12345 10

Dove ”12345” è la mantissa(p) e ”-5” è l’ esponente(q). Quindi ad x si associa la coppia (p,q).

La rappresentazione normalizzata cioè −1 ≤ |p|

N < 1

̸

conduce alla rappresentazione unica di un numero x = 0 mediante la coppia (p, q)

Lo spazio riservato alla rappresentazione di un un numero reale può essere visto come:

segno (s) esponente(q) mantissa (|p|)

Si avrà che:

Per la singola precisione ci saranno a disposizione 32 bit quindi: 1 bit per il segno, 8 bit per l’esponente e 23

bit per la mantissa.

Per la doppia precisione ci saranno a disposizione 64 bit quindi: 1 bit per il segno, 11 bit per l’esponente e

52 bit per la mantissa. −127 ≤ ≤

q 128 (semplice precisione)

−1023 ≤ ≤

q 1024 (doppia precisione)

∈ R

DEFINIZIONE: x è detto numero macchina.

∈

q / m, M Se q < m si associa zero ad x ed il sistema segnala la situazione di UNDERFLOW

Se q > m x non viene rappresentato ed il sistema segna la situazione di OVERFLOW

q q

∈ ±pN ∈ ℑ

Se q [m, M ] ma x = / allora si usa l’approssimazione x = p N

e e

2.2 Troncamento(O Chopping)

Nella mantissa p vengono escluse le cifre dopo la t-esima

p = 0.a a a ...a a ...a

1 2 3 t t+1 s

p = 0.a a a ...a

1 2 3 t

e ERRORE ASSOLUTO ERRORE RELATIVO

−x

x

−

ϵ = x x ϵ = e

A R x

e −t+q

|ϵ | < N

A −t+1

|ϵ | < N

R

2.3 Arrotondamento

q

x = arr(x) x = p N

e e e trn(p) se a < N/2

t+1

−t

12 ≥

) se a N/2

trn(p + N t+1

−t+q

1

|ϵ | < N

A 2 −t+1

1

|ϵ | < N

R 2

Il valore che limita superiormente l’errore relativo (eps) è detto precisione di macchina

−t+1

N T roncamento

eps = −t+1

1 N Arrotondamento

2 2

2.4 Operazioni Di Macchina

Se si effettua un operazione su due numeri di macchina, il risultato non per forza lo è. Bisogna approssimare

affinchè: ∈ ℑ → ∈ ℑ ∈ ℑ

x, y x op y / ma f l(x op y)

f l(x op y)−x op y |ϵ | < eps

ϵ = R

R x op y

Definizione: f l(x op y) = (1 + ϵ )(x op y)

R

In aritmetica non è detto che valgano le proprietà dell’aritmetica:

· · ̸ · ·

f l(f l(x y) z) = f l(x f l(y z))

̸

f l(f l(x + y) + z) = f l(x + f l(y + z))

Esempi Da Pagina 18 Sliedes 2 3

2.5 Errore Inerente

Errore relativo alla rappresentazione. f (x)−f (x)

e

ϵ =

In f (x)

Sviluppo in serie di Taylor al primo ordine f (x):

e δf (x) δf (x)

− −

f (x) = f (x) + (e

x x ) + ... + (e

x x )

i i n n

e δx δx

i n

δf (x) δf (x)

− − −

f (x) f (x) = (e

x x ) + ... + (e

x x )

i i n n

e δx δx

i n

Divido entrambi i membri per f (x) e moltiplico e divido il secondo membro per x ottenendo:

i

n − x δf (x)

(e

x x ) i

i i

X

ϵ =

IN f (x) x δx

i i

i =1

−

(e

x x )

i i

Sapendo che ϵ = si può scrivere:

r i x i n δf (x)

x i

X

ϵ = ϵ

IN r f (x) δx

i

i =1

δf (x)

x si ottiene:

Ponendo C = i

i f (x) δx i n

X

ϵ = ϵ C

IN r i

i =1

Dove C è l’INDICE DI CONDIZIONAMENTO

i

2.6 Errore Algoritmico M

X

ϵ = θ x , x , x , ..., x γ

ALG i 1 2 3 n i

i =1

Dove M è il numero di operazioni che compongono l’algoritmo in uso.

γ := ϵ i = 1, 2, 3, ... , M

i Ri

2.7 Errore Totale ≈

ϵ ϵ + ϵ

T OT IN ALG

(Esempio Da Pagina 33 Slides 2) 4

3 Slides 3  a x + a x + ... + a x = b

11 1 12 2 1n n 1



 a x + a x + ... + a x = b

 21 1 22 2 2n n 2



 ............................................

............................................







 a x + a x + ... + a x = b

 m1 1 m2 2 mn n m

Da cui si può ottenere la matrice A associata al sistema, il vettore x delle incognite, e il vettore b dei termini

noti. Quindi si può scrivere il sistema come: Ax = b

Esempi Da Pagina 4 Sliedes 3

3.1 Norma Di Un Vettore

La norma di un vettore è un a applicazione che a un vettore associa un numero reale.

n + S

|| · || C −→

: R 0

Definizione: n

||x|| ≥ ∀x ∈ ||x|| ↔

1. 0 C , = 0 x = 0

n

||αx|| |α| ||x|| ∀x ∈ ∀α ∈

2. = C , C n

||x ≤ ||x|| ||y|| ∀x ∈

3. + y|| + , y C

Le funzioni norma più comunemente usate sono:

n

X |x |

||x|| Norma 1

= i

1 i =1

||x|| |x |

= max Norma Infinito

∞ ≤ ≤

1 i n i

v n

u X

u 2

|x |

||x|| Norma 2

= i

2 t

i =1

Algoritmo Pagina 12 Sliedes 3

3.2 Norma Di Una Matrice

La norma di una matrice è un a applicazione che a una matrice associa un numero reale.

n×n + S

|| · || C −→ 0

: R

Definizione: n×n

||A|| ≥ ∀A ∈ ||A|| ↔

1. 0 C , = 0 x = Ω

n×n

||αA|| |α| ||A|| ∀A ∈ ∀α ∈

2. = C , C

n×n

||A ≤ ||A|| ||B|| ∀A ∈

3. + B|| + , B C

Le funzioni norma più comunemente usate sono:

n

X

||A|| |a |

= max Norma 1

≤ ≤

1 1 j n ij

i =1

n

X

||A|| |a |

= max Norma Infinito

∞ ≤ ≤

1 i n ij

j =1

q T

||A|| = ρ(A A) Norma 2

2

Dove ρ è il raggio spettrale cioè il massimo tra gli autovalori in modulo

Algoritmo Pagina 12 Sliedes 3

3.3 Relazioni Tra Norma Di Vettore E Di Matrice

Compatibilità tra norma di vettore e di matrice:

||Ax|| ≤ ||A|| ||x||

∞ ∞

Norma di vettore 1, 2 e sono compatibili con una norma 1, 2 e di una matrice.

5

3.4 Condizionamento Di Un Sistema Lineare −1

||A|| ||A ||

K(A) =

In mathlab, cond(A) fornisce in output l’indice di condizionamento del sistema Ax = b

(Da Pagina 19 Slides 3 )

3.5 Metodi Numerici Per La Risoluzione Di Sistemi Di Equazioni Lineari

(Da Pagina 22 Slides 3 )

3.6 Metodi Diretti Per La Risoluzione Di Sistemi Lineari

Sono dei metodi basati sulla trasformazione del sistema in uno equivalente che ha una struttura più semplice,

e quindi è più facile calcolare la soluzione in un numero finito di passi.

Vengono usati per sistemi di dimensioni non troppo grandi e con la matrice del sistema piena cioè con la mag-

gior parte degli elementi diversi da zero.

3.7 Metodo Di Eliminazione Di Gauss (MEG)

Il Metodo Di Eliminazione Di Gauss trasforma in n-1 passi il sistema lineare

n×n n×1

∈ ∈ ̸

Ax = b A R x, b R det(A) = 0 3

n )

in una matrice dei coefficienti triangolare superiore. Ha un costo computazionale O( 3

Formule Generali:

Per k = 1, 2, ..., n-1 e i = k+1, k+2, ..., n (k)

a

ik

m =

ik (k)

a

kk

(k) (k)

−

a = a m a

ij ik

ij kj

(k+1) (k) (k)

−

b = b m b

ik

i i k

Esempio Da Pagine 16 Slides 4

Algoritmo Gauss (Prima Versione)

INPUT: A, n

n n

OUTPUT: A , b

Ripetere per k = 1, n-1

Ripetere per i=k+1,n

m = a /a

ik ik kk

Ripetere per j=k+1,n

−

a = a m a

ij ij ik kj

−

b = b m b

i i ik k

3.8 Metodo Di Gauss Con Pivoting Parziale

(k) (k) (k)

≥ |a | |a |

Se a = 0 si cerca un r k tale che = max k≤s≤n

kk rk sk

Cioè si scambia la riga k-esima con la riga r-esima. Conviene, ad ogni passo k usare questa tecnica, anche se

(k) ̸

a = 0 perché aumenta la stabilità numerica.

kk

(Esempio Da Pagina 34 Slides 4 ) (Codice Pagina 36 Slides 4 )

6

4 Slides 4

4.1 Fattorizzazioni

Il sistema Ax = B viene risolto operando una fattorizzazione della matrice A = BC.

Questo significa che BCx = b e cioè che: Cx = y e By = b

4.2 Fattorizzazione LU

La scelta delle matrici B e C caratterizza la fattorizzazione. Avremo che:

B=L L è triangolare inferiore

C=U U è triangolare superiore 









 a a a ... ... a

1 0 0 ... ... 0

a a a ... ... a 11 12 13 1n

11 12 13 1n 0 u u ... ... u

l 1 0 ... ... 0

a a a ... ... a 22 23 2n

21

21 22 23 2n 









 







 

0 0 u ... ... u

l l 1 ... ... a

a a a ... ... a 33 3n

31 32 3n

31 32 33 3n 









 .. .. .. .. ..

.. .. .. .. ..

.. .. .. .. .. 









 ..

..

.. = 









 .

.

. . . . . .

. . . . .

. . . . . 











 







 .. .. .. .. ..

.. .. .. .. ..

. .. .. .. .. ..

..

..

.. 









 .

.

. . . . . .

. . . . .

. . . . 







 

0 0 0 ... . . . u

l l l ... ... 1

a a a ... . . . a nn

n1 n2 n3

n1 n2 n3 nn (1)

Si può notare che la matrice L ha tutti uno sulla diagonale principale e che la prima riga della matrice U è

uguale alla prima riga della matrice A.

Questa fattorizzazione è possibile se det(A )̸ =0. Dove A è la sottomatrice di ordine k.

k k

Gli elementi di L e U si ottengono dall’uguaglianza A = LU

Come si procede con il calcolo?

Essendo che prima riga di U è sempre uguale alla prima riga di A. Per la seconda riga si avrà:

a

→

a = l u l = 21

21 21 11 21 u 11

→ −

a = l u + l u u = a l u

22 21 12 22 22 22 22 21 12

→ −

a = l u + l u = u = a l u

2n 21 1n n2 2n 2n 2n 21 1n

Iterando si arriva alla conclusione che l’elemento a è dato dalla somma dei prodotti degli elementi

mn

della riga m della matrice L per gli elementi della colonna n della matrice U (Il normale prodotto

riga per colonna)

In definitiva possiamo dire che: n−1

X

−

u = a l u

ij ij ik kj

k=1

Quindi in generale si avrà che i−1

X

−

u = a l u j = i, ..., n

ij ij ik kj

k=1

j−1

X

−

a l u

ij ik kj

k=1 −

j = 1, ..., i 1

l =

ij u

jj 7

4.3 Applicazioni Della Fattorizzazione

Soluzione Di Un Sistema Lineare Ly = b Sistema T riangolare Inf eriore

−→

Ax = b LUx = b Ux = y Sistema T riangolare Superiore

Una volta fattorizzata A la soluzione del sistema si ottiene risolvendo i due sistemi triangolari.

Se si devono risolvere più sistemi lineari aventi la stessa matrice dei coefficienti, si fattorizza una sola volta A

e per ogni vettore b si risolvono i due sistemi triangolari. Calcolo Del Determinante Di A

det(A) = det(LU) = det(L) det(U) (Teorema Di Binet)

Sapendo che det(L) = 1 si avrà che: n (1) (2)

Y (n)

det(A) = det(LU) = det(U) = u = a a ... a

kk nn

11 22

k=1

4.4 Applicazioni Della Fattorizzazione Pt. 2 −1

La matrice inversa di una matrice A non singolare. è la matrice A tale che:

−1

A A = I

Si ricordi che I = E , E , ..., E , dove E sono vettori della base canonica.Quindi:

1 2 n i

−1

A = X , X , ..., X

1 2 n

A X = E

i i

Dove X sono le colonne di X che è la matrice inversa

i

Conoscendo la fattorizzazione di A basta risolvere gli n sistemi lineari, cioè:

L Y = E U X = Y i = 1, 2, ..., n

i i i i

4.5 MEG E Fattorizzazione LU

Il metodo di eliminazione gaussiana si basa sull’idea di ridurre il sistema Ax = b ad un sistema equivalente

della forma Ux=b, dove U è triangolare superiore e b è un nuovo termine noto. Questo sistema può essere

risolto con il metodo delle sostituzioni all’indietro.

(1) (1)

Indichiamo il sistema originario come A x = b . Per ottenere il sistema equivalente utilizzeremo il metodo

di Gauss.

Consideriamo una matrice A∈ R, non singolare, e supponiamo che l’elemento diagonale a sia non nullo.

11

Quindi: (1)

a i = 1, 2, ..., n

m = i1

i1 (1)

a

11

(1) (1)

dove a sono gli elementi di A . É possibile eliminare l’incognita x da tutte le righe successive alla prima

1

ij

sottraendo dalla riga i-esima con i = 2, 3, ..., n la prima riga moltiplicata per m , eseguendo la stessa

i1

operazione per il termine noto. In generale si avrà che:

(2) (1) (1)

−

a = a m a i = 2, 3, ..., n

i1

ij ij 1j

(2) (1) (1)

−

b = b m b i = 2, 3, ..., n

i1 1

i i

(1) (1)

Dove b sono le componenti di b si avrà un sistema:

i    

(1) (1) (1) (1)



 b

a a ... a x 1

11 12 1n 1

(2)

(2) (2) x

0 a ... a b

   

2 



22 2n 2

   

 

.

. . . . .

   

  = (2)

   



 .

. . . . .

   

 

   

 

.

. . . . .

   

 

   

(2) (2) (2)

x

0 a ... a b

n

nn n

n2 8

(2) (2)

Che indicheremo con A x = b equivalente a quello di partenza

In modo analogo, possiamo trasformare il sistema in modo da eliminare l’incognita x dalla righe i + 1, ..., n.

i

In generale si otterrà: (k) (k) ≤ ≤

A x = b 1 k n

(i) ̸ −

Assunto che a = 0 per i = 1, ..., k 1. É evidente che per k = n si otterrà un sistema triangolare superiore

ii

(n) (n)

A x = b 





 (1)

(1) (1) (1)   b

a a ... a x 1 1

11 12 1n (2)

(2) (2) x b

0 a ... a 





 2

  2

22 2n 





  

. .

. . . . 





   (3)

= 





  

.

0 . . . . 





   





  

. .

. . . . 





   





 (2)

(n) x b

0 0 ... a n n

nn (k)

(n)

Possiamo indicare con U la matrice triangolare superiore A . Gli a vengono detti elementi pivotiali e

kk

devono essere non nulli. Per evidenziare le formule che consentono di trasformare il sistema k-esimo in quello

kkk ̸

k+1-esimo, per k = 1, ..., n-1 si assume che a = 0 e definiamo il moltiplicatore:

(k)

a

m = i = k + 1, ..., n

ik

ik (k)

a kk

Quindi: (k+1) (k) (k)

−

a = a m a i, j = k + 1, ..., n

ik

ij ij kj

(k+1) (k) (k)

−

b = b m b i = k + 1, ..., n

ik

i i k

In generale (1) (

M A = A 2)

1 (2) (

M A = A 3)

2

( (2) (1)

A 3) = M A = M M A

2 2 1

...

n (1)

U = A = M M ...M A

n−1 n−2 1

Quindi si può scrivere: n (1)

U = A = (M M ...M )A

n−1 n−2 1

−1 −1 (1)

(M M ...M ) U = (M M ...M ) (M M ...M )A

n−1 n−2 1 n−1 n−2 1 n−1 n−2 1

−1 (1)

(M M ...M ) U = A

n−1 n−2 1

−1

Ponendo (M M ...M ) = L si ottiene:

n−1 n−2 1 (1)

LU = A

(Esempio Da Pagina 17 Slides 4 )

4.6 Matrice Simmetrica Definita Positiva

∈ M⊣⊔(n, R) ∈ R

Sia A n, una matrice di ordine n a coefficienti reali e sia x un generico vettore riga. La

T

A

matrice è definita positiva se il prodotto xAx è un numero positivo per ogni x diverso dal vettore nullo.

T T n

∀x ∈ R ̸

A = A e xAx > 0 , x = 0

4.7 Criterio Di Sylvester

Una matrice simmetrica è definita positiva se e solo se det(A ) per k = 1,2,...,n e dove A sono le sottomatrici

k k

principali dell’ordine k. 9

4.8 Fattorizzazione Di Cholesky

T

Data A = A definita positiva, si avrà che: T

A = L L

Per questo algoritmo basta fare il prodotto e uguagliare il risultato all’elemento a

ij

Formule Generali: v

 j−1

u

 u X

 2

−

a l

l =

 t jj

jj

 jk

 k=1

j−1

P

−

a l l

 jj ik jk

 k=1

 l =

 ij

 l jj

(Esempio Da Pagina 22 Slides 4 )

(Codice Pagina 25 Slides 4 )

4.9 Matrici Sparse

Le matrici sparse sono matrici con predominanza di elementi nulli. Non esiste una definizione rigorosa di

sparsità, la precedente è solo qualitativa.

La sp