Origin-shifted algorithm for matrix eigenvalues

Abstract

In this paper an origin-shifted algorithm for matrix eigenvalues based on Frobenius-like form of matrix and the quasi-Routh array for polynomial stability is given. First, using Householder's transformations, a general matrix A is reduced to upper Hessenberg form. Secondly, with scaling strategy, the origin-shifted Hessenberg matrices are reduced to the Frobenius-like forms. Thirdly, using quasi-Routh array, the Frobenius-like matrices are determined whether they are stable. Finally, we get the approximate eigenvalues of A with the largest real-part. All the eigenvalues of A are obtained with matrix deflation. The algorithm is numerically stable. In the algorithm, we describe the errors of eigenvalues using two quantities, shifted-accuracy and satisfactory-threshold. The results of numerical tests compared with QR algorithm show that the origin-shifted algorithm is fiducial and efficient for all the eigenvalues of general matrix or for all the roots of polynomial.

Keywords:

• matrix eigenvalues
• origin shifts
• Hessenberg matrix
• Frobenius-like form
• quasi-Routh array

2000 AMS Subject Classification :

• 15A21
• 93D05
• 65H17

Acknowledgements

The authors are grateful to Professor C. Li for his actual suggestions.