Un article de Wikipedia.y-project.com.
(Redirigé depuis
Pivot de Gauss)
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.
[] Histoire
Cette méthode fut nommée d'après le mathématicien Carl Friedrich Gauss, mais le premier à avoir inventé cette méthode fut Liu Hui, elle est réferencée dans l'important livre chinois Jiuzhang suanshu ou Les neuf chapitres sur l'art mathématique daté de 263.
[] Analyse numérique
La complexité algorithmique de l'élimination de Gauss est <math>O(n^3)</math>(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'inconnus 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 :
- <math>(A|I) = \begin
a_ & \cdots & a_ & | & 1 & \cdots & 0 \\
\vdots & \ddots & \vdots & | & \vdots & \ddots & \vdots \\
a_ & \cdots & a_ & | & 0 & \cdots & 1 \\
\end </math>
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 <math>(A|I)</math> pour qu'elle devienne de la forme <math>(I|A^)</math> en utilisant les propriétés de l'algorithme.
On notera :
- <math>l_i^k</math> la ligne i de la matrice A à l'itération k
- <math>a_^k</math> 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 <math>a_^\not=0</math>
- <math>l_k^k \leftarrow \frac^} l_k^</math>
- Pour i allant de 1 à n et i ? k
- <math>l_i^k \leftarrow l_i^-a_^*l_k^</math>
- Sinon A n'est pas inversible
[] Exemple
Soit le système d'équations suivant :
<math>
\begin
x - y + 2z &\mbox{= 5} \\
3x + 2y +z &\mbox{= 10} \\
2x - 3y - 2z &\mbox{= -10} \\
\end
</math>
On établit la matrice correspondante et on applique la première étape de Gauss-Jordan, le pivot est 1 :
<math>
\begin
(1) & -1 & 2 & \big| & 5 \\
3 & 2 & 1 & \big| & 10 \\
2 & -3 & -2 & \big| & -10
\end
</math>
On ajoute un multiple de la première ligne aux deux autres lignes pour obtenir des zéros, le nouveau pivot est 5 :
<math>
\begin
1 & -1 & 2 & \big| & 5 \\
0 & (5) & -5 & \big| & -5 \\
0 & -1 & -6 & \big| & -20
\end
</math>
La deuxième ligne est multipliée par 1/5 :
<math>
\begin
1 & -1 & 2 & \big| & 5 \\
0 & (1) & -1 & \big| & -1 \\
0 & -1 & -6 & \big| & -20
\end
</math>
On ajoute cette deuxième ligne à la 3ème et la première, le nouveau pivot est -7 :
<math>
\begin
1 & 0 & 1 & \big| & 4 \\
0 & 1 & -1 & \big| & -1 \\
0 & 0 & (-7) & \big| & -21
\end
</math>
On divise la 3ème ligne par -7 :
<math>
\begin
1 & 0 & 1 & \big| & 4 \\
0 & 1 & -1 & \big| & -1 \\
0 & 0 & (1) & \big| & 3
\end
</math>
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 :
<math>
\begin
1 & 0 & 0 & \big| & 1 \\
0 & 1 & 0 & \big| & 2 \\
0 & 0 & 1 & \big| & 3
\end
</math>
La solution du système est ainsi :
<math>
\begin
x &\mbox{= 1} \\
y &\mbox{= 2} \\
z &\mbox{= 3} \\
\end
</math>
[] Voir aussi
DernierMirror
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/pivot de Gauss
