Summary.
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 \(\hat{p}\) obtained by coefficientwise perturbations of \(p\) of size {$\leq \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\({\Bbb C}\) defined as the set of eigenvalues of matrices{$\hat{A} = A + E$} with \(\Vert E\Vert \leq \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 \Vert p\Vert }(p)\) and \(\Lambda_{ \epsilon \Vert A\Vert }(A)\) are usually quite close to one 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.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received June 15, 1993
Rights and permissions
About this article
Cite this article
Toh, KC., Trefethen, L. Pseudozeros of polynomials and pseudospectra of companion matrices . Numer. Math. 68, 403–425 (1994). https://doi.org/10.1007/s002110050069
Issue Date:
DOI: https://doi.org/10.1007/s002110050069