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