Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6130
Title: Pseudozeros of Polynomials and Pseudospectra of Companion Matrices
Authors: Toh, Kim-Chuan
Trefethen, Lloyd N.
Keywords: computer science
technical report
Issue Date: Jun-1993
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1360
Abstract: 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 C defined as the set of eigenvalues of matrices $\hat{A}=A+E$ with $||E|| \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||p||}(p)$ and $\Lambda_{\epsilon||A||}(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. Key words: polynomial zeros, comapnion matrix, pseudospectrum.
URI: http://hdl.handle.net/1813/6130
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
93-1360.pdf1.97 MBAdobe PDFView/Open
93-1360.ps562.92 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us