Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
MathSciNet review: 1262279
Full-text PDF

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.

References [Enhancements On Off] (What's this?)

  • [1] V. I. Arnold, On matrices depending on parameters, Russian Math. Surveys 26 (1971), 29-43. MR 0301242 (46:400)
  • [2] F. R. Gantmacher, The theory of matrices, Vols. 1, 2, Chelsea, New York, 1959. MR 0107649 (21:6372c)
  • [3] I. Gohberg, P. Lancaster, and L. Rodman, Matrix polynomials, Academic Press, New York, 1982. MR 662418 (84c:15012)
  • [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. Parlett and C. Reinsch, Balancing a matrix for calculation of eigenvalues and eigenvectors, Numer. Math. 13 (1969), 293-304. MR 1553969
  • [8] W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical recipes--The art of scientific computing, Cambridge Univ. Press, Cambridge, 1986. MR 833288 (87m:65001a)
  • [9] K.-C. Toh and L. N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), 403-425. MR 1313152 (95m:65085)
  • [10] J. F. Traub, Associated polynomials and uniform methods for the solution of linear problems, SIAM Rev. 8 (1966), 277-301. MR 0207238 (34:7054)
  • [11] P. Van Dooren and P. Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545-579. MR 699575 (84j:15009)

Similar Articles

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

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

Additional Information

Keywords: Algebraic equation, QR method, eigenvalue
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society