Méthode du pivot selon GAUSS
version JavaScript


version VisualBasic pour Microsoft Excel  |  pas de théorie : je
veux utiliser le programme !

Considérons le système n x n de n équations linéaires à n inconnues x1, x2,…,xn
:

a1,1x1 + a1,2x2 + … + a1,nxn = b1
a2,1x1 + a2,2x2 + … + a2,nxn = b2
…
...
an,1x1 + an,2x2 + … + an,nxn = bn

où les ai,j et les bi sont des réels donnés, i et j variant de 1 à n.
Le système peut s'écrire AX = B où A désigne la matrice des
ai,j , X la matrice colonne des xi et B la matrice colonne des bi.
On suppose que le système est de Cramer : il admet une unique solution.
C’est dire que le déterminant de A est non nul.

Cas général, théorème de Rouché :

Nous utilisons les notations suivantes :

Li désigne la i-ème équation (ou ligne) du système
Si k ­ 0, kLi désignera l'équation kai,1x1 + kai,2x2 + …
kai,nxn = kbi
L'écriture Li >> Li - kLj signifiera que l'équation Li est remplacée par
celle obtenue en lui soustrayant l'équation kLj.
La méthode de Gauss consiste à trianguler la matrice A afin de ramener
le système à la forme :

a1,1x1 + a1,2x2 + …        + a1,nxn = b1
      a'2,2x2 + a'2,3x3 + … + a2,nxn = b2
                  a'3,3x3  + … + a'3,nxn = b3
                                        ... ... ...
                   a'n-1,n-1xn-1 + a'n,nxn = bn-1
                                         a'n,nxn = bn


La matrice A est alors devenue :

.

On a fait apparaître des zéros au-dessous des termes diagonaux de i
= 2 à i = n - 1.

Dans ces conditions, on obtient tout d'abord xn = bn/a'n,n,
puis xn-1, … , x2, x1.


Description de l'algorithme : quitte à permuter les lignes, on peut supposer
que a1,1 est non nul. Si cela s'avère impossible, l'inconnue
x1 est arbitraire et le système n'est pas de Cramer.

Pour éliminer x1 en ligne 2, il suffit de lui retirer a2,1/a1,1 x L1 :


L2  ==> L2 - a2,1/a1,1x L1


Le terme constant b2 subit la même transformation : b2  ==> b2 - a2,1/a1,1x
b2.

D'une façon générale, pour éliminer x1 dans les lignes 2 à n, donc faire
apparaître des zéros au-dessous de a1,1, on procède à la transformation
:

Li  ==> Li - ai,1/a1,1x Li   et   bi  ==> bi - ai,1/a1,1x bi

On cherche à éliminer maintenant x2 dans les lignes 3 à n : cela revient
à réitérer le procédé sur la matrice :



extraite de A et sur le membre de droite (matrice colonne des constantes).


On procède à la transformation Li  ==> Li - a'i,2/a'2,2 x
Li , i variant de 3 à n.

Si a'2,2 s'était avéré nul, on aurait permuté les lignes jusqu'à
trouver un a'k,2 non nul. Si cela n'est pas possible, alors
x2 est arbitraire : le système ne serait pas de Cramer.

Le procédé se poursuit pour éliminer xk dans les lignes k, pour k <
n. Les éléments diagonaux servant de diviseur sont appelés pivots.
Remarquer que lors de l'élimination de xk, les lignes de rang
inférieur ne sont pas modifiées.

On parle parfois de la méthode du pivot maximum : elle consiste,
quitte à permuter les colonnes de la matrice, à prendre comme pivot
celui qui est le plus grand en valeur absolue afin de limiter les
erreurs d'arrondi inévitables dues à un diviseur trop faible
(pertes de chiffres significatifs).

Programmation de l'algorithme en JavaScript
L'inconvénient de JavaScript est de ne pas pouvoir définir directement
des tableaux à plusieurs dimensions. ainsi, pour entrer une matrice
d'éléments a(i,j), on utilise une petite astuce :

var a=new Array(10)
for (li=1;li<=10;li++) {a[li]=new Array(11)}

On définit ainsi une matrice 10 x 11 (10 lignes, 11 colonnes). On pourra
alors utiliser un élément matriciel en le notant a[i] [j] dans le
programme.


--------------------------------------------------------------------------------
    
--------------------------------------------------------------------------------

  

Exemple d'exécution

On a entré successivement : 2,3,-1,-6, puis 3,-1,2,11  et  7,4,-10,-8,
c'est à dire le système :


2x1 + 3x2 - x3 = -6
3x1 - x2 + 2x3 = 11          L'ordinateur donne la solution 2, -3,
1
7x1 + 4x2 - 10x3 = -8
Et pour le système :

2x1 + 3x2 - x3 = -6
3x1 - 2x2 - 8x3 = 4
7x1 + 4x2 - 10x3 = -8

l'ordinateur dit être désolé.... En effet : L2 = L3 - 2L1.