Présentation
En anglais
Auteur(s)
-
Robert CABANE : Ancien élève de l’École Normale Supérieure - Professeur de Mathématiques Spéciales au Lycée Michel-Montaigne (Bordeaux)
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleINTRODUCTION
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 viwi à 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.
L'expertise technique et scientifique de référence
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
Méthodes euclidiennes
En anglais
3. Méthodes itératives
Dans ce chapitre on considère à nouveau le problème de la résolution d’une équation linéaire de la forme Ax = b, A étant une matrice inversible, mais au lieu de chercher un algorithme permettant d’obtenir la solution directement, si elle existe, on examine des procédés d’itérations qui peuvent créer une suite convergente de vecteurs (xn), ayant pour limite la solution désirée.
Ce type de méthode est très utilisé pour des problèmes de grande taille, lorsque la matrice A contient beaucoup de coefficients nuls hors de sa diagonale.
On pourra se reporter au chapitre 10 de [9] et au chapitre 7 de [1] pour plus de détails.
3.1 Principes théoriques
3.1.1 Méthodes des approximations successives
Nous pouvons remplacer l’équation Ax = b par une équation équivalente :
P Ax = PbP étant une matrice inversible qui sera choisie ultérieurement, puis par un problème de point fixe de la forme :
x = x + (Pb − P Ax ) = ( In − P A )x + Pb = F (x )La méthode des approximations successives (expliquée dans l’article A 100, paragraphe 6.4) suggère alors de s’intéresser à l’itération de la fonction F ; plus précisément, si on note F k la k-ième composée successive de F avec elle-même, on considère la suite de vecteurs :
xk = F (x k−1) = F k (x0)le vecteur x0 restant à choisir.
Si cette suite converge vers un vecteur y, la continuité de F assure que l’on a F (y ) = y , c’est-à-dire une solution au problème étudié.
Deux problèmes se posent alors :
-
choisir une fonction F (donc une matrice P ) assurant une convergence du processus ;
-
estimer...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Méthodes itératives
ANNEXES
1.1 Logiciels et bibliothèques de calcul numérique
La mise en œuvre effective des méthodes décrites ci-dessus requiert des techniques informatiques fort précises que la taille de cet article ne permet pas d’aborder. De toutes manières, les programmes « prêts à l’emploi » ne sont pas toujours bien adaptés au traitement de situations réelles qui peuvent nécessiter des simplifications préalables, des estimations des erreurs tolérables, etc.
C’est donc sous toutes réserves que nous fournissons ci-dessous une liste nullement exhaustive des logiciels et bibliothèques existants. Ajoutons que ce domaine est susceptible d’évoluer rapidement sous l’effet de l’amélioration continue des performances des ordinateurs et de la découverte d’algorithmes toujours plus efficaces. Enfin, signalons que la validité de certaines «recettes numériques » est parfois contestée ; il convient donc de se renseigner amplement avant de faire confiance à un programme existant.
Voici une liste des principales bibliothèques (librairies) de calcul numérique linéaire :
1. EISPACK.
Bibliothèque de programmes en Fortran pour le calcul de valeurs propres et vecteurs propres. Contient des procédures pour l’évaluation du rayon spectral.
NEA Data Bank, BP 9,
91191 Gif-sur-Yvette, France
Le manuel est édité sous le titre :
Smith (B.T.), Boyle (J.M.), Dongarra (J.), Garbow (B.), Ikebe (Y.), Klema (V.C.) et Moler...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
