Méthode du pivot de Gauss

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=\pmatrix{ a_{11} & a_{12} & \cdots & a_{1n} \cr a_{21} & a_{22} & \cdots & a_{2n} \cr \vdots & \vdots & \ddots & \vdots \cr a_{n1} & a_{n2} & \cdots & a_{nn} } \pmatrix{ x_1 \cr x_2 \cr \vdots \cr x_n }=\pmatrix{ b_1 \cr b_2 \cr \vdots \cr b_n }=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=\pmatrix{ 1 & 2 & 2 \cr 1 & 3 & -2 \cr 3 & 5 & 8 } , x=\pmatrix{ x_1 \cr x_2 \cr x_3 },b=\pmatrix{ 2\cr -1 \cr 8 }$

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=\pmatrix{ 3 \cr -1 \cr 1/2 }$

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

Méthode du pivot de Gauss

Mots-clés:

Problème

Exemple de résolution

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

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

Rubriques

Dans la même rubrique

Mots-clés