Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Divided differences, shift transformations and Larkin's root finding method

Authors: A. Neumaier and A. Schäfer
Journal: Math. Comp. 45 (1985), 181-196
MSC: Primary 65H05
MathSciNet review: 790651
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For a one-dimensional complex-valued function f this paper deals with iterative root finding methods using divided differences of f. Assuming that f is given in a Newtonian representation we show how Horner-like transformations ("shift transformations") yield the divided differences needed in each iteration step. In particular, we consider an iteration method given by Larkin [5] and derive an equivalent version of this method fitting into this context. Monotonic convergence to real roots of real polynomials is investigated. Both "shift-" and "nonshift versions" of several root finding methods are tested and compared with respect to their numerical behavior.

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

  • [1] W. Gautschi, "On the condition of algebraic equations," Numer. Math., v. 21, 1973, pp. 405-424. MR 0339478 (49:4237)
  • [2] E. Hansen & M. Patrick, "A family of root finding methods," Numer. Math., v. 27, 1977, pp. 257-269. MR 0433858 (55:6829)
  • [3] P. Henrici, Applied and Computational Complex Analysis, Wiley, New York, 1974. MR 0372162 (51:8378)
  • [4] F. M. Larkin, "Root-finding by fitting rational functions," Math. Comp., v. 35, 1980, pp. 803-816. MR 572858 (81k:65049)
  • [5] F. M. Larkin, "Root-finding by divided differences," Numer. Math., v. 37, 1981, pp. 93-104. MR 615893 (82f:65058)
  • [6] J. F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, N.J., 1964. MR 0169356 (29:6607)
  • [7] W. Werner, On the Simultaneous Determination of Polynomial Roots, Lecture Notes in Math., Vol. 953, Springer-Verlag, Berlin and New York, 1982, pp. 188-202. MR 678620 (84a:12003)
  • [8] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, N.J., 1963. MR 0161456 (28:4661)
  • [9] M. A. Jenkins & J. F. Traub, "A three-stage algorithm for real polynomials using quadratic iteration," SIAM J. Numer. Anal., v. 7, 1970, pp. 545-566. MR 0279995 (43:5716)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H05

Retrieve articles in all journals with MSC: 65H05

Additional Information

Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society