Fattorizzazione LU

La fattorizzazione LU consiste nello scomporre una matrice A nel prodotto du due matrici, L triangolare inferiore ed U triangolare superiore con la particolaritá che la matrice L ha sulla diagonale tutti 1; se esiste tale fattorizzazione è unica. Una volta fattorizzata A basta risolvere il seguente sistema lineare per ottenere la soluzione

$$\left\{ \begin{array}{ccc} L\underline{y}&=&\underline{b}\\ U\underline{x}&=&\underline{y}\\ \end{array}\right.$$

Se la matrice A è di ordine $n$ allora l'algoritmo consiste di $n-1$ passi ognuno dei quali annulla gli elementi di una colonna (quella corrispondente al numero del passo) sotto la diagonale principale e lascia inalterato il ``lavoro svolto'' ai passi precedenti; tutto questo si ottiene premoltiplicando a sinistra A per delle matrici con struttura analoga alla L e chiamata matrici elementari di Gauss . Descrizione dell'algoritmo: con $A^k$ viene indicata la matrice $A$ al passo k-esimo e con $a_{i\:j}^k$ l'ememento in riga $i$,in colonna $j$ ed al passo $k$ della matrice $A$. L'algoritmo parte con

$$A=A^1= \left( \begin{array}{cccc} a_{1\:1}^1 &a_{1\:2}^1 & \... ...\:1}^1 &a_{n\:2}^1 & \ldots & a_{n\:n}^1\\ \end{array}\right)$$

e ricava $A^2=L^1A$ dove adesso $A^2$ è

$$\left( \begin{array}{cccc} a_{1\:1}^1 &a_{1\:2}^1 & \ldots &... ... \\ 0 &a_{n\:2}^2 & \ldots & a_{n\:n}^2\\ \end{array}\right)$$

si nota che adesso nelle righe inferiori alla prima compare l'indice 2 in alto e questo significa che l'algoritmo non modifica quello che era stato fatto ai passi precedenti e che via via si vanno a modificare le righe inferiori della matrice, lasciando inalterate le altre. Al passo i-esimo si ricava $A^{i+1}$ come i prodotto $L^i A^i$ dove $A^i = L_{i-1}\cdots L_2 L_1 A$. Di queste matrici $L_{i}$ ce ne sono esattamente $n-1$ e la loro forma è del tipo

$$L_i = I - \underline{g}_i \underline{e}_i^T$$

dove $\underline{e}_i^T$ indica nel modo usuale l'i-esimo vettore della base canonica di $R^n$ trasposto e $\underline{g}_i$ indica l'i-esimo vettore di Gauss definito come

$$\underline{g}_i =\frac{1}{a_{i\:i}^i} ( \underbrace{0\ldots0}_{i} \: a_{i+1\:i}^i\:\ldots \: a_{n\:i}^i )^T$$

Se indichiamo con $L^{-1}$ il prodotto $L_{i-1}\cdots L_2 L_1$ si ha proporio che $A=LU$, infatti si ha che l'inversa di $L^i$ è $I - \underline{g}_i \underline{e}_i^T$ ed è triangolare inferiore con tutti 1 sulla diagonale, e quindi lo è anche il loro prodotto. L' algoritmo al passo i-esimo modifica la matrice nel seguente modo

$$\left\{ \begin{array}{lll r} a_{k\:i}^{i+1}&=&\frac{a_{k\:i}... ...}^{i+1}\cdot a_{i\:j}^{i}& j=i+1\ldots n\\ \end{array}\right.$$

e poichè vengono annullati $n-i$ elementi sotto la diagonale, le loro posizioni possono essege occupare dalle componenti significative del vettore $\underline{g}_i$.