The resultant iteration for determining the stability of a polynomial
HTML articles powered by AMS MathViewer
- by James Lucien Howland PDF
- Math. Comp. 32 (1978), 779-789 Request permission
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
- Erwin H. Bareiss, Resultant procedure and the mechanization of the Graeffe process, J. Assoc. Comput. Mach. 7 (1960), 346–386. MR 119416, DOI 10.1145/321043.321049 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.
- William Snow Burnside and Arthur William Panton, The theory of equations: With an introduction to the theory of binary algebraic forms, Dover Publications, Inc., New York, 1960. 2 volumes. MR 0115987
- A. Cohn, Über die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise, Math. Z. 14 (1922), no. 1, 110–148 (German). MR 1544543, DOI 10.1007/BF01215894
- Eugene D. Denman and Alex N. Beavers Jr., The matrix sign function and computations in systems, Appl. Math. Comput. 2 (1976), no. 1, 63–94. MR 393075, DOI 10.1016/0096-3003(76)90020-5
- R. J. Duffin, Algorithms for classical stability problems, SIAM Rev. 11 (1969), 196–213. MR 249740, DOI 10.1137/1011034
- H. Kober, Dictionary of conformal representations, Dover Publications, Inc., New York, N.Y., 1952. MR 0049326
- Cornelius Lanczos, Applied analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1956. MR 0084175
- Morris Marden, Geometry of polynomials, 2nd ed., Mathematical Surveys, No. 3, American Mathematical Society, Providence, R.I., 1966. MR 0225972 D.-E. MAYER, "Sur les équations algébriques," Ann. de Math. (3), v. 10, 1891, pp. 111-124.
- F. W. J. Olver, The evaluation of zeros of high-degree polynomials, Philos. Trans. Roy. Soc. London Ser. A 244 (1952), 385–415. MR 49652, DOI 10.1098/rsta.1952.0010
- Jean Peltier, Résolution numérique des équations algébriques, Gauthier-Villars, Paris, 1957 (French). MR 0088797
- James B. Scarborough, Numerical mathematical analysis, 6th ed., Johns Hopkins Press, Baltimore, Md., 1966. MR 0198651 B. L. VAN DER WAERDEN, Modern Algebra, Vol. I, Ungar, New York, 1949.
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
Additional Information
- © Copyright 1978 American Mathematical Society
- Journal: Math. Comp. 32 (1978), 779-789
- MSC: Primary 65E05
- DOI: https://doi.org/10.1090/S0025-5718-1978-0494866-3
- MathSciNet review: 0494866