Élimination de Gauss-Jordan

Gelose | Tous les portails | Portail Medecine | Portail Biologie | Portail Biochimie | Portail Microbiologie | Portail Ecologie | Portail Botanique | Biologie cellulaire | Portail Zoologie | Science de la terre | Portail Eau |


 Inscrivez votre site en haut de cette page Soumission direct par Allopass, obtenez 1 lien de qualite en haut de cette page Elimination de Gauss-Jordan ainsi que sur la page des nouveaux sites inscrits pour seulement 20 euros!


En mathématiques, l'élimination de Gauss ou l'élimination de Gauss-Jordan, nommé en hommmage à Carl Friedrich Gauss et Wilhelm Jordan est un algorithme de l'algèbre linéaire pour déterminer les solutions d'un système d'équations linéaires, pour déterminer le rang d'une matrice ou pour calculer l'inverse d'une matrice carrée inversible. Lorsqu'on applique l'élimination de Gauss sur une matrice, on obtient sa forme échelonnée réduite.

Sommaire

[] Histoire

Cette méthode fut nommée d'après le mathématicien Carl Friedrich Gauss, mais elle est connue des Chinois depuis au moins le Ier siècle de notre ère. Elle est référencée dans l'important livre chinois Jiuzhang suanshu ou Les neuf chapitres sur l'art mathématique, dont elle constitue le huitième chapitre, sous le titre « Fang cheng » (la disposition rectangulaire). La méthode est présentée au moyen de 18 exercices. Dans son commentaire très détaillé daté de 263, Liu Huien attribue la paternité à Chang Ts'ang chancelier de l'empereur de Chine au IIe siècle avant notre ère.

[] Analyse numérique

La complexité algorithmique de l'élimination de Gauss est O(n3)(Notations de Landau), donc le nombre d'instruction nécessaire est proportionnel à n3 si la matrice est de type n*n. Cet algorithme peut être utilisé sur un ordinateur pour des systèmes avec des milliers d'inconnues et d'équations. Il est cependant numériquement instable, les erreurs d'arrondis effectuées pendant le calcul sont accumulées et le résultat trouvé peut être loin de la solution. Mais l'élimination de Gauss est une bonne méthode pour les systèmes d'équations sur un champ où les calculs sont exacts comme les corps finis.

[] Calcul de l'inverse d'une matrice carrée par l'algorithme de Gauss-Jordan

Inverser une matrice A carrée inversible d'ordre n, revient à résoudre les n systèmes Afi = ei pour i allant de 1 à n. Pour cela, on crée un tableau à n lignes et 2n colonnes en bordant la matrice A par la matrice identité In.


Ainsi, pour inverser la matrice A=(ai j) de format (n, n), on utilisera la matrice augmentée suivante :

(A|I) = \begin{pmatrix} a_{11} & \cdots & a_{1n} & | & 1 & \cdots & 0 \\ \vdots & \ddots & \vdots & | & \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} & | & 0 & \cdots & 1 \\ \end{pmatrix}

La transformation de Gauss-Jordan consiste à transformer ce système en un système équivalent dont le bloc gauche est l'identité, c'est-à-dire qu'il faut la matrice (A | I) pour qu'elle devienne de la forme (I | A − 1) en utilisant les propriétés de l'algorithme. On notera :

  • l_i^k la ligne i de la matrice A à l'itération k
  • a_{ij}^k le scalaire ai j de la matrice A à l'itération k

L'algorithme de Gauss-Jordan est le suivant :

Pour k allant de 1 à n

Si a_{kk}^{k-1}\not=0
l_k^k \leftarrow \frac{1}{a_{kk}^{k-1}} l_k^{k-1}
Pour i allant de 1 à n et i ≠ k
l_i^k \leftarrow l_i^{k-1}-a_{ik}^{k-1} \times l_k^{k}
Sinon A n'est pas inversible

[] Exemple

Soit le système d'équations suivant :

\begin{cases} x - y + 2z &\mbox{= 5} \\ 3x + 2y +z &\mbox{= 10} \\ 2x - 3y - 2z &\mbox{= -10} \\ \end{cases}

On établit la matrice correspondante et on applique la première étape de Gauss-Jordan, le pivot est 1 :

\begin{bmatrix} 1 & -1 & 2 & \big| & 5 \\ 3 & 2 & 1 & \big| & 10 \\ 2 & -3 & -2 & \big| & -10 \end{bmatrix}

On ajoute un multiple (respectivement -3 et -2) de la première ligne aux deux autres lignes pour obtenir des zéros ; le nouveau pivot est ensuite 5 :

\begin{bmatrix} (1) & -1 & 2 & \big| & 5 \\ 0 & (5) & -5 & \big| & -5 \\ 0 & -1 & -6 & \big| & -20 \end{bmatrix}

La deuxième ligne est multipliée par 1/5 :

\begin{bmatrix} 1 & -1 & 2 & \big| & 5 \\ 0 & (1) & -1 & \big| & -1 \\ 0 & -1 & -6 & \big| & -20 \end{bmatrix}

On ajoute cette deuxième ligne à la troisième, le nouveau pivot est -7 :

\begin{bmatrix} 1 & 0 & 1 & \big| & 4 \\ 0 & 1 & -1 & \big| & -1 \\ 0 & 0 & (-7) & \big| & -21 \end{bmatrix}

On divise la 3ème ligne par -7 :

\begin{bmatrix} 1 & 0 & 1 & \big| & 4 \\ 0 & 1 & -1 & \big| & -1 \\ 0 & 0 & (1) & \big| & 3 \end{bmatrix}

On utilise la 3ème ligne pour éliminer des coefficients dans la première et deuxième ligne. Nous sommes alors en présence d'une forme échelonnée réduite avec la matrice identité d'un côté et la valeur des variables dans l'autre :

\begin{bmatrix} 1 & 0 & 0 & \big| & 1 \\ 0 & 1 & 0 & \big| & 2 \\ 0 & 0 & 1 & \big| & 3 \end{bmatrix}

La solution du système est ainsi :

\begin{cases} x &\mbox{= 1} \\ y &\mbox{= 2} \\ z &\mbox{= 3} \\ \end{cases}

[] Voir aussi


Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques.
Elimination_de_Gauss-Jordan_49b0