SISTEMI LINEARI
(le slide guardale lo stesso)

m equazioni in n incognite

Ax=b

x= vettore incognite

b= vettore termini noti

A= matrice coefficienti

n° operazioni per calcolare b

m*n operazioni

m(n-1) addizioni

colonne:
c_j= A e_j ^ (n)

righe:
r_i^T= (e_i^(m))^T A

elementi:
a_ij= (e_i^(m) )^T A e_j^(n)

vettore base canonica:
e_k= [0 .. 1 .. 0]^T

Non sempre, fissato un vettore b
di dimensione m, si può trovare
un vettore x tale che Ax=b

b=0 <=> sistema omogeneo

Algebra Lineare

Partizionamento

decomposizione matrice
in sottomatrici

Matrice a blocchi

A_ij sotto matrice

Trasposta

inverto righe e colonne

Coniugata

cambiando di segno la parte immaginaria

Aggiunta

trasposta della matrice coniugata

A^T

A con la barra sopra

A^*

Range

tutti i vettori y che posso
ottenere moltiplicando A*x

ran(A)

Rango

dimensione di ran(A)

rank(A)

Matrice Non Singolare

A è non singolare se rank(A)=n

se è solo se b appartiene a ran(A)
ammette soluzione unica se rank(A)=n

x=A^-1 b

Matrice Simmetrica

A=A^T

antisimmetrica A= - A^T

Matrice Hermitiana

A=A*

antihermitiana A= - A *

Matrice Ortogonale

A^-1 = A^T

Matrice Unitaria

A^-1 = A*

Matrice definita positiva

x^T A x > 0,
Ogni x diverso da 0

Determinante

sum (-1)^(i+1) a_i1 det(A_i1)

A è non singolare se det(A) diverso da 0

Autovalore

lambda tale che esista x (autovettore)
tale che Ax = lambda x

Spettro

insieme autovalori

raggio spettrale: max valore assoluto di lambda

Norme

||x||_p := (sum |xi|^p)^(1/p)

Norma indotta su matrice

||A|| := max ||A_x||
||x||=1

Sistemi Lineari Quadrati

n equazioni in n incognite

Risoluzione Numerica

Metodi Diretti

Metodi Iterativi

trasformazione sistema in uno equivalente

in assenza di errori di arrotondamento
forniscono la soluzione esatta

distruggono sparsità matrice

splitting matrice e poi op. ricorsivamente fino ad ottenere un approssimazione della soluzione esatta

Soluzione ottenuta come limite di una successione

sfruttano sparsità matrice dei coefficienti

Fattorizzazione

matrici diagonali

matrici triangolari

matrici ortogonali

Fattorizzazione LU

Metodo di Eliminazione
di Gauss

da Ax=b
a Ly=b
e Ux=y

L matr triang inf diagonale 1
U matr triang sup

Se A=LU esiste e A è non singolare,
allora essa è unica

se A è non singolare, A=LU esiste se e solo se tutti i minori principali di A sono non nulli

non completamente generale
instabilità numerica

soluzione: PIVOTING

scambio tra righe o colonne

se A è nonsingolare, allora esiste pivot tale che PA=LU

CASI PARTICOLARI

matrici a diagonale dominante

matrici simmetriche definite positive

ogni elemento diagonale è maggiore della somma degli altri elementi sulla stessa riga(colonna)

A=A^T e per ogni x diverso dal vettore nullo
x^T A x >0

tutte le sottomatrici principali di una matrice sdp sono sdp

Metodi Iterativi
Stazionari

successioni vettori
x(k) t.c. x(k+1)=Qx(k)+d

Metodo di Jacobi

Metodo di Gauss Seidel

Convergenza: e(k) converge a 0
se esiste una norma naturale
per l quale ||Q||<1

e(k) converge se e solo se la matrice di iterazione Q è convergente

raggio spettrale<1
(più vicino a 0 più velocemente converge)

Criteri di Arresto

criterio di salvaguardia

criterio di controllo sul residuo

criterio di controllo su due iterative consecutive

fisso n max di iterazioni

si controlla ||b-Ax(k)||/||b||<epsilon

si controlla ||x(k)-x(k-1)||<epsilon

A=D-L-U
D matr diag
L matr strett triang inf
U matr strett triang sup

si risolve Mx(k+1)=Nx(k)+b
con M=D e N = U+L

A=D-L-U
D matr diag
L strett triang inf
U strett triang sup

si risolve Mx(k+1)=Nx(k)+b
con M=D-L e N=U

se A è diagonale dominante.
metodo di Jacobi converge sempre

Se A è simmetrica definita positiva
Gauss Seidel converge