Procédé d'élimination de Gauss-Jordan

L'idée sous-jacente est de transformer un système en un système équivalent triangulaire dont la résolution est immédiate. Soit un système de Cramer :
α1,1x1+...+α1,nxn1
α2,1x1+...+α2,nxn2
....................................
αn,1x1+...+αn,nxnn
que nous pouvons encore écrire en utilisant les notations des formes linéaires:
f1(X)=β1
f2(X)=β2
...........
fn(X)=βn
Pour tout système de scalaires (k2,...,kn) ∈ Kn-1 le système est équivalent à:
f1(X)= β1
f2(X)-k2f1(X)=β2-k2β1
...............................
fn(X)-knf1(X)= βn-knβ1
Peut-on choisir les scalaires (k2,...,kn), de façon à ce que tous les coefficients de x1 soient nuls dans les équations autres que la première ?
La réponse est positive pourvu que α1,1 soit inversible dans K.
Il suffit de prendre:
k22,11,1
..........
knn,11,1
Le système initial est alors équivalent à un système du type:
α1,1x1+ α1,2x2+...+α1,nxn1
0        +γ2,2x2+...+γ2,nxn2
....................................
0        +γn,2x2+...+γn,nxnn
On voit donc qu'on est ramené à résoudre le système d'ordre n-1:
γ2,2x2+...+γ2,nxn2
....................................
γn,2x2+...+γn,nxnn
x1 sera alors calculé en fonction de x2,...,xn par:
x1=(β1-(α1,2x2+...+α1,nxn))/α1,1
Supposons maintenant qu'on ait α1,1=0. Nous affirmons que forcément un des coefficients αi,1 pour 2≤i≤n est non nul.
Dans le cas contraire toute la première colonne de la matrice serait nulle, la matrice ne serait pas de rang n et on n'aurait pas un système de Cramer, contrairement à l'hypothèse.
Cela vu, dans un système toutes les lignes sont interchangeables. Il suffit donc de commencer par échanger la ligne 1 avec la ligne i pour être placé dans les conditions α1,1≠0.
Il suffit alors d'itérer le processus, c'est à dire d'appliquer le même traitement au système:
γ2,2x2+...+γ2,nxn2
....................................
γn,2x2+...+γn,nxn= δn
A chaque fois on fait tomber d'une unité l'ordre du système à résoudre, jusqu'à parvenir à:
αxn
dont la solution est évidente.
Cet algorithme est connu sous le nom de 'procédé d'élimination de Gauss-Jordan' ou encore de 'pivot de Gauss' , le 'pivot' correspondant au coefficient non nul dont nous avons besoin à chaque fois pour itérer le processus.
Mesurons maintenant l'efficacité de cet algorithme.
A la première étape nous avons n-1 divisions puis n2 multiplications puis n additions. Les termes en n sont négligeables devant n2 . Le procédé total est donc en n2+(n-1)2+...+22+12=n(n-1)(2n-1)/6. L'efficacité est donc en n3/3, ce qui est bien meilleur que le n! des formules de Cramer nécessitant le calcul de déterminants.
On peut maintenant réfléchir à de possibles optimisations de ce procédé. Par exemple, au lieu de se borner à prendre un pivot non nul, on préférera, si le cas se présente, prendre un pivot égal à 1. Cela dit, si aucun pivot n'est égal à l'unité entre tous les pivots possibles, on aura intérêt à en choisir un qui ne soit ni trop petit ni trop grand pour ne pas avoir de problèmes d'arrondis trop importants en fonction de la précision des types numériques utilisés (float, double, etc...).

Wilhelm Jordan: http://www.et.fh-koeln.de/ia/ma/jordan.html
Voici une appliquette permettant de voir à l’œuvre le système d'élimination de Gauss-Jordan.
Matrice A Second membre
Matrice du système Solution
ℤ/5ℤ
Ordre de la matrice carrée A  :

Café Python

Voici une implémentation de la méthode du pivot de Gauss pour la résolution d'un système à coefficients rationnels (calculs exacts).

On remarquera que l'implémentation ci-dessus est 'destructrice', le système est altéré par le procédé de résolution. Ceci n'a aucune importance quand on est seulement interessé par les solutions. En général les systèmes à résqoudre sont (très) gros, on peut imaginer qu'ils sont stockés sur disque. Il est alors préférable, pour ne pas utiliser trop d'espace mémoire d'utiliser un procédé destructeur. La plupart des bibliothèques spécialisées offrent le choix.