metodo di eliminazione di Gauss (o di gradinizzazione)

Algoritmo

Input: matrice completa $(A|b)$ di un sistema lineare.
Output: matrice completa $(\tilde{A}|\tilde{b})$ tale che $\tilde{A}$ è a scala e $\tilde{A}X=\tilde{b}$ è equivalente a $AX=b$.

$1)$ Determino $\overline{j}$ indice colonna minima per cui abbiamo una colonna non nulla di $A$.

$\overline{j}=min\left\{j:A^{(j)}\ne 0\right\}$

$$A=\left(\begin{array}{ccccc}0& 0& \underline{\ast }& \dots & \ast \\ 0& 0& \ast & \dots & \ast \\ 0& 0& \ast & \dots & \ast \end{array}\right)$$

$2)$ Determino un indice $\overline{i}$ tale per cui l’elemento $a_{ij}$ è non nullo (l’esistenza di un tale $\overline{i}$ dipende dalla scelta di $\overline{j}$).

$3)$ Scambio le righe $\overline{i}$ e $1$; in questo modo posso supporre che l’elemento $a_{1j}$ sia non nullo.

$$\left(\begin{array}{ccccc}0& 0& a_{1j}& \ast & \ast \\ 0& 0& \underline{\ast }& \ast & \ast \\ 0& 0& \underline{\ast }& \ast & \ast \end{array}\right)$$

$4)$ Moltiplico la prima riga per $\frac{1}{a_{1j}}$.

$$\left(\begin{array}{ccccc}0& 0& 1& \ast & \ast \\ 0& 0& \underline{\ast }& \ast & \ast \\ 0& 0& \underline{\ast }& \ast & \ast \end{array}\right)$$

$5)$ Per ogni $i\in \{2,\dots ,m\}$, sommo alla riga $i$-esima un opportuno multiplo della prima riga; più precisamente, sostituisco l’$i$-esima riga con

$A_{(i)}-a_{i\overline{j}}{A}_{(1)}$

$$\left(\begin{array}{ccccc}0& 0& 1& \ast & \ast \\ 0& 0& 0& \ast & \ast \\ 0& 0& 0& \ast & \ast \end{array}\right)$$

$6)$ Ripeto il procedimento precedente sulla sotto-matrice con righe $\{2,\dots ,m\}$ e colonne $\{\overline{j}+1,\dots ,n\}$.

$$\left(\begin{array}{ccccc}0& 0& 1& \ast & \ast \\ 0& 0& 0& \underline{\ast }& \underline{\ast }\\ 0& 0& 0& \underline{\ast }& \underline{\ast }\end{array}\right)$$

Questo algoritmo termina in un tempo finito e restituisce un risultato che rispetta le prescrizioni della specificazione.

Risorse

Wikipedia