There is no “Uspensky's method.”

ABSTRACT

In this paper an attempt is made to correct the misconception of several authors [1] that there exists a method by Upensky (based on Vincent's theorem) for the isolation of the real roots of a polynomial equation with rational coefficients. Despite Uspensky's claim, in the preface of his book [2], that he invented this method, we show that what Upensky actually did was to take Vincent's method and double its computing time. Upensky must not have understood Vincent's method probably because he was not aware of Budan's theorem [3]. In view of the above, it is historically incorrect to attribute Vincent's method to Upensky.

REFERENCES

• 1: George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 2: Uspensky, J.V.: Theory of Equations. McGraw- Hill Co., New York 1948.
• 3: Akritas, A.G.: Reflections on a pair of theorems by Budan and Fourier. Mathematics Magazin% Vol. 55, No. 5, 292-298, 1982.
• 4: Vincent, A.J.H.: Sur la r~solution des ~quations num~riques. Journal de Math~matiques Pures et Appliqu~es, Vol. i, 341-372, 1836
• 5: Akritas, A.G.: An implementation of Vincent's theorem. Numerische Mathematik, Vol. 36, 53-62, 1980.
• 6: Cajori, F.: A history of the arithmetical methods of approximation to the roots of numerical equations of one unknown quantity. Colorado College Publications, General Series No. 51, Science Series Vo. XII, no. 7, Colorado Springs, CO., 171-215, 1910.
• 7: Akritas, A.G. and S.D. Danielopoulos: On the forgotten theorem of Mr. Vincent. Historia Mathematica, Vol. 5, 427-435, 1978.
• 8: Akritas, A.G.: There is no "Uspensky's Method". TR-86-10, University of Kansas, Department of Computer Science, Lawrence Ks 66045, 1986.
• 9: George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806346]
• 10: Alkiviadis G. Akritas, A remark on the proposed syllabus for an AMS short course on computer algebra, ACM SIGSAM Bulletin, v.14 n.2, p.24-25, May 1980 [doi>10.1145/1089220.1089223]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods; Polynomials, methods for

  K. Computing Milieux
  K.2 HISTORY OF COMPUTING
      Subjects: Systems

General Terms:
Algorithms, Theory