  The polynomial eigenvalue problem arises in many applications and has
received a great deal of attention over the last decade. The use of
root-finding methods to solve the polynomial eigenvalue problem dates back to
the work of Kublanovskaya (1969, 1970) and has received a resurgence due to the
work of Bini and Noferini (2013). In this paper, we present a method which uses
Laguerre iteration for computing the eigenvalues of a matrix polynomial. An
effective method based on the numerical range is presented for computing
initial estimates to the eigenvalues of a matrix polynomial. A detailed
explanation of the stopping criteria is given, and it is shown that under
suitable conditions we can guarantee the backward stability of the eigenvalues
computed by our method. Then, robust methods are provided for computing both
the right and left eigenvectors and the condition number of each eigenpair.
Applications for Hessenberg and tridiagonal matrix polynomials are given and we
show that both structures benefit from substantial computational savings.
Finally, we present several numerical experiments to verify the accuracy of our
method and its competitiveness for solving the roots of a polynomial and the
tridiagonal eigenvalue problem.
