Bibliographie & annexes
Présentation
RÉSUMÉ
Calculer les valeurs propres et les vecteurs propres de matrices est un important problème en analyse numérique linéaire. Les problèmes de valeurs propres sont très riches, tant par leur variété que par le type de matrices que l'on doit traiter et par les méthodes et algorithmes de calcul à utiliser : les matrices peuvent être symétriques ou non symétriques, creuses ou pleines, et les problèmes peuvent être classiques ou généralisés ou même quadratiques. Il existe des applications qui requièrent le calcul d'un très petit nombre de valeurs propres, d'autres au contraire un grand nombre ou même tout le spectre.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleABSTRACT
Calculating the eigenvalues and eigenvectors of a matrix is a major issue in linear numerical analysis. Eigenvalue problems are extremely rich, due to their variety, the type of matrices to be treated as well as the methods and calculation algorithms to be used; matrices can be symmetrical or non-symmetrical, hollow or full and the problems can be traditional, generalized or even quadratic. Whereas certain applications require the calculation of a very low number of eigenvalues, others require the calculation of a very large number and even of the whole spectrum.
Auteur(s)
-
Bernard PHILIPPE : INRIA Rennes-Bretagne Atlantique
-
Yousef SAAD : Department of computer science and engineering, university of Minnesota
INTRODUCTION
Calculer les valeurs propres et les vecteurs propres de matrices est un des problèmes les plus importants en analyse numérique linéaire. Les techniques requérant la connaissance du spectre de matrices sont utilisées dans des domaines aussi variés que la mécanique quantique, l'analyse des structures, la théorie des graphes, les modèles de l'économie et le classement des pages de la Toile informatique par les moteurs de recherche.
Par exemple, en mécanique des structures, les problèmes de « résonances » ou de « vibrations » de structures mécaniques, décrits par l'analyse spectrale, se ramènent à des calculs de valeurs et de vecteurs propres.
Les problèmes non symétriques de valeurs propres apparaissent dans l'analyse de la stabilité de systèmes dynamiques. Dans un tout autre domaine, la chimie quantique donne lieu à des problèmes symétriques aux valeurs propres qui peuvent être gigantesques, tant par leur taille que par le nombre de valeurs et de vecteurs propres à extraire. On peut également mentionner que la décomposition aux valeurs singulières, qui est une sorte de généralisation de la décomposition spectrale classique, est primordiale en statistique et dans les problèmes de la « nouvelle économie » (reconnaissance de formes, fouille de données, traitement du signal, exploitation de données, etc.).
Les problèmes de valeurs propres sont très riches, tant par leur variété que par le type de matrices que l'on doit traiter et par les méthodes et algorithmes de calcul à utiliser : les matrices peuvent être symétriques ou non symétriques, creuses ou pleines, et les problèmes peuvent être classiques ou généralisés ou même quadratiques. Il existe des applications qui requièrent le calcul d'un très petit nombre de valeurs propres, d'autres au contraire un grand nombre de valeurs propres ou même tout le spectre.
On essaiera donc dans cet article de survoler les outils permettant de résoudre ces différents cas.
L'expertise technique et scientifique de référence
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Mathématiques
(202 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
Algorithmes pour le cas d'une matrice pleine symétrique2. Algorithme QR pour le cas non symétrique
Dans ce paragraphe, on suppose que la matrice A, dont on recherche les valeurs propres, est réelle et qu'on maintient les calculs réels aussi longtemps que possible. C'est en effet le cas le plus courant. Même si le recours à l'arithmétique complexe dans le cas des matrices non symétriques est conceptuellement plus simple que la restriction aux calculs réels puisqu'il supprime le traitement de cas particuliers, du point de vue informatique, on préfère éviter les calculs complexes car ils ralentissent généralement l'exécution. Cependant, tous les calculs décrits peuvent être exécutés en arithmétique complexe en faisant attention à utiliser le produit scalaire hermitien de deux vecteurs complexes x et y défini par
.
Puisque la forme de Hessenberg est préservée par l'algorithme QR qui sera décrit ensuite, il est important de réduire d'abord la matrice donnée sous cette forme par des transformations de similarité.
2.1 Réduction à la forme Hessenberg supérieure
On rappelle d'abord les transformations de Householder pour transformer une matrice non symétrique à la forme de Hessenberg supérieure. Les matrices de symétrie de Householder sont des matrices de la forme :
où w est un vecteur de norme unité. Une telle matrice correspond à une transformation linéaire qui envoie un vecteur x vers son image symétrique par rapport à l'hyperplan orthogonal à w, noté sev{w }⊥.
On remarque d'abord que P est une matrice réelle symétrique orthogonale lorsque w est réel. Dans le cas complexe, la matrice de Householder P = I – 2ww H est hermitienne et unitaire. Pour simplifier l'exposé du paragraphe, on se limite au cas réel.
En pratique, on réécrit P sous la forme P = I – βvv T avec β = 2/||v ||2, où v est un multiple de w. Pour la stocker, il suffit...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(202 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
Algorithme QR pour le cas non symétrique
BIBLIOGRAPHIE
-
(1) - ANDERSON (E.), BAI (Z.), BISCHOF (C.), BLACKFORD (L.S.), DEMMEL (J.), DONGARRA (J.J.), DU CROZ (J.), HAMMARLING (S.), GREENBAUM (A.), McKENNEY (A.), SORENSEN (D.) - LAPACK Users' guide (3ème éd.). - Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999). http://www.netlib.org/lapack/lug/
-
(2) - BAI (Z.), DEMMEL (J.), DONGARRA (J.), RUHE (A.), VAN DER VORST (H.) - Templates for the Solution of Algebraic Eigenvalue Problems : A Practical Guide. - Number 11 in Software, Environments, and Tools. SIAM, Philadelphia (2000).
-
(3) - BENNIGHOF (J.K.), LEHOUCQ (R.B.) - An automated multilevel substructuring method for eigenspace computation in linear elastodynamics. - SIAM J. Sci. Comput., 25(6), p. 2084-2106 (2004).
-
(4) - BOISVERT (R.F.), POZO (R.), REMINGTON (K.), BARRETT (R.), DONGARRA (J.) - The Matrix Market : A Web repository for test matrix data. - In R.F. Boisvert, editor. The Quality of Numerical Software, Assessment and Enhancement. Chapman & Hall, London p. 125-137 (1997).
-
(5) - BREZINSKI (C.), REDIVO ZAGLIA (M.), SADOK (H.) - A review of formal orthogonality in Lanczos-based...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(202 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
