AN EFFICIENT AND STABLE STRUCTURE PRESERVING ALGORITHM FOR COMPUTING THE EIGENVALUES OF A HAMILTONIAN MATRIX

Abstract

Abstract: An efficient and stable structure preserving algorithm, which is a variant of the QR like (SR) algorithm due to Bunse-Gerstner and Mehrmann, is presented for computing the eigenvalues and stable invariant subspaces of a Hamiltonian matrix In the algorithm two strategies are employed, one of which is called dis-unstabilization technique and the other is preprocessing technique Together with them, a so-called ratio-reduction equation and a backtrack technique are introduced to avoid the instability and breakdown in the original algorithm It is shown that the new algorithm can overcome the instability and breakdown at low cost Numerical results have demonstrated that the algorithm is stable and can compute the eigenvalues to very high accuracy.

Key words: Hamiltonian matrix, QR like algorithm, eigenvalue, stability, dis-unstabilization, backtrack technique, ratio-reduction

2010 MSC Number:

O241.6

YAN Qing-you;XIONG Xi-wen. AN EFFICIENT AND STABLE STRUCTURE PRESERVING ALGORITHM FOR COMPUTING THE EIGENVALUES OF A HAMILTONIAN MATRIX. Applied Mathematics and Mechanics (English Edition), 2002, 23(11): 1292-1309.

TrendMD

References

[1] Byers R. A Hamiltonian QR-algorithm[J]. SIAMJSci Statist Comput,1986,7:212-229.
[2] Bunse-Gerstner A, Byers R, Mehrmann V. A chat of numerical methods for structured eigenvalue problems[J]. SIAM J Matrix Anal Appl, 1992,13:419-453.
[3] Bunse-Gerstner A, Mehrmann V. A symplectic QR-like algorithm for the solution of the real alge braic Riccati equation[J]. IEEE Trans Automat Control, 1986,31:1104-1113.
[4] Hench J J, Laub A J. Numerical solution of the discrete-time periadic Riccati equation[J]. IEEETrans Automat Control, 1994,39: 1197-1210.
[5] Lin W W. A new method for computing the closed loop eigenvalues of a discrete-time algebraic Riccati equation[J]. Linear Algebra Appl, 1987,96:157-180.
[6] Lu L Z, Lin W W. An iterative algorithm for the solution of a discrete-time algebraic Riccati equation[J]. Linear Algebra Appl, 1993,188/189:465-488.
[7] Lin W W, Wang C. On computing stable Lagrangian subspaces of Hamiltonian martices and sym plectic pencils[J]. SIAM J Matrix Anal Appl , 1997,18: 590-614.
[8] Pappas C, Laub A J, Sandell N R. On the numerical solution of the discrete-time algebraic Riccati equation[J]. IEEE Trans Autorm Control, 1980,25:631-641.
[9] Patel R V. On computing the eigenvalues of a symplectic pencils[J]. Linear Algebra Appl, 1993, 188:591-611.
[10] Patel R V, Lin Z, Misra P. Computation of stable invariant subspaces of Hamiltonian matrices[J]. SIAM J Matrix Anal Appl , 1994,15:284-298.
[11] Benner P, Mehrmann V, Xu H. A numerically stable, structure preserving method for computing the eigenvalues or real Hamiltonian or symplectic pencils[J]. Numer Math, 1998,78:329-358.
[12] Bunse-Gerstner A, Mehrmann V, Watkins D. An SR algorithm for Hamiltonian matrices, based on Gaussian elimination[J]. Methods Oper Res, 1989,58: 339-358.
[13] Mehrmann V. A symplectic orthogonal method for single input or single output discrete time opti mal quadratic control problems[J]. SIAM J Matrix Anal Appl, 1988,9: 221-247.
[14] Van Loan C. A symplectic method for approximating all the eigenvalues of a Hamiltonian matrix[J]. Linear Algebra Appl ,1984 ,16:233-251.
[15] Golub G H, Van Loan C. Matrix Computations[M]. Baltimore: The Johns Hopkins University Press, 1996.
[16] Stewart G W. Introduction to Matrix Computations[M]. New York: Academic, 1973.
[17] Wilkinson J H. The Algebraic Eigenvalue Problem[M]. Clarendon: Oxford,1965.
[18] Benner P, Faeebender H. An implicity restarted symplectic lanczos method for the Hamiltonian eig envalue problem[J]. Linear Algebra Appl, 1997,263: 75-111.