Decomposizione LU
# 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'$

    $Ux=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:

    $Ax=LUx=b$

così si può riutilizzare la decomposizione se si vuole 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) si costruisce 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"). Si supponga 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, si può dedurre che tutte le $T_{i}^{-1}$ sono triangolari inferiori (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.

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

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

## Applicazioni

### Matrici inverse

La fattorizzazione $PA=LU$ viene anche usata per calcolare la matrice inversa di $A$. Infatti:

    $PA=LU\Rightarrow A=P^{-1}LU$

da cui:

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

### Determinante

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

$A=P^{-1}LU\Rightarrow \det(A)=\det(P^{-1}LU)$

quindi per il teorema di Binet:

$\det(A)=\det(P^{-1})\det(L)\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}}$, si ottiene che:

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

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

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

ma sapendo anche che i termini sulla diagonale principale di $L$ sono tutti $1$, quindi si può infine concludere:

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

dove $S$ indica il numero di scambi di riga effettuati nel processo (implicitamente 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$.

