ISSN:
0945-3245
Keywords:
Mathematics Subject Classification (1991): 65F35
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002110050069