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: , , , , , , , , .

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.

Messages

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n'apparaîtra qu'après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message
  • Pour créer des paragraphes, laissez simplement des lignes vides.

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

Links