Locating the Eigenvalues of Matrix Polynomials

Some known results for locating the roots of polynomials are extended to the case of matrix polynomials. In particular, a theorem by Pellet [Bull. Sci. Math. (2), 5 (1881), pp. 393--395], some results from Bini [Numer. Algorithms, 13 (1996), pp. 179--200] based on the Newton polygon technique, and recent results from Gaubert and Sharify (see, in particular, [Tropical scaling of polynomial matrices, Lecture Notes in Control and Inform. Sci. 389, Springer, Berlin, 2009, pp. 291--303] and [Sharify, Scaling Algorithms and Tropical Methods in Numerical Matrix Analysis: Application to the Optimal Assignment Problem and to the Accurate Computation of Eigenvalues, Ph.D. thesis, École Polytechnique, Paris, 2011]). These extensions are applied to determine effective initial approximations for the numerical computation of the eigenvalues of matrix polynomials by means of simultaneous iterations, like the Ehrlich--Aberth method. Numerical experiments that show the computational advantage of these results are presented.