PSEUDOZEROS OF POLYNOMIALS AND PSEUDOSPECTRA OF COMPANION MATRICES

It is well known that the zeros of a polynomial p are equal to the eigenvalues of the associated companion matrix A. In this paper we take a geometric view of the conditioning of these two problems and of the stability of algorithms for polynomial zerofinding. The epsilon-pseudozero set Z(epsilon)(p) is the set of zeros of all polynomials p obtained by coefficientwise perturbations of p of size less-than-or-equal-to epsilon; this is a subset of the complex plane considered earlier by Mosier, and is bounded by a certain generalized lemniscate. The epsilon-pseudospectrum LAMBDA(epsilon)(A) is another subset of C defined as the set of eigenvalues of matrices A = A + E with parallel-toEparallel-to less-than-or-equal-to epsilon; it is bounded by a level curve of the resolvent of A. We find that if A is first balanced in the usual EISPACK sense, then Z(epsilon)parallel-topparallel-to(p)) and LAMBDA(epsilon)parallel-toAparallel-to(A) are usually quite close t to another. It follows that the Matlab ROOTS algorithm of balancing the companion matrix, then computing its eigenvalues, is a stable algorithm for polynomial zerofinding. Experimental comparisons with the Jenkins-Traub (IMSL) and Madsen-Reid (Harwell) Fortran codes confirm that these three algorithms have roughly similar stability properties.