On the computation of eigenvectors of a symmetric tridiagonal matrix: comparison of accuracy improvements of Givens and inverse iteration methods

Stéphane Balac
Laboratoire de Mathématiques Appliquées de Lyon
INSA de Lyon, 69621 Villeurbanne cedex, France
stephane.balac@insa-lyon.fr

Miloud Sadkane
Laboratoire de Mathématiques
Université de Bretagne Occidentale, 29000 Brest, France
miloud.sadkane@univ-brest.fr

 

Abstract

The aim of this paper is the comparison of the recent improvements of two methods to compute eigenvectors of a symmetric tridiagonal matrix once the eigenvalues are computed. The first one is the Givens method which is based on the use of Sturm sequences. This method suffers from a lack of accuracy for the computation of the eigenvector when an approximate value (even a very accurate one) of the eigenvalue is used in the computational process. In [Godunov, S.K. and Antonov, A.G. and Kirilyuk, O.P. and Kostin, V.I., Guaranteed accuracy in numerical linear algebra, Mathematics and its Applications, Kluwer Academic Publishers, 1993] the authors introduce a modification of Givens method to ensure the computation of an accurate eigenvector from a good approximation of the corresponding eigenvalue. The second improvement concerns the inverse iteration method. In [Parlett, B.N. and Dhillon, I.S., Fernando's solution to Wilkinson's problem: An application of double factorization, Linear Algebra Appl., 267:247-279, 1997] the authors present a way to determine the best initial vector to start the iterations. Although the two methods and their improvements seem to be very different from a computational point of view, there exists some striking analogies. For instance, in the two methods we look for an optimal index, we have to minimize a residual, etc. In the paper we briefly present the two methods and investigate the connections between them.

 

Résumé

Nous nous intéressons à la comparaison d'améliorations de deux méthodes classiques de calcul des vecteurs propres d'une matrice tridiagonale symétrique réelle. Il s'agit d'une part de la méthode de Givens basée sur l'utilisation des suites de Sturm dont une amélioration a été proposée par S.K. Godunov, A.G. Antonov, O.P. Kirilyuk et V.I. Kostin [Guaranteed accuracy in numerical linear algebra, Mathematics and its Applications, Kluwer Academic Publishers, 1993] et d'autre part de la méthode de l'itération inverse dont un perfectionnement concernant le choix du vecteur initial a été proposé par B.N. Parlett et I.S. Dhillon [Fernando's solution to Wilkinson's problem: An application of double factorization, Linear Algebra Appl., 267:247-279, 1997]. Bien que basées sur des idées différentes, les deux méthodes présentent des analogies frappantes. Dans les deux cas on cherche à déterminer un indice optimal et on cherche à minimiser un résidu. Nous présentons ces deux méthodes et explicitons les analogies. Nous avons mis en oeuvre les deux méthodes et nous les comparons du point de vue de leur efficacité numérique.