Gauss

Soit une matrice $A$ de dimension $n\times n$, $x,b\in {\bf R}^n$

Soit $A^{(1)}=A$, on définit par récurrence $A^{(k+1)}$ à partir de $A^{(k)}$ en faisant des combinaisons de lignes :

$$\ell_i\leftarrow \ell_i-\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}\ell_k\quad i>k$$

On obtient ainsi des 0 au-dessous de la diagonale dans la colonne k, à condition que $a_{kk}^{(k)}\ne 0$. A l'étape n on a un système triangulaire qu'on résoud par remontée :

$$\left\{ \begin{array}{lll} x_n & = & \frac{1}{a_{nn}}b_n\\ &... ... \frac{1}{a_{11}}(-\sum_{j>1}a_{1j}x_j+b_1) \end{array}\right.$$

La méthode de Gauss équivaut à écrire la décomposition $A=LU$ où $L$ est triangulaire inférieure avec des coefficients diagonaux égaux à 1 et $U$ est triangulaire supérieure avec des coefficients diagonaux $\ne 0$ .

Stratégie de pivot : à chaque étape on effectue un échange de lignes pour avoir le coefficient diagonal le plus grand en module .