Metodo di Eliminazione di Gauss (Triangolarizzazione)

Premessa

Osserviamo preliminarmente che la soluzione di un sistema non singolare di forma triangolare, superiore o inferiore, è quasi immediata.

Infatti nel caso di un sistema triangolare superiore:

$a_{ii} \neq 0, \forall i = 1, ..., n$ 

la soluzione si ottiene con
$O( \frac{n^2}{2})$ operazioni moltiplicative con il seguente algoritmo: $x_i = \frac{b_i - \sum \limits_{j=i+1}^n a_{ij} x_j }{a_{ii}}, i=n-1, n-2, ..., 1$

Questo ci suggerisce che triangolarizzare un qualunque sistema con matrice quadrata è una utile strategia risolutiva.

E' noto che quando ad un'equazione di un sistema sostituiamo una combinazione lineare con un'altra equazione del sistema, il nuovo sistema risulta equivalente a quello originario, cioè pur avendo forma diversa, la soluzione è uguale.

Col metodo di Gaus è possibile trasformare in n-1 passi, ed eventuali permutazioni di righe e/o di colonne (pivoting parziale e pivoting totale), un generico sistema in uno equivalente ma triangolare.

Calcolo del costo computazionale del metodo di Gauss
Ci chiediamo:

• quanto costa un passo?

Al passo k-esimo si effettuano $n-k$ divisioni

infatti si valuta 

$m_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}$ per $i=k+1, ..., n$;
e $(n-k)(n-k+1)$ moltiplicazioni per le entrate $a_{ij}^{(k+1)}$ e $b_{i}^{(k+1)}$ per $i=k+1, ..., n$ e $j=k+1, ..., n$

• quanti passi facciamo? 

Poiché realizziamo $n-1$ passi allora avremo