A Backward Stable Algorithm For Quadratic Eigenvalue Problems

The quadratic eigenvalue problem (QEP) arises in a wide variety of applications in science and engineering. In this thesis, we develop a backward stable algorithm for QEPs and implement it effectively. The notation of backward stability is the standard way of measuring whether an algorithm is good or not. A backward stable algorithm gives the exact answer to nearly the original problem. In general, we at most guarantee that the best algorithms for most problems in numerical linear algebra are backward stable. Our algorithm for dense QEPs is the first backward stable one so far.First, we present a backward stable algorithm for dense QEPs. Our algorithm incor-porates a tropical-like scaling, a strategy for choosing linearizations and an associated strategy for recovering eigentriples. We prove that the growth factor in the translation from conditioning for the quadratic to conditioning for the linearization and the growth factor in the translation from backward error for the linearization to backward error for the quadratic are both of order one in the algorithm. Therefore, we prove that the whole algorithm is backward stable. Moreover, numerical examples confirm our theoretical analysis and display the advantages of our algorithm, particularly its effectiveness for solving heavily damped QEPs.Second, we implement the designed algorithm as an eigensolver (a MATLAB func-tion called qeig) for the complete solution of dense QEPs. The eigensolver consists of not only the previous developments for the algorithm but also a preprocessing step that deflates some zero and infinity eigenvalues owing to singular leading and trail-ing coefficient matrices. It is backward stable for all general dense QEPs. Numerical experiments illustrate that for some QEPs, especially heavily damped ones, qeig out-performs the MATLAB function quadeig in terms of both stability and effciency.