Fattorizzazione LU

Il processo di fattorizzazione consiste nel trovare una scomposizione della matrice dei coefficienti $A$ in due matrici $L$ ed $U$ in modo che sia $LU = A$. Per fare ciò si sottraggono i multipli della prima equazione del sistema dalle altre equazioni così che la prima variabile sia rimossa da quelle equazioni. Si sottraggono i multipli della seconda equazione dalla terza e dalle successive così che la prima e la seconda variabile siano rimosse. Si itera il procedimento fino a quando la matrice non assume la forma triangolare superiore, si arriva così alla matrice $U$. La matrice $L$ è composta da moltiplicatori che causano l' eliminazione delle variabili. L' algoritmo può essere facilmente descritto in modo induttivo su $n$. Se $n = 1$ si sceglie $L = 1$ ed $U = a_{1,1}$. Per $n > 1$ si taglia $A$ in quattro parti

$$A = \left( \begin{array}{c\vert ccc} a_{1,1} & a_{1,2} & \c... ...ght) = \begin{pmatrix} a_{1,1} & w^T \\ v & A' \end{pmatrix}$$

dove $v$ è un vettore colonna e $w^T$ è un vettore riga, entrambi di dimensione $(n-1)$. $A'$ è una matrice $(n-1)\times(n-1)$. È facile verificare che $A$ ammette la seguente scomposizione

$$A = \begin{pmatrix} a_{1,1} & w^T \\ v & A' \end{pmatrix}= \begi... ...in{pmatrix} a_{1,1} & w^T \\ \boldsymbol{0} & A'- vw^T/a_{1,1} \end{pmatrix}.$$

Si intende con $\boldsymbol 0$ nella prima e nella seconda matrice, rispettivamente, vettori riga e colonna di dimensione $(n-1)$, che hanno tutti gli elementi uguali a zero.

Supponendo vero questo metodo per la matrice $A'-vw^T/a_{1,1}$ di dimensioni $(n-1)\times(n-1)$, si dimostra per $A$ di dimensioni $n \times n$. Siano $L'$ e $U'$ le matrici ottenute dalla scomposizione della sottomatrice $A'-vw^T/a_{1,1}$, si ha

$$\begin{split}A & = \begin{pmatrix}1 & \boldsymbol{0} \\ v/a_{... ...w^T \\ \boldsymbol{0} & U' \end{pmatrix}\\ & = LU . \end{split}$$ (2.20)

Poiché $L'$ è triangolare inferiore unitaria, anche $L$ lo è. Poiché $U'$ è triangolare superiore, anche $U$ lo è. Si ottiene così ottenuto una fattorizzazione LU per la matrice $A$.

Osserviamo che se l' elemento $a_{1,1}$ fosse uguale a zero questo metodo non funzionerebbe, perché si dividerebbe per zero, non si può applicare, inoltre, se l' elemento $a_{1,1}'$ della matrice $A'-vw^T/a_{1,1}$ fosse zero e così via. In questi casi non è possibile applicare la fattorizzazione LU. Vedremmo successivamente che la la classe di matrici a cui verrà applicata la fattorizzazione presenta delle caratteristiche che garantiscono che non si verifichi mai questo inconveniente. Gli elementi per cui si divide durante la fattorizzazione LU sono chiamati perni. Vengono scelti come perni gli elementi sulla diagonale perchè nel nostro caso sono i valori maggiori di ogni riga; essi fanno si che gli errori di arrotondamento siano minori e di conseguenza aumenti la stabilità.

Il codice della fattorizzazione LU è riportato nel cap .