Optimal partitioning of Newton’s method for calculating roots
HTML articles powered by AMS MathViewer
 by Günter Meinardus and G. D. Taylor PDF
 Math. Comp. 35 (1980), 12211230 Request permission
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.References

N. I. ACHIESER, Theory of Approximations, Ungar, New York, 1956.
M.ANDREWS, S. F. McCORMICK & G. D. TAYLOR, "Evaluation of functions on microprocessors: Square root," Comput. Math. Appl., v. 4, 1978, pp. 359367.
M. ANDREWS, S. F. McCORMICK & G. D. TAYLOR, Evaluation of the Square Root Function on Microprocessors, Proc. of ACM, Houston, Texas, October 1976, pp. 185191.
 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, DOI 10.1147/rd.164.0380 W. J. CODY, "Doubleprecision square root for the CDC3600," Comm. ACM, v. 7, 1964, pp. 715718.
 John B. Gibson, Optimal rational starting approximations, J. Approximation Theory 12 (1974), 182–198. MR 381244, DOI 10.1016/00219045(74)900471
 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, DOI 10.1002/nme.1620090204
 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, DOI 10.1145/362848.362861
 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, DOI 10.1090/S00255718196501785873
 G. Meinardus and G. D. Taylor, Optimal starting approximations for iterative schemes, J. Approximation Theory 9 (1973), 1–19. MR 422964, DOI 10.1016/00219045(73)901081
 David G. Moursund, Optimal starting values for NewtonRaphson calculation of $\surd x$, Comm. ACM 10 (1967), 430–432. MR 0240952, DOI 10.1145/363427.363454
 D. G. Moursund and G. D. Taylor, Optimal starting values for the NewtonRaphson calculation of inverses of certain functions, SIAM J. Numer. Anal. 5 (1968), 138–150. MR 225481, DOI 10.1137/0705011
 Ichizo Ninomiya, Best rational starting approximations and improved Newton iteration for the square root, Math. Comp. 24 (1970), 391–404. MR 273809, DOI 10.1090/S00255718197002738094
 David L. Phillips, Generalized logarithmic error and Newton’s method for the $m$th root, Math. Comp. 24 (1970), 383–389. MR 283982, DOI 10.1090/S0025571819700283982X
 I. F. Ganžela and C. T. Fike, Sterbenz, P. H, Math. Comp. 23 (1969), 313–318. MR 245199, DOI 10.1090/S00255718196902451996
 G. D. Taylor, Optimal starting approximations for Newton’s method, J. Approximation Theory 3 (1970), 156–163. MR 263234, DOI 10.1016/00219045(70)900249 J. S. WALTHER, A Unified Algorithm for Elementary Functions, Proc. AFIPS, Spring Joint Computer Conference, v. 38, 1971, pp. 379385.
 M. Wayne Wilson, Optimal starting approximations for generating square root for slow or no divide, Comm. ACM 13 (1970), 559–560. MR 0285114, DOI 10.1145/362736.362750
Additional Information
 © Copyright 1980 American Mathematical Society
 Journal: Math. Comp. 35 (1980), 12211230
 MSC: Primary 65H05; Secondary 41A30
 DOI: https://doi.org/10.1090/S00255718198005834995
 MathSciNet review: 583499