Il metodo di eliminazione di Gauss

Adesso andremo a compiere la vera e propria fattorizzazione. Quello che faremo sarà trovare una matrice triangolare superiore ottenendola da $A$ attraverso opportune trasformazioni. Innanzitutto poniamo

$$A= \left( \begin{array}{ccc} a_{11}^{(1)} & \cdots & a_{1... ... & \cdots & a_{nn}^{(1)} \end{array} \right) \equiv A^{(1)}$$

dove con l'indice $(1)$ stabiliamo l'ultimo passaggio in cui quel determinato elemento della matrice è stato modificato. In modo iterativo, al passo i-esimo ci concentreremo sulla colonna i-esima ed il compito del passo corrente sarà quello di fare in modo che quella colonna diventi la colonna di una matrice triangolare superiore e quindi annulli gli elementi dall'(i+1)-esima posizione in poi.

Al primo passo si devono azzerare gli elementi $a_{21},\cdots,a_{n1}$, quindi se $a_{11} \neq 0$ possiamo definire

$$g_1=\frac{1}{a_{11}}{(0,a_{21}^{(1)}, \cdots , a_{n1}^{(1)})}^T$$

$$L_1=I-g_1e_1^T$$

tali che

$$L_1 \left( \begin{array}{c} a_{11}^{(1)} \\ \vdots \\ ... ...^{(1)} \\ 0\\ \vdots \\ 0 \end{array} \right)\mbox{.}$$

Possiamo adesso moltiplicare a sinistra la matrice di partenza $A$ per $L_1$ per ottenere

$$L_1A= \left( \begin{array}{cccc} a_{11}^{(1)} & a_{12}^{(... ... \cdots & a_{nn}^{(2)} \end{array} \right) \equiv A^{(2)}$$

Come si può vedere l'indice all'interno della sottomatrice di $A$ è stato aggiornato: infatti applicando la matrice $L_1$ ad $A$ gli elementi sulla prima riga rimangono inalterati (il vettore $g_1$ è stato scelto in modo che lasciasse inalterata proprio la prima componente del vettore) e si ottiene l'annullamento degli elementi sotto la diagonale della prima colonna; come effetto secondario otteniamo la modifica degli elementi della sottomatrice di $A$: infatti mentre per costruzione della matrice $L_1$ la prima colonna viene modificata come volevamo, applicando detta matrice alle altre colonne, queste verranno modificate senza un preciso schema, da qui l'aggiornamento dell'indice. Infatti, sia $v$ un vettore qualsiasi:

$$L_1v= \left( \begin{array}{cccc} 1 & & & \\ \ast & \ddot... ...y}{c} v_1\\ \ast\\ \vdots\\ \ast \end{array} \right)$$

dove con gli elementi $\ast$ intendiamo degli elementi che non vogliamo caratterizzare ma solitamente diversi da quelli precedenti.

Abbiamo così concluso il primo passo.

Durante il generico passo i-esimo vediamo come prosegue l'algoritmo. Se $a_{ii} \neq 0$ possiamo definire

$$g_i=\frac{1}{a_{ii}^{(i)}}{(\underbrace{0\cdots0}_{i},a_{i+1,i}^{(i)}, \cdots , a_{ni}^{(i)})}^T$$

$$L_i=I-g_ie_i^T$$

dai quali possiamo ottenere:

$$L_iL_{i-1}\cdots L_1A=\left( \begin{array}{cccccccc} a_{1... ... & a_{nn}^{(i+1)} \\ \end{array} \right) \equiv A^{(i+1)}$$

Dopo $n-1$ passi otteniamo:

$$L_{n-1}\cdots L_i\cdots L_1A=\left( \begin{array}{cccccc} ... ..._{nn}^{(n)} \\ \end{array} \right) \equiv A^{(n)} \equiv U$$

Abbiamo dunque ottenuto $L_{n-1}\cdots L_1A=U$, con le matrici $L_i$ triangolari inferiori a diagonale unitaria; se chiamiamo $L^{-1}=L_{n-1}\cdots L_1$, $L$ sarà anch'essa una matrice triangolare inferiore a diagonale unitaria e quindi possiamo scrivere:

$$L^{-1}A=U \quad \rightarrow \quad LL^{-1}A=LU \quad \rightarrow \quad A=LU$$

la fattorizzazione che cercavamo.