Bissection et itération inverse

Un nombre réel Λ et un vecteur z forment une paire propre de la matrice A si Az = Λz. Si une matrice A de taille N×N est symétrique, elle possède N valeurs propres (non nécessairement distinctes) et N vecteurs propres associés, formant une base orthonormée (généralement, les vecteurs propres ne sont pas orthogonaux et leur nombre peut être inférieur à N).

Pour une matrice réelle A, on peut se trouver face au problème de la recherche de toutes les valeurs propres et de tous les vecteurs propres (le spectre de la matrice), ou à celui de la recherche d'une partie de ce spectre. Si toutes les valeurs propres ne sont pas nécessaires, on peut utiliser la méthode de dichotomie pour les trouver dans un intervalle donné (ou à partir de valeurs données). Ensuite, on peut trouver les vecteurs propres par la méthode d'itération inverse. Si l'on ne cherche qu'une petite partie du spectre, on peut améliorer considérablement les performances par rapport à l'algorithme QL/QR.

Comme lors de l'utilisation de l'algorithme QL/QR, la matrice symétrique est réduite à une forme tridiagonale, puis les méthodes de dichotomie et d'itération inverse, adaptées à cette forme, sont appliquées.

Convergence et précision

Examinons la fiabilité de cette 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 confronté à un problème qu'il n'a pas pu résoudre, la sous-routine renvoie la valeur « Faux ». Dans ce cas, il est judicieux d'utiliser l'algorithme QL/QR, plus stable que la méthode d'itération inverse, puis de sélectionner le vecteur recherché parmi l'ensemble des vecteurs propres trouvés (cette méthode est relativement lente, mais elle permet d'obtenir une solution).

Description de la sous-routine

Pour trouver les valeurs propres (et leurs vecteurs propres correspondants) du demi-intervalle donné [A, B], utilisez la sous-routine SMatrixEVDR. La sous-routine SMatrixEVDI trouve les paires de valeurs propres correspondant aux nombres indiqués (le spectre est considéré comme trié par ordre croissant).

Il convient de noter que cet algorithme n'est efficace que pour la recherche d'une petite partie du spectre. Si l'on souhaite trouver toutes les valeurs propres (ou la majorité d'entre elles), l'algorithme QL/QR est plus performant.

Cet algorithme est issu de la bibliothèque LAPACK.