Metodo di eliminazione di Gauss

Si riporta di seguito la risoluzione di un sistema di equazioni lineari usando il metodo di fattorizzazione LU, chiamato anche eliminazione di Gauss [12]. Si applicherà questo metodo per la soluzione dell' equazione ().

Un approccio per risolvere il sistema () di $n$ equazioni in $n$ incognite consiste nel calcolare $A^{-1}$ e moltiplicare l' equazione per $A^{-1}$ ottenendo $A^{-1}Ax = A^{-1}b$, in questo modo $x = A^{-1}b$. Questo metodo ha problemi di instabilità numerica, gli errori di arrotondamento tendono ad accumularsi esageratamente quando viene usata la rappresentazione in virgola mobile dei numeri al posto dei numeri reali ideali. Basti pensare all' equazione lineare $7x = 21$ (la cui soluzione è $x = 3$) con il calcolo dell' inversa $1/7$ si ottiene la soluzione $x = 1/7\;21 = 0.142857\;21 = 2.999997$. Fortunatamente la fattorizzazione LU non presenta questi problemi e risulta molto vantaggiosa in termini computazionali.

L' idea che sta dietro la fattorizzazione LU consiste nel trovare due matrici $n \times n$ chiamate $L$ ed $U$ tali che $LU = A$, dove $L$ è una matrice triangolare inferiore unitaria (che ha tutti $1$ sulla diagonale principale) e $U$ è una matrice triangolare superiore. Una volta trovata la fattorizzazione LU per la matrice $A$ si può risolvere il sistema () $Ax = b$ risolvendo solo sistemi lineari triangolari. Sia

$$Ux = y,$$ (2.18)

l' eq () sapendo che $LU = A$ e poichè vale la () diviene

$$Ly = b.$$ (2.19)

Questo è un sistema triangolare inferiore che può essere risolto utilizzando il metodo di ``sostituzione in avanti'' che ha complessità $\Theta(n^2)$. Una volta risolto questo sistema si ottiene il vettore $y$, sostituendo il risultato ottenuto nell' equazione () e risolvendo un sistema triangolare superiore si ottiene $x$. Il vettore $x$ sarà anche soluzione del sistema (). Il sistema () viene risolto con il metodo di ``sostituzione a ritroso'' che ha complessità $\Theta(n^2)$.