EVD tridiagonale : bissection et itération inverse

Il existe plusieurs méthodes pour trouver les valeurs propres, outre la réduction de la matrice à une forme tridiagonale par transformations orthogonales. Par exemple, pour une matrice tridiagonale symétrique, le nombre de valeurs propres inférieures à une valeur donnée peut être facilement déterminé. Introduisons la fonction N(w), égale au nombre d'éléments de la matrice T inférieurs ou égaux à w. Cette fonction est constante par morceaux, non strictement croissante, et présente des discontinuités aux points w qui sont des valeurs propres. Ainsi, le problème de la recherche des valeurs propres se ramène à celui de la recherche des discontinuités d'une fonction constante par morceaux. Ceci peut être facilement réalisé par la méthode de dichotomie des intervalles contenant ces discontinuités.

La méthode de dichotomie permet de trouver les valeurs propres dans un intervalle donné, pour des valeurs propres données (par ordre croissant). Si l'on souhaite trouver toutes les valeurs propres, cette méthode est nettement plus lente que les autres, mais elle peut être utilisée pour trouver un petit nombre de valeurs propres.

La méthode de dichotomie est souvent utilisée conjointement avec la méthode d'itération inverse, permettant de trouver un vecteur propre à partir de sa valeur propre associée. Si l'on souhaite déterminer seulement une petite partie d'un ensemble complet de vecteurs propres, l'itération inverse est plus rapide que la recherche de tous les vecteurs propres à l'aide de l'algorithme QL/QR.

Les méthodes de dichotomie et d'itération inverse peuvent être utilisées séparément et appliquées à une matrice tridiagonale obtenue à partir d'une matrice symétrique (ceci est réalisé par l'algorithme qui extrait une partie des valeurs propres et des vecteurs propres d'une matrice symétrique).

Convergence et précision

Examinons la fiabilité d'une telle procédure de calcul. Ces méthodes sont relativement fiables pour les matrices dont les valeurs propres sont bien séparées. Si certaines valeurs propres sont proches, la méthode d'itération inverse peut fournir un ensemble de vecteurs propres imprécis (plus les valeurs propres sont proches, moins les vecteurs propres sont précis).

Il est important de noter que ces difficultés sont inhérentes à toutes les méthodes de recherche de valeurs propres et qu'aucune solution satisfaisante n'a encore été trouvée. Néanmoins, cette méthode reste applicable à la plupart des problèmes concrets. Si l'algorithme est appliqué à un problème qu'il ne parvient pas à résoudre, la sous-routine renvoie la valeur « Faux ». Dans ce cas, il est préférable d'utiliser l'algorithme QL/QR, plus stable que la méthode d'itération inverse. On utilise une méthode itérative, puis on sélectionne le vecteur requis parmi l'ensemble des vecteurs propres trouvés (cette méthode est relativement lente, mais elle permet d'obtenir une solution).

Description des sous-programmes

Deux sous-programmes permettent de calculer les valeurs propres et les vecteurs propres. Le premier, SMatrixTDEVDR, permet de calculer les valeurs propres dans un intervalle donné. Le second, SMatrixTDEVDI, permet de calculer les valeurs propres (et les vecteurs propres correspondants) à partir d'indices donnés.

Cet algorithme est issu de la bibliothèque LAPACK.