Fill-in di una matrice

(1)

Fill-in di una matrice

Costruire la matrice A cos`ı definita (n = 10):

aii = 3 per i = 2, ..., n a1j = 1 per j = 1, ..., n a_{i 1}= 1 per i = 1, ..., n

Richiamare la fattorizzazione LU con pivotazione e visualizzare il pattern di A, di L, di U e di P (matrice di pivotazione) con il comando spy:

A =[ . . .];

f i g u r e( 1 ) ; clf spy( A )

[ L , U , P ]= l u f a c t ( A , 1 ) ;

©Paola Gervasio (UniBS) - Calcolo Scientifico 1

(2)

I pattern delle matrici

0 5 10

nz = 28 0

2 4 6 8 10

matrice A

0 5 10

nz = 54 0

2 4 6 8 10

matrice L

0 5 10

nz = 54 0

2 4 6 8 10

matrice U

0 5 10

nz = 10 0

2 4 6 8 10

matrice P

(3)

Fill-in di matrice

La fattorizzazione LU (ma anche il MEG) genera elementi non nulli in L e U anche dove il corrispondente elemento di A era nullo.

Questo fenomeno si chiamafill-in.

Anche se la matrice A ha pochi elementi non nulli, le matrici L e U possono avere una densit`a molto elevata.

Tutti i metodi diretti agiscono sulla matrice, trasformandola in una matrice pi`u densa.

Al contrario i metodi iterativi non modificano la matrice del sistema, quindi quando si utilizzano i metodi iterativi non si verifica il fill-in.

(4)

Come evitare il fill-in

Esistono metodi di riordinamento di righe e colonne di una matrice da applicare prima di svolgere la fattorizzazione LU o il MEG con lo scopo di minimizzare il fill-in.

Esempio: colpermcolperm costruisce una permutazione delle colonne in modo da spostare le righe e colonne di A con il maggior numero di elementi verso il fondo della matrice.

A =. . . % stessa matrice di prima

q = c o l p e r m( A ); % q e’ un vettore che contiene

% una permutazione delle colonne Ap = A ( q , q ); % matrice permutata spy( Ap )

[ L , U , P ]= l u f a c t ( Ap , 1 ) ;

(5)

I pattern delle matrici dopo la permutazione

0 5 10

nz = 28 0

2 4 6 8 10

matrice Ap

0 5 10

nz = 19 0

2 4 6 8 10

matrice L

0 5 10

nz = 19 0

2 4 6 8 10

matrice U

0 5 10

nz = 10 0

2 4 6 8 10

matrice P