Élimination de gauss-jordan

Élimination de Gauss-Jordan

Pour les articles homonymes, voir pivot.

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

1 Histoire
2 Analyse numérique
3 Calcul de l'inverse d'une matrice carrée par l'algorithme de Gauss-Jordan
4 Résolution d'un système d'équations linéaires par l'algorithme de Gauss-Jordan
5 Exemple
6 Déterminant
7 Notes et références
8 Voir aussi
- 8.1 Articles connexes
- 8.2 Liens externes

Histoire

Cette méthode doit son nom aux mathématiciens Carl Friedrich Gauss et Wilhelm Jordan, mais elle est connue des Chinois depuis au moins le I^er 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 Hui en attribue la paternité à Chang Ts'ang chancelier de l'empereur de Chine au II^e siècle avant notre ère.

Analyse numérique

La complexité algorithmique asymptotique de l'élimination de Gauss est $O (n 3)$ (notations de Landau), donc le nombre d'instructions nécessaires est proportionnel à n³ 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. Cependant, l'algorithme de Strassen, qui est en $O (n 2,807)$ a une meilleure complexité algorithmique asymptotique. De plus, la stabilité du procédé pose problème : en appliquant directement l'algorithme, les erreurs d'arrondis effectuées pendant le calcul sont accumulées et le résultat trouvé peut être loin de la solution. Dans la pratique, une bonne stratégie de choix des pivots permet en général de remédier à cette instabilité, même si on peut donner des contre-exemples^[1]. L'élimination de Gauss est une bonne méthode pour les systèmes d'équations sur un corps 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 Af_i = e_i 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é I_n.

Ainsi, pour inverser la matrice A=(a_{i 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 a_{i 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, qui vaut 1.

Variante : on peut aussi chercher le coefficient $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 un coefficient plus grand, mais il faut garder la trace 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 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 vecteur 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 que pour $i$ allant de $k + 1$ à $n$ , on obtient une matrice triangulaire 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^e 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^e 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 son rang.

Notes et références

↑ voir par exemple les commentaires de Patrick Lascaux, Raymond Théodor, Analyse numérique matricielle appliquée à l'art de l'ingénieur, tome 1 : Méthodes directes [détail des éditions], p. 228

Voir aussi

Algèbre linéaire générale
Vecteur • Scalaire • Combinaison linéaire • Espace vectoriel • Matrice
Famille de vecteurs	Colinéarité • Indépendance linéaire • Famille libre • Rang • Famille génératrice • Base • Théorème de la base incomplète
Sous-espace	Somme d'ensembles • Somme directe • Sous-espace supplémentaire • Dimension d'un espace vectoriel • Codimension • Droite • Plan • Hyperplan
Morphisme et notions relatives	Application linéaire • Noyau • Conoyau • Lemme des noyaux • Pseudo-inverse • Théorème de factorisation • Théorème du rang • Équation linéaire • Système d'équations linéaires • Élimination de Gauss-Jordan • Forme linéaire • Espace dual • Orthogonalité • Base duale • Endomorphisme linéaire • Valeur propre, vecteur propre et espace propre • Spectre • Projecteur • Symétrie • Matrice diagonalisable • Endomorphisme nilpotent
En dimension finie	Trace • Déterminant • Polynôme caractéristique • Polynôme d'endomorphisme • Théorème de Cayley-Hamilton • Polynôme minimal d'un endomorphisme • Invariants de similitude • Réduction d'endomorphisme • Réduction de Jordan • Décomposition de Dunford
Enrichissements de structure	Norme • Produit scalaire • Forme quadratique • Espace vectoriel topologique • Orientation • Algèbre sur un corps • Algèbre de Lie • Complexe différentiel
Développements	Théorie des matrices • Représentation de groupe • Analyse fonctionnelle • Algèbre multilinéaire • Module sur un anneau

Liens externes

Méthode du pivot de Gauss

Portail des mathématiques

Ce document provient de « %C3%89limination de Gauss-Jordan ».

Catégories : Matrice | Analyse numérique matricielle | Carl Friedrich Gauss

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Élimination de gauss-jordan de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Elimination de Gauss-Jordan — Élimination de Gauss Jordan Pour les articles homonymes, voir pivot. 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… … Wikipédia en Français
Élimination de Gauss-Jordan — Pour les articles homonymes, voir pivot. 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… … Wikipédia en Français
Pivot (élimination de Gauss-Jordan) — Élimination de Gauss Jordan Pour les articles homonymes, voir pivot. 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… … Wikipédia en Français
Élimination de Gauss — Carl Friedrich Gauss « Gauss » redirige ici. Pour les autres significations, voir Gauss (homonymie). Carl Friedrich Gauss … Wikipédia en Français
Méthode de Gauss-Jordan — Réduction de Jordan Pour les articles homonymes, voir Jordan. La réduction de Jordan est la traduction matricielle de la réduction des endomorphismes introduite par Jordan. Cette réduction est tellement employée, en particulier en analyse pour la … Wikipédia en Français
Gauss–Jordan elimination — In linear algebra, Gauss–Jordan elimination is a version of Gaussian elimination that puts zeros both above and below each pivot element as it goes from the top row of the given matrix to the bottom. In other words, Gauss Jordan elimination… … Wikipedia
Méthode d'élimination de Gauss — Élimination de Gauss Jordan Pour les articles homonymes, voir pivot. 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… … Wikipédia en Français
Eliminación de Gauss-Jordan — En matemáticas, la eliminación Gaussiana, eliminación de Gauss o eliminación de Gauss Jordan, llamadas así debido a Carl Friedrich Gauss y Wilhelm Jordan, son algoritmos del álgebra lineal para determinar las soluciones de un sistema de… … Wikipedia Español
Elimination — Élimination Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Gauss (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Carl Friedrich Gauss (1777 1855), mathématicien, astronome et physicien allemand. Le gauss, une unité de mesure du champ magnétique, noté G. GAUSS, un… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Élimination de gauss-jordan