A Bisection Method for the Banded Hyperbolic Quadratic Eigenvalue Problem

Abstract

It is well-known that the eigenvalues of a Hermitian matrix in a given interval can be approximated within a predefined error tolerance using the bisection method as a direct application of the Sylvester's Law of Inertia. In this thesis, we will develop a bisection method for the hyperbolic quadratic eigenvalue problem (HQEP) which is guaranteed to have 2n real eigenvalues for a problem of size n. A number of numerical methods are available to solve HQEPs. Matlab's polyeig uses the QZ algorithm on the problem after linearizing it to a pencil of size 2n. Another approach is by finding a solvent matrix. Both approaches ignore any banded structure of the problem. For the tri-diagonal HQEPs, an approach to approximate the eigenvalues by efficiently solving the characteristic equation was also proposed. The method can't be applied to higher banded HQEPs efficiently. Our method will avoid converting the HQEP to a definite pencil of order 2n by working on the HQEP directly taking into consideration any banded structure of the problem. Our method can be applied to large banded HQEPs and produces more accurate eigenvalue approximations compared to the approaches stated.