Metodo di eliminazione di Gauss

Sia $A$ matrice quadrata non singolare. Nella soluzione con MEG di un sistema $Ax = b$, la matrice $A$ viene trasformata in una matrice triangolare superiore $U$ e il sistema viene trasformato nell'equivalente $Ux = \beta$ (soluzione identica):

$$[A\vert b] \rightarrow [U\vert\beta]$$

L'algoritmo realizza una decomposizione LU, la quale fattorizza $A$ in un prodotto di due matrici $L$ e $U$ rispettivamente triangolare inferiore e superiore.

$$A = LU$$

Quindi il sistema $Ax = b$ diventa

$$LUx = b$$

$$L^{-1}LUx = \underbrace{L^{-1}b}_{\beta}$$

$$Ux = \beta$$

Il sistema triangolare $Ux = \beta$ è facilmente risolvibile con sostituzioni all'indietro, di complessità $\approx n^2$.

$$x_i = \frac{\beta_i - \sum_{j=i+1}^{n} u_{ij}x_j}{u_{ii}}$$

Questo approccio è estremamente utile quando si ha necessità di trovare la soluzione per diversi sistemi con matrice $A$ fissa in cui varia solo il termine noto $b_{1,2,\ldots,n}$: è sufficiente calcolare $LU$ una volta sola a costo $O(n^3)$ e poi risolvere ciascun sistema a costo $O(n^2)$.

$$LUx = b \Leftrightarrow \left\{ \begin{array}{l} Ly = b \\ Ux = y \end{array} \right.$$