Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Accueil > Mathématiques > Résolution de systèmes linéaires > Méthode du pivot de Gauss

Méthode du pivot de Gauss

Toutes les versions de cet article : <English> <français>

La méthode du pivot de Gauss est une méthode directe de résolution de système linéaire qui permet de transformer un système en un autre système équivalent échelonné. On résout le système ainsi obtenu à l’aide d’un algorithme de remontée.

Problème

On cherche à résoudre le système suivant de $n$ équations à $n$ inconnues $x_1,x_2,\ldots,x_n$ :

$$ \left \{ \begin{array}{c} a_{12}x_1+a_{12}x_2+\ldots+a_{1n}x_n=b_1\\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n=b_2\\ \vdots\\ a_{n1}x_1+a_{n2}x_2+\ldots+a_{nn}x_n=b_n \end{array}\right. $$
Du point de vue matriciel, on a

$$Ax=b$$
avec

$$Ax= \left( \begin{array}{c c c c } a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \right) \left( \begin{array}{c } x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right) = \left( \begin{array}{c } b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right) =b $$

Exemple de résolution

Considérons le système suivant :

$$ \left \{ \begin{array}{cccccccl} x_1&+&2x_2&+&2x_3&=&2&L_1\\ x_1&+&3x_2&-&2x_3&=&-1&L_2\\ 3x_1&+&5x_2&+&8x_3&=&8&L_3 \end{array}\right. $$
avec

$$ A= \left( \begin{array}{ccc} 1 & 2 & 2 \\ 1 & 3 & -2\\ 3 & 5 & 8 \end{array} \right) , x= \left( \begin{array}{c} x_1\\ x_2\\ x_3 \end{array} \right) ,b= \left( \begin{array}{c} 2\\ -1\\ 8 \end{array} \right) $$

 Première étape du pivot de Gauss pour éliminer les variables $x_1$ dans les lignes $L_2$ et $L_3$ :

$$ \left \{ \begin{array}{cccccccl} x_1&+&2x_2&+&2x_3&=&2&L_1\\ &&x_2&-&4x_3&=&-3&L_2\leftarrow L_2-L_1\\ &&-x_2&+&2x_3&=&2&L_3\leftarrow L_3-3L_1 \end{array}\right. $$

 Seconde étape du pivot de Gauss pour éliminer les variables $x_2$ dans la ligne $L_3$ :

$$ \left \{ \begin{array}{cccccccl} x_1&+&2x_2&+&2x_3&=&2&L_1\\ &&x_2&-&4x_3&=&-3&L_2\\ &&&-&2x_3&=&-1&L_3\leftarrow L_3+L_2 \end{array}\right. $$
 En remontant le système, on obtient aisément la solution $x$ du système :

$$x=\left( \begin{array}{c} 3\\ -1\\ 1/2 \end{array} \right) $$

Algorithme de la méthode du pivot de Gauss : Triangularisation

$$k=1,\ldots,n-1\left\{ \begin{array}{l|ll} a_{ij}^{(k+1)}=a_{ij}^{(k)}&i=1,\ldots,k & j=1,\ldots,n \\ a_{ij}^{(k+1)}=0 &i=k+1,\ldots,n & j=1,\ldots,k \\ a_{ij}^{(k+1)}=a_{ij}^{(k)}-\displaystyle\frac{a_{ik}^{(k)}a_{kj}^{(k)}}{a_{kk}^{(k)}} & i=k+1,\ldots,n &j=k+1,\ldots,n\\ b_i^{(k+1)}=b_i^{(k)}&i=1,\ldots,k & \\ b_i^{(k+1)}=b_i^{(k)}-\displaystyle\frac{a_{ik}^{(k)}b_{k}^{(k)}}{a_{kk}^{(k)}}&i=k+1,\ldots,n & \end{array}\right. $$
Soit $U$ la matrice échelonnée du système, on a alors

$$U=(u_{ij})_{1\leq i,j\leq n}=(a^{(n)}_{ij})_{1\leq i,j\leq n}$$

Algorithme de la méthode du pivot de Gauss : Remontée et résolution

à€ présent la matrice $A$ du système linéaire est échelonnée, on doit alors résoudre le système triangulaire :

$$Ux=b^{(n)}$$
puisque $b^{(n)}$ rappelons le, est le second membre échelonné, il a subi les màªmes opérations que la matrice échelonnée $U$.

On utilise alors un algorithme de remontée pour le système $Ux = b^{(n)}$ :

$$ \left\{\begin{array}{ll} x_n = \displaystyle\frac{y_n}{u_{nn}}= \displaystyle\frac{y_n}{a^{(n)}_{nn}} ;& \\ x_i = \displaystyle\frac{1}{u_{ii}}(y_i-\sum_{j=i+1}^{n}u_{ij}x_j)= \displaystyle\frac{1}{a^{(n)}_{ii}}(y_i-\sum_{j=i+1}^{n}a^{(n)}_{ij}x_j) &\forall i=n-1,n-2,\ldots,1. \end{array}\right. $$

Dans la même rubrique

  1. Décomposition LU
  2. La factorisation de Cholesky
  3. La méthode du gradient conjugué
  4. La méthode du gradient conjugué préconditionné
  5. Méthode de Gauss-Seidel
  6. Méthode de Jacobi
  7. Méthode du pivot de Gauss