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

DOI:
https://doi.org/10.1090/S0025-5718-1985-0790651-7

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.

**[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)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65H05

Retrieve articles in all journals with MSC: 65H05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1985-0790651-7

Article copyright:
© Copyright 1985
American Mathematical Society