Résolution des systèmes d’équations linéaires
Méthodes numériques de base - Algèbre numérique

Soit A une matrice carrée à n lignes et n colonnes dont les éléments a_ij sont connus. Soit b un vecteur dont les n composantes b_i sont connues. On recherche le vecteur x, de composantes x ₁ , x ₂ , ..., x_n , qui vérifie le système d’équations linéaires :

La solution de ce problème est connue, on la trouve dans tous les cours d’algèbre linéaire : x_i est égal à un rapport de déterminants, au dénominateur le déterminant de la matrice A et au numérateur le même déterminant dans lequel on a remplacé la i ^ième colonne par le vecteur second membre b. Les règles pour calculer un déterminant sont également classiques. Cependant, on oublie souvent de dire qu’un tel calcul demande n · n ! multiplications, c’est-à-dire de l’ordre de n ² · n ! multiplications pour résoudre le système. Pour n = 10, cela fait 3,6 × 10⁸ multiplications et pour n = 30 cela en fait 2,3 × 10³⁵ (c’est-à-dire 8 × 10¹² milliards d’années de travail pour un ordinateur effectuant un million de multiplications par seconde, ce qui représente une durée plus grande que l’âge de l’univers). C’est-à-dire que cette méthode est totalement inutilisable dans la pratique, surtout en sachant qu’il est courant de résoudre actuellement des systèmes d’équations avec plusieurs millions d’inconnues. C’est pour cette raison que l’on fait appel à des méthodes d’analyse numérique.

Celles-ci se divisent en deux classes :

• les méthodes directes qui fournissent la solution exacte après un nombre fini (et beaucoup plus petit que n ² · n !) d’opérations arithmétiques ;

• les méthodes itératives qui s’apparentent à la méthode des approximations successives et qui donnent la solution comme limite d’une suite de vecteurs.

On peut donc se demander pourquoi utiliser des méthodes itératives alors que l’on dispose de méthodes directes ;...