Soluzione di sistemi con Matrice Triangolare

Come visto in precedenza, il MEG opera una trasformazione $PA = LU$.

Posto $A$ non singolare:

$$\begin{split}Ax = b & \Leftrightarrow PAx = Pb \\ & \Leftrighta... ... Pb\\ &\Leftrightarrow \begin{cases}Ly = Pb \\ Ux = y \end{cases} \end{split}$$

Trasforma ossia un sistema $Ax = b$, denotato in breve come $[A\vert b]$, in $[U\vert\beta]$.

Il sistema $Ux = \beta$ si risolve, ovviamente, con una serie di sostituzioni all'indietro:

$$\underbrace{x_i = \beta_i - \sum_{j=i+1}^n u_{ij} x_j}_{u_{ii}} \qquad i=n, n-1, \ldots, 1$$

Il costo computazionale è di $\approx n^2$ FLOPs, e il costo asintotico è:

$$C = \not{2} \frac{n(n-1)}{\not{2}} = O(n^2)$$

Dunque il costo per risolvere

$$\begin{cases} Ly = Pb \\ Ux = y \end{cases}$$

è

$$C = 2n^2$$