EVD symétrique

Un nombre réel Λ et un vecteur z forment une paire propre de la matrice A si Az = Λz. Pour une matrice réelle A, on peut avoir à la fois le problème de la recherche des valeurs propres et celui de la recherche des valeurs propres et des vecteurs propres.

Si la matrice A de taille N×N est symétrique, elle possède N valeurs propres (pas nécessairement distinctes) et N vecteurs propres correspondants qui forment une base orthonormée (généralement, les vecteurs propres ne sont pas orthogonaux et leur nombre peut être inférieur à N).

Aperçu des algorithmes existants pour la résolution du problème des valeurs propres

Le premier algorithme résolvant le problème des valeurs propres d'une matrice symétrique N×N fut l'algorithme de Jacobi, réduisant la matrice à une forme diagonale par une transformation orthogonale. Lors de ces transformations, les éléments diagonaux étaient augmentés et les éléments hors diagonale diminués. Le résultat était une matrice dont les éléments hors diagonale étaient nuls et les éléments diagonaux égaux aux valeurs propres.

L'algorithme de Jacobi est simple mais inefficace : il effectue des opérations sur la matrice complète A même lorsque la plupart de ses éléments ont déjà convergé vers zéro. Presque tous les algorithmes ultérieurs de résolution du problème des valeurs propres symétriques réduisent préalablement la matrice à une forme tridiagonale (cette opération est effectuée par un algorithme non itératif en un nombre fini d'étapes) avant de travailler avec une matrice tridiagonale.

La famille d'algorithmes la plus répandue est celle basée sur l'itération QL/QR appliquée à une matrice tridiagonale. On peut citer l'algorithme de la bibliothèque LINPACK qui implémente l'algorithme QL le plus simple (les sous-programmes associés sont disponibles dans de nombreuses sources) et une variante plus récente de la bibliothèque LAPACK (le sous-programme xSTEQR) qui utilise des décalages implicites et peut alterner entre les itérations QL et QR en fonction de leurs performances pour la matrice donnée. L'algorithme de la bibliothèque LAPACK est plus volumineux, mais plus fiable et précis ; c'est donc celui qui sert de base au code source disponible sur cette page.

La bibliothèque LAPACK propose d'autres algorithmes de recherche de paires propres. On peut mentionner un algorithme de type «diviser pour régner» et un algorithme RRR. Ils permettent d'accélérer considérablement la recherche de paires propres pour les grandes matrices tridiagonales symétriques. Le gain de vitesse peut atteindre plusieurs dizaines de fois pour une matrice tridiagonale, et de 2 à 4 fois pour une matrice symétrique (en tenant compte du temps nécessaire à sa réduction à une forme tridiagonale). Ces algorithmes étant relativement complexes, ils n'ont pas encore été intégrés à la bibliothèque ALGLIB. Si le temps de calcul des paires propres de grandes matrices symétriques est critique, il est recommandé d'utiliser la bibliothèque LAPACK.

Remarque n° 1 : Si l'on doit calculer les valeurs propres et les vecteurs propres d'un intervalle donné (ou à partir de valeurs données), il est judicieux d'utiliser un algorithme basé sur la dichotomie et l'itération inverse. Si l'on ne doit calculer qu'une petite partie du spectre, on peut améliorer considérablement les performances par rapport aux algorithmes qui calculent toutes les valeurs propres et tous les vecteurs propres.

Description de la sous-routine

Cet algorithme calcule toutes les valeurs propres (et, le cas échéant, les vecteurs propres) d'une matrice symétrique. La matrice symétrique est réduite à une forme tridiagonale par transformation orthogonale. L'algorithme de résolution de ce problème pour une matrice tridiagonale est ensuite appelé. Cet algorithme étant itératif, il peut théoriquement ne pas converger. Dans ce cas, il renvoie la valeur «Faux».

Cet algorithme utilise les sous-routines de la bibliothèque LAPACK 3.0.