Résolution de systèmes simples d'équations
Algèbre linéaire

Le problème

Le but de ce TD est de programmer une méthode de résolution de systèmes d'équations linéaires simples. Par systèmes simples, j'entends que :

• le nombre d'équations est égal au nombre d'inconnues,
• le système admet une solution,
• les coefficients mis en jeu sont des entiers ou des flottants,

Considérons le système suivant (solution = 3, 5, 7) :

3x_l -2x₂+x₃ = 6
-x₁ +3x₂-x₃ = 5
5x_l+x₂-4x₃ = -8

Ce système d'équation peut bien sûr être considéré du point de vue de l'algèbre linéaire comme la multiplication d'une matrice (3 sur 3) des coefficients par un vecteur colonne des inconnues le tout étant égal à un vecteur colonne second membre.

Il existe essentiellement deux méthodes de résolution d'un tel système :

• la méthode de Kramer consistant à calculer ni plus ni moins que l'inverse de la matrice des coefficients puis de multiplier chaque membre de l'équation par cet inverse,
• la méthode de Gauss que je vous propose de mettre en oeuvre au cours de ce TD et consistant non plus à inverser la matrice mais à :
  • calculer une matrice triangulaire supérieure ou inférieure équivalente à la matrice des coefficients,
  • calculer de la même manière un second membre équivalent,
  • effectuer ensuite une substitution arrière pour obtenir la solution finale.

Triangulation de la matrice des coefficients

La méthode est simple.

• prenons le premier élément de la diagonale comme pivot et utilisons la première ligne pour faire apparaître, par combinaisons linéaires des autres lignes, des 0 dans la première colonne (sous le pivot).
• le vecteur second membre doit, évidemment subir les mêmes transformations que les lignes de notre matrice,
• réitérer le processus en choisissant maintenant comme pivot le second élément de la diagonale et en utilisant la seconde ligne pour faire apparaître des 0 sous le pivot,
• la même méthode se poursuit, bien entendu, jusqu'à obtention d'une matrice triangulaire.

Substitution arrière :

Là encore rien de bien compliqué, la dernière équation étant pratiquement résolue.

• calcul de la valeur de x_n à partir de la dernière équation,
• substitution de la valeur de x_n dans l'équation n- 1,
• calcul de x_n-l,
• propagation de la valeur des x_i dans les équations précédentes jusqu'à obtention de x_l.

Mise en garde

Cette méthode risque d'échouer lamentablement si la matrice est singulière. Il y a également un problème lorsque le pivot est nul ...

Programmation

Nous reprendrons bien entendu la structure de données du TD concernant la petite bibliothèque d'algèbre linéaire ainsi que les procédures déjà écrites qui nous seront utiles.

En plus des opérations déjà programmées, nous aurons besoin des procédures suivantes

• extraction d'une ligne d'une matrice,
• remplacement d'une ligne par une autre dans une matrice,

La manière la plus simple d'effectuer les mêmes opérations sur la matrice et sur le second membre consiste à intégrer ce dernier en bout de la matrice et nécessite donc l'écriture des deux procédures suivantes

• extraction d'une colonne de matrice,
• ajout d'une colonne à une matrice.

Sans oublier, bien évidemment, la procédure de substitution arrière et la mise en forme de toutes ces opérations dans le programme principal.

Deux dernières choses (pour les gens qui seraient en avance) :

1. la matrice peut être singulière ! !
2. les pivots peuvent être nuls !!