Decomposizione LU

In algebra lineare una decomposizione LU, o decomposizione LUP o decomposizione di Doolittle è una fattorizzazione di una matrice in una matrice triangolare inferiore $L$, una matrice triangolare superiore $U$ e una matrice di permutazione $P$. Questa decomposizione è usata in analisi numerica per risolvere un sistema di equazioni lineari, per calcolare l'inversa di una matrice o per calcolare il determinante di una matrice.

Definizione

Sia $A$ una matrice invertibile. Allora $A$ può essere decomposta come

$PA = LU$

dove $P$ è una matrice di permutazione, $L$ è una matrice triangolare inferiore a diagonale unitaria ($l_{ii} = 1, \forall i$) e $U$ è una matrice triangolare superiore.

Idea principale

La decomposizione $LU$ è simile all'algoritmo di Gauss. Nell'eliminazione gaussiana si prova a risolvere l'equazione matriciale

$\mathbf{A} \mathbf{x} = \mathbf{b}$

Il processo di eliminazione produce una matrice triangolare superiore $U$ e trasforma il vettore $b$ in $b'$

$U x = b'$

Poiché $U$ è una matrice triangolare superiore, questo sistema di equazioni si può risolvere facilmente tramite sostituzione all'indietro.

Durante la decomposizione $LU$, però, $b$ non è trasformato e l'equazione può essere scritta come

$A x = L U x = b$

così possiamo riusare la decomposizione se vogliamo risolvere lo stesso sistema per un differente $b$.

Nel caso più generale, nel quale la fattorizzazione della matrice comprende anche l'utilizzo di scambi di riga nella matrice, viene introdotta anche una matrice di permutazione $P$, ed il sistema diventa:

$\begin{cases} Ly=Pb\\ Ux=y \end{cases}$

La risoluzione di questo sistema permette la determinazione del vettore $x$ cercato.

Algoritmo

Applicando delle serie di trasformazioni elementari di matrice (cioè moltiplicazioni di $A$ a sinistra) costruiamo una matrice triangolare superiore $U$ che parte da $A$. Questo metodo è chiamato metodo di Gauss. Queste trasformazioni elementari di matrice sono tutte delle trasformazioni lineari di tipo combinatorio (il terzo tipo elencato nella voce "Matrice elementare"). Supponiamo che T sia il prodotto di N trasformazioni $T_N \dots T_2 T_1=T$, allora la matrice triangolare superiore è:

$TA=T_N\dots T_2 T_1 A =\colon U.$

L'inversa della matrice $T$ è:

$T^{-1}=T_1^{-1}T_2^{-1}\dots T_N^{-1}$

Come l'algoritmo di Gauss usa solo la terza forma dei tre tipi di trasformazioni elementari di matrice rendendo $A$ triangolare superiore, possiamo dedurre che tutte le $T_i^{-1}$ sono triangolari (vedi trasformazioni elementari di matrice). Essendo un prodotto di $T_i^{-1}$ anche:

$T^{-1}=T_1^{-1}T_2^{-1}\dots T_N^{-1}=\colon L$

è triangolare inferiore.

Abbiamo quindi la decomposizione della matrice $A$ nel prodotto di $L$ e $U$:

$LU=T^{-1}TA=A.$

Applicazioni

Matrici inverse

La fattorizzazione $P \cdot A = L \cdot U$ viene anche usata per calcolare la matrice inversa di $A$. Infatti,

$P \cdot A = L \cdot U \Rightarrow A = P^{-1} \cdot L \cdot U$

da cui:

$A^{-1} = (P^{-1} \cdot L \cdot U)^{-1} = U^{-1} \cdot L^{-1} \cdot P$

Determinante

Un altro utilizzo di questa decomposizione è per il calcolo del determinante della matrice $A$. Infatti,

$A = P^{-1} \cdot L \cdot U \Rightarrow \det(A) = \det(P^{-1} \cdot L \cdot U)$

quindi per il teorema di Binet:

$\det(A) = \det(P^{-1}) \cdot \det(L) \cdot \det(U)$

Sapendo che il determinante di una matrice di permutazione vale 1 se questa corrisponde ad un numero pari di permutazioni, -1 altrimenti, e che $\det A^{-1} = \frac{1}{\det A}$, otteniamo che:

$\det(A) = (-1)^S \cdot \det(L) \cdot \det(U)$

Sapendo poi che il determinante di una matrice triangolare è dato dal prodotto dei termini sulla sua diagonale principale, abbiamo che:

$\det(A)=\left(-1\right)^{S}\cdot\prod_{i=1}^{n}{u_{ii} \cdot l_{ii}}$

ma sappiamo anche che i termini sulla diagonale principale di $L$ sono tutti 1, quindi possiamo infine concludere:

$\det(A)=\left(-1\right)^{S}\cdot\prod_{i=1}^{n}u_{ii}$

dove $S$ indica il numero di scambi di riga effettuati nel processo (indicati nella matrice $P$) ed i termini $u_{ij}$ e $l_{ij}$ indicano il termine in riga $i$ e colonna $j$ rispettivamente delle matrici $U$ e $L$.

Voci correlate

• Analisi numerica
• Decomposizione di Cholesky
• Decomposizione di Crout

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica