SISTEMI LINEARI
Metodi diretti
Sistemi lineari
Ax = b, A ∈ R n×n , b ∈ R n b INPUT
x OUTPUT
A relazione funzionale
non ambigua ⇔ det(A) 6= 0 ( ∃ un’unica soluzione) Se det (A) = 0
rank(A) = rank(A|b) ⇒ infinite soluzioni
Se rank(A) 6= rank(A|b) ⇒ nessuna soluzione.
(Esercizio 1)
Condizionamento
Cosa accade quando i dati di ingresso (A e/o b) del problema sono affetti da errore?
Caso ”piu’ semplice“ (per la teoria): errore nel termine noto b 7→ ˜b = b + δb, Ax = b V A˜ x = ˜b
La soluzione non è più x ma x = x + δx. ˜ Si dimostra che, scelta una norma,
||δx||
||x|| ≤ ||A|| ||A −1 || ||δb||
||b||
||δx||
||x|| errore relativo sulla soluzione (errore propagato)
||δb||
||b|| errore relativo sui dati iniziali (errore inerente)
K(A) = ||A|| ||A −1 || indice di condizionamento
Condizionamento
Più in generale, se A = A + δA ˜b = b + δb ˜ si ha che l’errore relativo sulla soluzione è
||δx||
||x|| ≤ 2||A|| ||A −1 || µ ||δA||
||A|| + ||δb||
||b||
¶
Esempio
» A=[1 1; 0.999 1]; b=[2 ;1.999]; x=A \ b
perturbiamo la matrice e calcoliamo la soluzione del sistema perturbato
» dA=0.00024*[1 1; -1 -1]; B=A+dA ; x1=B \ b Calcoliamo l’errore relativo sui dati e sulla soluzione
» errdati=norm(dA,inf)/norm(A,inf)
» errsol=norm(x-x1,inf)/norm(x,inf)
A un errore iniziale del 0.024% corrisponde un errore del 95.9% sulla
soluzione (esercizi 2,3)
Condizionamento
Comandi utili
Calcolare il rango di una matrice
» rank(A)
Calcolare una norma di matrice o vettore
» norm(A,tipo) tipo=2,1,inf calcolo dell’inversa di A
» inv(A)
calcolo dell’indice di condizionamento in norma 2 di A
» cond(A)
Esempi di matrici malcondizionate
matrici di Hilbert:
H = ³
a i,j ´
, a i,j = 1
i + j − 1 , i, j = 1, . . . , n
»H=hilb(n)
Calcolare l’indice di condizionamento delle matrici di Hilbert di
ordine 4 e 10
Esempi di matrici malcondizionate
matrice di Vandermond associata a un vettore v = [x 1 , · · · , x n ]
V =
x n 1 −1 x n 1 −2 . x 1 1 x n−1 2 x n−2 2 . x 2 1
. . . . .
. . . . .
x n n −1 x n n −2 . x n 1
V i,j = v i n−j , i, j = 1, · · · , n
»vander(v)
Calcolare l’indice di condizionamento in norma infinito delle
matrici di Vandermond associate ai vettori v 1 = [2, 3, 4] e
v 2 = [2, 2.05, 4]
Metodi diretti
Si usano per matrici piene
Metodo di eliminazione gaussiana
A =
• • • •
• • • •
• • • •
• • • •
→
• • • • 0 • • • 0 • • • 0 • • •
· · · → U =
• • • • 0 • • • 0 0 • • 0 0 0 •
Il metodo si arresta quando ci sono elementi pivotali nulli Il metodo è instabile.
E’ necessaria una strategia pivotale per renderlo stabile (esercizi 4,5)
Metodi diretti
Pivoting parziale pivoting totale
.. ↓ ... ..
0| • • • 0| .. ↓↑ ..
0| • • •
.. .. ¿ ..
0| • • • 0| .. ↓↑ ..
0| • • •
Il pivoting parziale risulta poco costoso e fornisce generalmente una soluzione soddisfacente (in termini di stabilità)
Il pivoting totale e più costoso ma assicura la stabilità Il metodo di eliminazione gaussiana senza pivoting, è
numericamente stabile per matrici simmetriche a diagonale dominante e per matrici simmetriche definite positive
Costo computazionale O( n 3
3)
Metodi diretti: fattorizzazione LU
Il metodo di Gauss (con pivoting parziale) è una successione finita di trasformazioni della matrice A e del vettore b .
A ⇒ U P A = LU
P matrice che tiene conto degli scambi di righe
L matrice triangolare inferiore: contiene i moltiplicatori
Ax = b ⇒ P Ax = P b ⇒ LU x = P b ⇒ Ly = P b U x = y
Fattorizzazione LU è utile quando si devono risolvere tanti sistemi con la stessa matrice A e termini noti diversi: faccio la
decomposizione una sola volta (è la parte più costosa!) e poi risolvo
tanti sistemi triangolari ...(es: calcolo dell’inversa di A, esercizio 6)
Metodi diretti: fattorizzazione LU
la funzione MATLAB che esegue la fattorizzazione LU (con pivoting parziale) è
» [L,U,P]=lu(A) Divisione a sinistra
L’operatore \ calcola automaticamente la soluzione x del sistema Ax = b con il metodo di eliminazione gaussiana
» x=A \ b
La function "divisione a sinistra e’ molto sofisticata...leggere l’help (mldivide \ , mrdivide / )
Per esempio nei casi particolari di sistemi con matrice A triangolare
inferiore o superiore risolve con il metodo di sostituzione in avanti o
all’ indietro rispettivamente....
Metodi diretti: fattorizzazione di Cholesky
Se A è simmetrica definita positiva
A = L L T L matrice triangolare inferiore
Il comando matlab che fornisce la fattorizzazione di Cholesky è
» L=chol(A)
costo computazionale O( n 6
3)
Raffinamento iterativo
Ax = b ⇒ ¯ A¯ x = ¯b A, ¯ ¯ x, ¯b rappresentazioni macchina di A, b, x.
Sappiamo che detta x 0 la soluzione ottenuta con il metodo di Gauss si ha
r 0 = ¯b − ¯ Ax 0 ⇒ ¯ Ae 0 = r 0 dove e 0 = ¯ x − x 0
Quindi x 1 = x 0 + e 0 dovrebbe essere più vicina a x ¯ (se il sistema è ben condizionato).
Posso iterare il procedimento iterativo. Questo converge
rapidamente a x ¯ che è la massima precisione raggiungibile partendo
con i dati A ¯ e ¯b.
Raffinamento iterativo
Il raffinamento iterativo può essere utile per depurare
l’approssimazione x 0 , ottenuta con Gauss, dagli errori introdotti dal metodo stesso dovuti a una non perfetta stabilità.
Attenzione: per non perdere cifre significative, il residuo DEVE essere calcolato con una precisione doppia. (Svantaggio: aggravio dei costi computazionali)
Si rivela molto utile quando si lavora in precisione singola
Matlab lavora in precisione doppia. È possibile definire le variabili in singola precisione con il comando single
»A=single([ 5 7 6 5; 7 10 8 7; 6 8 10 9; 5 7 9 10]);
»b=single([23;32;33;31])
Tutte le operazioni fatte su A e b saranno fatte in singola precisione.
Per convertire una variabile dalla precisione singola alla doppia si
usa il comando double
Raffinamento iterativo
Come fare con matlab a calcolare il residuo con una precisione doppia, ovvero con 32 cifre?
Si può usare il comando vpa variable-precision arithmetic per calcolare una espressione con d cifre decimali. Ogni elemento del risultato è una espressione simbolica
» digits(32)
» vpa( ¯b − ¯ A ∗ x 0 )
Attenzione, tornare alle 16 cifre impostando
» digits(16)
Esercizio. Applicare il procedimento di raffinamento al sistema
5 7 6 5
7 10 8 7 6 8 10 9 5 7 9 10
=
23 32 33 31
Matrici sparse: effetto Fill in
Consideriamo una matrice A sparsa ovvero con un 70% − 80% di
elementi nulli. Cosa accade quando calcoliamo la fattorizzazione LU di A ?
Le matrici L e U sono molto piu’ piene di A : si perdono i vantaggi della sparsità avendo una occupazione maggiore di memoria
(esercizio 8).
0 50 100
0
20
40
60
80
100
nz = 398
0 50 100
0
20
40
60
80
100
nz = 5198
