Matrices creuses
Méthodes numériques en algèbre linéaire

Autant l’algèbre linéaire s’occupe de vecteurs très généraux, autant l’analyse numérique linéaire considère essentiellement des vecteurs ayant un nombre fini de composantes numériques, c’est-à-dire situés dans des espaces de dimension finie. Le but de cet ensemble de méthodes est de dégager des procédés explicites qui conduisent à des approximations aussi précises que possible des objets « idéaux » que la théorie a dégagés.

On verra assez rapidement que la notion de précision est elle-même imprécise, car on peut accepter, ou non, une certaine marge d’erreur sur les résultats, et mesurer cette erreur par divers procédés. Nous chercherons donc à dégager en quel(s) sens un vecteur peut être considéré comme « petit », une solution « acceptable ». L’étude rigoureuse des erreurs et de leur propagation au cours des calculs est cependant difficile et amène généralement des résultats exagérément pessimistes. Des points de vue différents, fondés sur la théorie des probabilités, conduisent souvent à des conclusions plus engageantes.

Cette étude, poussée à son extrême limite, nous amènera à une impasse dans la mesure où certains concepts de l’algèbre linéaire s’exprime par des valeurs entières (ce sont des dimensions), pour lesquelles la notion de valeur approchée n’a aucun sens.

La notion d’algorithme apparaîtra vite prépondérante ; en effet, c’est par une itération que l’on parvient généralement à « calculer » les objets recherchés. Pour prendre un exemple très simple, le produit scalaire de deux vecteurs v et w ayant n composantes se calcule par l’algorithme suivant :

Initialiser une somme S à 0.

Faire varier un compteur i de 1 à n.

Pour chaque valeur de i, ajouter v_iw_i à S.

Le résultat est la valeur finale de S.

Nous présenterons les algorithmes « en français », sans faire référence à un langage informatique particulier. De fait, la plupart sinon la totalité des algorithmes signalés se trouvent déjà codés dans l’une des bibliothèques de programmes existantes, en Fortran ou en C. Il n’est pas très difficile d’adapter ces mêmes algorithmes à d’autres langages de programmation.

Enfin, ce domaine aux confins de l’Algèbre et de l’Analyse a connu un certain renouvellement sous l’influence grandissante des logiciels qui permettent un calcul formel, c’est-à-dire exact et non approché. Ces produits, bien au point depuis les années 1990, permettent d’aborder plus favorablement la recherche des grandeurs entières dont on a parlé plus haut. Dans ces conditions, se pose la question du calcul effectif de certains objets de l’Algèbre linéaire comme les vecteurs propres ; ainsi, le travail « formel » sur les valeurs propres conduit tout naturellement à calculer dans des corps de nombres algébriques.

Nous invitons le lecteur à se reporter à l’article Algèbre linéaire pour les bases et les notations les plus courantes de cette théorie ; il pourra également consulter l’article relatif aux structures euclidiennes.

Le présent article se limite aux méthodes de résolution exacte ou approchée des équations linéaires (vectorielles), et aux outils théoriques relatifs à ces méthodes. Les problèmes de calcul exact ou approché des éléments propres (valeurs propres, vecteurs propres) seront traités dans un autre article.