Knowledge base dedicated to Linux and applied mathematics.
Accueil > Mathématiques > Résolution de systèmes linéaires > 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.
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 $$
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) $$
$$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}$$
à€ 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. $$