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 Free Access

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]**Walter Gautschi,*On the condition of algebraic equations*, Numer. Math.**21**(1973), 405–424. MR**0339478****[2]**Eldon Hansen and Merrell Patrick,*A family of root finding methods*, Numer. Math.**27**(1976/77), no. 3, 257–269. MR**0433858****[3]**Peter Henrici,*Applied and computational complex analysis*, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Volume 1: Power series—integration—conformal mapping—location of zeros; Pure and Applied Mathematics. MR**0372162****[4]**F. M. Larkin,*Root-finding by fitting rational functions*, Math. Comp.**35**(1980), no. 151, 803–816. MR**572858**, 10.1090/S0025-5718-1980-0572858-2**[5]**F. M. Larkin,*Root finding by divided differences*, Numer. Math.**37**(1981), no. 1, 93–104. MR**615893**, 10.1007/BF01396188**[6]**J. F. Traub,*Iterative methods for the solution of equations*, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR**0169356****[7]**Wilhelm Werner,*On the simultaneous determination of polynomial roots*, Iterative solution of nonlinear systems of equations (Oberwolfach, 1982), Lecture Notes in Math., vol. 953, Springer, Berlin-New York, 1982, pp. 188–202. MR**678620****[8]**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456****[9]**M. A. Jenkins and J. F. Traub,*A three-stage algorithm for real polynomials using quadratic iteration.*, SIAM J. Numer. Anal.**7**(1970), 545–566. MR**0279995**

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