ESE_CN_Informatica

1. Implementazione dei metodi diretti per sistemi lineari :
fattorizzazione LU ;
pivoting

Il metodo di eliminazione gaussiana, per la risoluzione di un sistema di equazioni lineari, si basa sull'idea di ridurre il sistema A*x = b in un sistema equivalente (cioè avente soluzione identica) della forma U*x = y , dove U è una matrice triangolare superiore , e di risolvere questo sistema mediante sostituzioni all'indietro. Per rendersene conto, leggere ed eseguire il seguente m-file: eliminazione_gaussiana.m

Vediamo con un esempio come l'algoritmo appena mostrato sia equivalente ad una fattorizzazione A=L*U , seguita dalla soluzione dei due sistemi triangolari (rispettivamente inferiore e superiore) L*y=b e U*x=y . Infatti, consideriamo il sistema A*x = b , e:

sostituiamo ad A la sua fattorizzazione L*U , ovvero vale A = L*U, e quindi il sistema diventa: L*U*x = b ;
poniamo U*x = y , che è un sistema lineare a matrice triangolare superiore , da cui risulta L*y = b , che è un sistema lineare a matrice triangolare superiore ;
ci ricaviamo y , conoscendo L e b , risolvendo il sistema lineare L*y = b mediante semplici sostituzioni in avanti;
ci ricaviamo x , conoscendo U ed y , risolvendo il sistema lineare U*x = y mediante semplici sostituzioni all'indietro .

Leggere ed eseguire il seguente m-file: EG_equiv_fattLU.m

Esistono varie implementazioni possibili della fattorizzazione LU . Ad esempio, le implementazioni degli algoritmi "kji" e "ijk" sono contenute nel file fattorizzazioni_LU_e_Cholesky.m .

Esercizio: guardare il codice sorgente delle due fattorizzazioni "kji" e "ijk" nel file appena citato, "fattorizzazioni_LU_e_Cholesky.m"; sapreste dire quale dei due accede per righe e quale per colonne ?

La tecnica del "pivoting":

Per evitare di trovarsi un elemento pivotale nullo o molto piccolo, entrambe situazioni da evitare, in certe matrici è necessario applicare la tecnica del "pivoting", che vediamo spiegata nella figura seguente, rispettivamente per il pivoting parizale sulle righe (sinistra) e per il pivoting totale (destra) :

dove l'elemento (k,k) è il pivot "naturale", mentre (ipr,k) e (ipr,ipq) sono quelli determinati per ricerca del massimo valore nelle rispettive zone colorate di rosso:

per il pivoting parziale per righe la zona in rosso è la porzione di colonna di indici (k:n,k) ;
per il pivoting totale la zona in rosso è la sotto-matrice di indici (k:n,k:n) .

Una volta determinato l'elemento pivotale , si procede allo scambio di righe/colonne :

si scambiano le righe "k" ed "ipr" nel pivoting parziale per righe ;
si scambiano le righe "k" ed "ipr" e le colonne "k" ed "ipq" nel pivoting totale ;

Leggere ed eseguire il seguente m-file che implementa il pivoting parziale (sulle righe) : LU_con_pivoting_su_righe.m

Esercizio: scrivere un programma Matlab/Octave che esegua la fattorizzazione LU con il pivoting totale e provarlo su una matrice piccola (ad es. 5x5, in modo da poterla visualizzare facilmente) . Come verifica della correttezza dell'algoritmo implementato nel programma, si può verificare che 'sum(sum(abs(A - L*U)))' dia un valore molto piccolo .