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.
- V. I. Arnol′d, On matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101–114 (Russian). MR 0301242
- F. R. Gantmacher, Matrizenrechnung. II. Spezielle Fragen und Anwendungen, Hochschulbücher für Mathematik, Band 37, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959 (German). MR 0107647
- I. Gohberg, P. Lancaster, and L. Rodman, Matrix polynomials, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662418 D. Manocha and J. Demmel, Algorithms for intersecting parametric and algebraic curves I: simple intersections, ACM Trans. Graphics 13 (1994), 73-100. —, Algorithms for intersecting parametric and algebraic curves II: multiple intersections, Computer graphics, vision and image processing: Graphical models and image processing (to appear). C. Moler, Cleve’s corner: ROOTS—Of polynomials, that is, The MathWorks Newsletter, vol. 5, no. 1 (Spring 1991), 8-9.
- 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, DOI 10.1007/BF02165404
- 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
- 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, DOI 10.1007/s002110050069
- J. F. Traub, Associated polynomials and uniform methods for the solution of linear problems, SIAM Rev. 8 (1966), 277–301. MR 207238, DOI 10.1137/1008061
- Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545–579. MR 699575, DOI 10.1016/0024-3795(83)90069-1
- © Copyright 1995 American Mathematical Society
- 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