Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



The resultant iteration for determining the stability of a polynomial

Author: James Lucien Howland
Journal: Math. Comp. 32 (1978), 779-789
MSC: Primary 65E05
MathSciNet review: 0494866
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The square root iteration $ {x_{i + 1}} = ({x_i} + x_i^{ - 1})/2$ is known to be convergent to $ + 1$ from starting values $ {x_0}$ in the open right half-plane, and to $ - 1$ from starting values in the open left half-plane. The resultant of the quadratic $ {z^2} - 2wz + 1$ and a given polynomial $ P(z)$, of proper degree n, is a polynomial $ R(w)$ whose zeros, expressed in terms of the zeros $ {z_i}$ of $ P(z)$, are just $ {w_i} = ({z_i} + z_i^{ - 1})/2$. The construction of $ R(w)$ is thus equivalent to n independent applications of the square root iteration, with unknown starting values $ {z_i}$. Repetition of this construction generates a sequence of resultants whose zeros are independently convergent to either $ + 1$ or $ - 1$ according as the initial zero of $ P(z)$ lies in the open right or left half-plane. When the given polynomial, and each of the resultants, is written as a linear combination of the $ n + 1$ polynomials $ {(z + 1)^n},{(z + 1)^{n - 1}}(z - 1),{(z + 1)^{n - 2}}{(z - 1)^2}, \ldots ,(z + 1){(z - 1)^{n - 1}},{(z - 1)^n}$. the sequence of resultants is ultimately convergent to one of the elements $ {(z + 1)^{n - p}}{(z - 1)^p}$ of this basis, whence it follows that $ P(z)$ has p zeros with positive real part and $ n - p$ zeros with negative real part, and the Hurwitz stability problem for $ P(z)$ is solved. By an application of the principle of argument it is, in general, possible to determine p at a finite stage of the resultant iteration.

When formulated in terms of this basis, the resultant iteration becomes formally identical with the root-squaring process. This fact may be exploited to establish the properties of the resultant iteration, and to show that root-squaring may be applied to solve the Schur stability problem for a given polynomial. Although precise results are not available, numerical results and the general properties of this iteration suggest that, for the purpose at hand, it is unaffected by the progressive deterioration of condition that sometimes occurs in other applications of root-squaring.

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

  • [1] E. H. BAREISS, Resultant procedure and the mechanization of the Graeffe process," J. Assoc. Comput. Mach., v. 7, 1960, pp. 346-386. MR 0119416 (22:10178)
  • [2] E. H. BAREISS, "The numerical solution of polynomial equations and the resultant procedures" in Mathematical Methods for Digital Computers, Vol. II (A. Ralston & H. S. Wilf, Editors), Wiley, New York, 1967, pp. 185-214.
  • [3] W. S. BURNSIDE & A. W. PANTON, The Theory of Equations, Two volumes, Dover, New York, 1960. MR 0115987 (22:6784)
  • [4] A. COHN, "Über die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise," Math. Z., v. 14, 1922, pp. 110-148. MR 1544543
  • [5] E. D. DENMAN & A. N. BEAVERS, JR., "The matrix sign function and computation in systems," Appl. Math. Comput., v. 2, 1976, pp. 63-94. MR 0393075 (52:13886)
  • [6] R. J. DUFFIN, "Algorithms for classical stability problems," SIAM Rev., v. 11, 1969, pp. 196-213. MR 0249740 (40:2981)
  • [7] H. KOBER, Dictionary of Conformal Representations, Dover, New York, 1952. MR 0049326 (14:156d)
  • [8] C. LANCZOS, Applied Analysis, Prentice-Hall, Englewood Cliffs, N. J., 1956. MR 0084175 (18:823c)
  • [9] M. MARDEN, Geometry of Polynomials, Math. Surveys, no. 3, Amer. Math. Soc., Providence, R. I., 1966. MR 0225972 (37:1562)
  • [10] D.-E. MAYER, "Sur les équations algébriques," Ann. de Math. (3), v. 10, 1891, pp. 111-124.
  • [11] F. W. J. OLVER, "The evaluation of zeros of high-degree polynomials," Philos. Trans. Roy. Soc. London Ser. A, v. 244, 1952, pp. 385-415. MR 0049652 (14:209f)
  • [12] J. PELTIER, Résolution Numérique des Équations Algébriques, Gauthier-Villars, Paris, 1957. MR 0088797 (19:582a)
  • [13] J. B. SCARBOROUGH, Numerical Mathematical Analysis, 6th ed., The Johns Hopkins Press, Baltimore, Maryland, 1966. MR 0198651 (33:6806)
  • [14] B. L. VAN DER WAERDEN, Modern Algebra, Vol. I, Ungar, New York, 1949.
  • [15] J. H. WILKINSON, Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, N. J., 1963. MR 0161456 (28:4661)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65E05

Retrieve articles in all journals with MSC: 65E05

Additional Information

Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society