Élimination de Gauss-Jordan
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

En mathématiques, l'élimination de Gauss-Jordan, aussi appelée pivot de Gauss, nommée en hommage à 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 ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du sous-espace vectoriel engendré par cette famille. Le théorème du rang lie le rang et la dimension du noyau...) d'une matrice ou pour calculer l'inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de composition interne · notée multiplicativement, est un élément y tel que x·y = y·x =...) d'une matrice carrée inversible. Lorsqu'on applique l'élimination de Gauss sur une matrice, on obtient sa forme échelonnée réduite (Une matrice est dite échelonnée, si le nombre de zéros précédant la première valeur non nulle d'une ligne augmente ligne par ligne jusqu'à ce qu'il ne reste plus que des zéros.).

Histoire

Cette méthode fut nommée d'après le mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son activité...) 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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les...), 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 (Liu (chinois : 柳宿, pinyin : liǔ xiù) est une loge lunaire de l'astronomie chinoise. Son étoile...) Hui en attribue la paternité à Chang Ts'ang chancelier de l'empereur de Chine au IIe siècle avant notre ère.

Analyse numérique (Une information numérique (en anglais « digital ») est une information ayant été quantifiée et...)

La complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en sciences de...) algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de résolution, par le calcul, d'un...) asymptotique de l'élimination de Gauss est O(n3) (notations de Landau), donc le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'instructions nécessaires est proportionnel à n3 si la matrice est de type n*n. Cet algorithme peut être utilisé sur un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des données sous forme binaire,...) pour des systèmes avec des milliers d'inconnues et d'équations. Cependant, l'algorithme de Strassen, qui est en O(n2,807) a une meilleure complexité algorithmique asymptotique. De plus, l'élimination de Gauss est 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 si le calculs ne sont pas faits en arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie...) exacte. Mais l'élimination de Gauss est une bonne méthode pour les systèmes d'équations sur un champ (Un champ correspond à une notion d'espace défini:) où les calculs sont par nature 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 (Tableau peut avoir plusieurs sens suivant le contexte employé :) à n lignes et 2n colonnes en bordant la matrice A par la matrice identité (En algèbre linéaire, la matrice unité ou matrice identité (cette dernière dénomination étant un anglicisme) est une matrice carrée avec des 1 sur la diagonale et des 0...) In.

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

\Big(A\;\Big|\,I_{n}\Big) = \left(\begin{array}{ccc|ccc} a_{1,1} & \cdots & a_{1,n} &  1      & \cdots & 0      \\ \vdots & \ddots & \vdots &  \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} & \ 0      & \cdots & 1      \\ \end{array}\right)

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 modifier 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 (Un vrai scalaire est un nombre qui est indépendant du choix de la base choisie pour exprimer les vecteurs, par opposition à un pseudoscalaire, qui est un...) 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 il existe une ligne i\geq k telle que a_{ik}^{k-1}\not=0
échanger cette ligne i et la ligne k : l_i \leftrightarrow l_k
l_k^k \leftarrow \frac{1}{a_{kk}^{k-1}} l_k^{k-1}
Pour i allant de 1 à n et i \neq k
l_i^k \leftarrow l_i^{k-1}-a_{ik}^{k-1} \times l_k^{k}
Sinon A n'est pas inversible, abandonner (on sait ici que le rang de la matrice est k − 1).

Après l'étape k de l'algorithme, la colonne k a tous ces coefficients nuls sauf un : celui de la diagonale (On appelle diagonale d'un polygone tout segment reliant deux sommets non consécutifs (non reliés par un côté). Un polygone à n côtés possède diagonales.), qui vaut 1.

Variante : on peut aussi chercher le coefficient (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un polynôme), un espace vectoriel, une fonction de base et ainsi de...) a_{ik}^{k-1}, i\geq k le plus grand (en valeur absolue) avant d'échanger les lignes. Cela améliore la stabilité de l'algorithme. De même on peut aussi faire des échanges sur les colonnes pour trouver une coefficient plus grand, mais il faut garder la trace (TRACE est un télescope spatial de la NASA conçu pour étudier la connexion entre le champ magnétique à petite échelle du Soleil et la géométrie du plasma coronal, à...) de ces permutations.

Avec l'inverse de la matrice A, peut résoudre les équations de la forme A.X = B, où B est un vecteur (En mathématiques, un vecteur est un élément d'un espace vectoriel, ce qui permet d'effectuer des opérations d'addition et de...) fixé, et X l'inconnue. Mais il existe aussi une autre présentation.

Résolution d'un système d'équations linéaires par l'algorithme de Gauss-Jordan

On veut résoudre un système d'équations A.X = B, où B est un vecteur fixé, et X le vesteur inconnu. On crée un tableau à n lignes et n + 1 colonnes en bordant la matrice A par le vecteur B. On utilise le même algorithme que ci-dessus. On obtient à la fin une matrice identité, et dans la dernière colonne le vecteur X recherché.

Variante : dans l'algorithme précédent, si on n'exécute la boucle interne (En France, ce nom désigne un médecin, un pharmacien ou un chirurgien-dentiste, à la fois en activité et en formation à l'hôpital ou en cabinet...) que pour i allant de k + 1 à n, on obtient une matrice triangulaire (En algèbre linéaire, les matrices triangulaires sont des matrices carrées dont une partie triangulaire des valeurs, délimitée par la diagonale principale,...) supérieure. Il ne reste plus qu'à " remonter " pour retrouver les valeurs des coefficients de X.

Exemple

Soit le système d'équations suivant :

\left\{\begin{array}{*{7}{c}}  x &-& y &+& 2z &=& 5 \\ 3x &+& 2y &+&z &=& 10 \\ 2x &-& 3y &-& 2z &=& -10 \\ \end{array}\right.

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

\left(\begin{array}{ccc|c} (1) &  -1 & 2 &  5 \\ 3 & 2 & 1 &  10 \\ 2 & -3 & -2 & -10 \end{array}\right)

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

\left(\begin{array}{ccc|c} 1 &  -1 & 2 &  5 \\ 0 & (5) & -5 &  -5 \\ 0 & -1 & -6 & -20 \end{array}\right)

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

\left(\begin{array}{ccc|c} 1 &  -1 & 2 &  5 \\ 0 & (1) & -1 &  -1 \\ 0 & -1 & -6 &   -20 \end{array}\right)

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

\left(\begin{array}{ccc|c} 1 &  0 & 1 &  4 \\ 0 & 1 & -1 &  -1 \\ 0 & 0 & (-7) &   -21 \end{array}\right)

On divise la 3ème ligne par -7 :

\left(\begin{array}{ccc|c} 1 &  0 & 1 &  4 \\ 0 & 1 & -1 &  -1 \\ 0 & 0 & (1) &  3 \end{array}\right)

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 :

\left(\begin{array}{ccc|c} 1 &  0 & 0 &  1 \\ 0 & 1 & 0 &  2 \\ 0 & 0 & 1 &   3 \end{array}\right)

La solution du système est ainsi :

\left\{\begin{array} {ccc} x &=& 1 \\ y &=& 2 \\ z &=& 3 \\ \end{array}\right.

Déterminant

Cet algorithme permet aussi de calculer le déterminant d'une matrice : dans l'algorithme ci-dessus, c'est le produit des " a_{ik}^{k-1}\not=0 " qui sont choisis comme pivot à chaque itération. Si l'algorithme s'arrête parce qu'il n'y a plus de pivot non nul, alors la matrice n'est pas inversible, son déterminant est nul, mais on peut calculer sont rang.

Page générée en 0.596 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique