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

Méthode du pivot de Gauss

jeudi 1er juin 2006, par Nadir SOUALEM

Mots-clés: algorithme , descente , méthode , méthode directe , pivot de Gauss , remontée , résolution , système linéaire , système triangulaire .

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 équations à 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

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 dans les lignes et :

$\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 dans la ligne :

$\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 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 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 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 .

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.$

Un message, un commentaire ?

Si vous souhaitez aider financièrement le projet Math-Linux.com, vous pouvez aider notre équipe. Merci !!!

Links