Optimal partitioning of Newton's method for calculating roots

Authors:
Günter Meinardus and G. D. Taylor

Journal:
Math. Comp. **35** (1980), 1221-1230

MSC:
Primary 65H05; Secondary 41A30

DOI:
https://doi.org/10.1090/S0025-5718-1980-0583499-5

MathSciNet review:
583499

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, an algorithm is given for calculating roots via Newton's method initialized with a piecewise best starting approximation. The piecewise best starting approximation corresponds to an optimal partitioning of the interval of the domain of Newton's method. Explicit formulas are given when piecewise linear polynomials are used for the best starting approximations. Specific tables are given for square roots, cube roots and reciprocal square roots.

**[1]**N. I. ACHIESER,*Theory of Approximations*, Ungar, New York, 1956.**[2]**M.ANDREWS, S. F. McCORMICK & G. D. TAYLOR, "Evaluation of functions on microprocessors: Square root,"*Comput. Math. Appl.*, v. 4, 1978, pp. 359-367.**[3]**M. ANDREWS, S. F. McCORMICK & G. D. TAYLOR,*Evaluation of the Square Root Function on Microprocessors*, Proc. of ACM, Houston, Texas, October 1976, pp. 185-191.**[4]**Tien Chi Chen,*Automatic computation of exponentials, logarithms, ratios and square roots*, IBM J. Res. Develop.**16**(1972), 380–388. Mathematics of numerical computation. MR**336965**, https://doi.org/10.1147/rd.164.0380**[5]**W. J. CODY, "Double-precision square root for the CDC-3600,"*Comm. ACM*, v. 7, 1964, pp. 715-718.**[6]**John B. Gibson,*Optimal rational starting approximations*, J. Approximation Theory**12**(1974), 182–198. MR**381244**, https://doi.org/10.1016/0021-9045(74)90047-1**[7]**E. H. Kaufman Jr. and G. D. Taylor,*Uniform rational approximation of functions of several variables*, Internat. J. Numer. Methods Engrg.**9**(1975), no. 2, 297–323. MR**454460**, https://doi.org/10.1002/nme.1620090204**[8]**Richard F. King and David L. Phillips,*The logarithmic error and Newton’s method for the square root*, Comm. ACM**12**(1969), 87–88. MR**0285109**, https://doi.org/10.1145/362848.362861**[9]**Wendy James and P. Jarratt,*The generation of square roots on a computer with rapid multiplication compared with division*, Math. Comp.**19**(1965), 497–500. MR**178587**, https://doi.org/10.1090/S0025-5718-1965-0178587-3**[10]**G. Meinardus and G. D. Taylor,*Optimal starting approximations for iterative schemes*, J. Approximation Theory**9**(1973), 1–19. MR**422964**, https://doi.org/10.1016/0021-9045(73)90108-1**[11]**David G. Moursund,*Optimal starting values for Newton-Raphson calculation of √𝑥*, Comm. ACM**10**(1967), 430–432. MR**0240952**, https://doi.org/10.1145/363427.363454**[12]**D. G. Moursund and G. D. Taylor,*Optimal starting values for the Newton-Raphson calculation of inverses of certain functions*, SIAM J. Numer. Anal.**5**(1968), 138–150. MR**225481**, https://doi.org/10.1137/0705011**[13]**Ichizo Ninomiya,*Best rational starting approximations and improved Newton iteration for the square root*, Math. Comp.**24**(1970), 391–404. MR**273809**, https://doi.org/10.1090/S0025-5718-1970-0273809-4**[14]**David L. Phillips,*Generalized logarithmic error and Newton’s method for the 𝑚th root*, Math. Comp.**24**(1970), 383–389. MR**283982**, https://doi.org/10.1090/S0025-5718-1970-0283982-X**[15]**I. F. Ganžela and C. T. Fike,*Sterbenz, P. H*, Math. Comp.**23**(1969), 313–318. MR**245199**, https://doi.org/10.1090/S0025-5718-1969-0245199-6**[16]**G. D. Taylor,*Optimal starting approximations for Newton’s method*, J. Approximation Theory**3**(1970), 156–163. MR**263234**, https://doi.org/10.1016/0021-9045(70)90024-9**[17]**J. S. WALTHER,*A Unified Algorithm for Elementary Functions*, Proc. AFIPS, Spring Joint Computer Conference, v. 38, 1971, pp. 379-385.**[18]**M. Wayne Wilson,*Optimal starting approximations for generating square root for slow or no divide*, Comm. ACM**13**(1970), 559–560. MR**0285114**, https://doi.org/10.1145/362736.362750

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

Retrieve articles in all journals with MSC: 65H05, 41A30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1980-0583499-5

Keywords:
Computation of roots,
optimal initialization of Newton's method for computing roots,
best piecewise starting approximations

Article copyright:
© Copyright 1980
American Mathematical Society