Numerically reliable computation of characteristic polynomials

Abstract

Presents an algorithm for computing the characteristic polynomial of the pencil (A-sE). It is shown that after a preliminary reduction of the matrices A and E to, respectively, an upper Hessenberg and an upper triangular matrix, the problem of computing the characteristic polynomial is transformed to the solution of certain triangular systems of linear algebraic equations. The authors show that the computed characteristic polynomial corresponds exactly to perturbed matrices A+/spl Delta/A and E+/spl Delta/E and the authors derive bounds for /spl Delta/A and /spl Delta/E. The authors also suggest how to improve on this backward error via iterative refinement.