Polynomial roots from companion matrix eigenvalues

Authors:
Alan Edelman and H. Murakami

Journal:
Math. Comp. **64** (1995), 763-776

MSC:
Primary 65F15; Secondary 65G10, 65H05

DOI:
https://doi.org/10.1090/S0025-5718-1995-1262279-2

MathSciNet review:
1262279

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In classical linear algebra, the eigenvalues of a matrix are sometimes defined as the roots of the characteristic polynomial. An algorithm to compute the roots of a polynomial by computing the eigenvalues of the corresponding companion matrix turns the tables on the usual definition. We derive a first-order error analysis of this algorithm that sheds light on both the underlying geometry of the problem as well as the numerical error of the algorithm. Our error analysis expands on work by Van Dooren and Dewilde in that it states that the algorithm is backward normwise stable in a sense that must be defined carefully. Regarding the stronger concept of a small componentwise backward error, our analysis predicts a small such error on a test suite of eight random polynomials suggested by Toh and Trefethen. However, we construct examples for which a small componentwise relative backward error is neither predicted nor obtained in practice. We extend our results to polynomial matrices, where the result is essentially the same, but the geometry becomes more complicated.

**[1]**V. I. Arnol′d,*On matrices depending on parameters*, Uspehi Mat. Nauk**26**(1971), no. 2(158), 101–114 (Russian). MR**0301242****[2]**F. R. Gantmacher,*Matrizenrechnung. II. Spezielle Fragen und Anwendungen*, Hochschulbücher für Mathematik, Bd. 37, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959 (German). MR**0107647**

F. R. Gantmacher,*Applications of the theory of matrices*, Translated by J. L. Brenner, with the assistance of D. W. Bushaw and S. Evanusa, Interscience Publishers, Inc., New York; Interscience Publishers Ltd., London, 1959. MR**0107648**

F. R. Gantmacher,*The theory of matrices. Vols. 1, 2*, Translated by K. A. Hirsch, Chelsea Publishing Co., New York, 1959. MR**0107649****[3]**I. Gohberg, P. Lancaster, and L. Rodman,*Matrix polynomials*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. Computer Science and Applied Mathematics. MR**662418****[4]**D. Manocha and J. Demmel,*Algorithms for intersecting parametric and algebraic curves*I:*simple intersections*, ACM Trans. Graphics**13**(1994), 73-100.**[5]**-,*Algorithms for intersecting parametric and algebraic curves*II:*multiple intersections*, Computer graphics, vision and image processing: Graphical models and image processing (to appear).**[6]**C. Moler,*Cleve's corner*:*ROOTS--Of polynomials, that is*, The MathWorks Newsletter, vol. 5, no. 1 (Spring 1991), 8-9.**[7]**B. N. Parlett and C. Reinsch,*Handbook Series Linear Algebra: Balancing a matrix for calculation of eigenvalues and eigenvectors*, Numer. Math.**13**(1969), no. 4, 293–304. MR**1553969**, https://doi.org/10.1007/BF02165404**[8]**William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling,*Numerical recipes*, Cambridge University Press, Cambridge, 1986. The art of scientific computing. MR**833288**

William T. Vetterling, Saul A. Teukolsky, William H. Press, and Brian P. Flannery,*Numerical recipes example book (Pascal)*, Cambridge University Press, Cambridge, 1985. MR**833291**

William T. Vetterling, Saul A. Teukolsky, William H. Press, and Brian P. Flannery,*Numerical recipes example book (FORTRAN)*, Cambridge University Press, Cambridge, 1985. MR**833292****[9]**Kim-Chuan Toh and Lloyd N. Trefethen,*Pseudozeros of polynomials and pseudospectra of companion matrices*, Numer. Math.**68**(1994), no. 3, 403–425. MR**1313152**, https://doi.org/10.1007/s002110050069**[10]**J. F. Traub,*Associated polynomials and uniform methods for the solution of linear problems*, SIAM Rev.**8**(1966), 277–301. MR**0207238**, https://doi.org/10.1137/1008061**[11]**Paul Van Dooren and Patrick Dewilde,*The eigenstructure of an arbitrary polynomial matrix: computational aspects*, Linear Algebra Appl.**50**(1983), 545–579. MR**699575**, https://doi.org/10.1016/0024-3795(83)90069-1

Retrieve articles in *Mathematics of Computation*
with MSC:
65F15,
65G10,
65H05

Retrieve articles in all journals with MSC: 65F15, 65G10, 65H05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1995-1262279-2

Keywords:
Algebraic equation,
QR method,
eigenvalue

Article copyright:
© Copyright 1995
American Mathematical Society