Optimal partitioning of Newton's method for calculating roots
Authors:
Günter Meinardus and G. D. Taylor
Journal:
Math. Comp. 35 (1980), 12211230
MSC:
Primary 65H05; Secondary 41A30
MathSciNet review:
583499
Fulltext 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. 359367.
 [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. 185191.
 [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 0336965
(49 #1738)
 [5]
W. J. CODY, "Doubleprecision square root for the CDC3600," Comm. ACM, v. 7, 1964, pp. 715718.
 [6]
John
B. Gibson, Optimal rational starting approximations, J.
Approximation Theory 12 (1974), 182–198. MR 0381244
(52 #2141)
 [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 0454460
(56 #12711)
 [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
(44 #2333)
 [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 0178587
(31 #2844), http://dx.doi.org/10.1090/S00255718196501785873
 [10]
G.
Meinardus and G.
D. Taylor, Optimal starting approximations for iterative
schemes, J. Approximation Theory 9 (1973),
1–19. MR
0422964 (54 #10948)
 [11]
David
G. Moursund, Optimal starting values for NewtonRaphson calculation
of √𝑥, Comm. ACM 10 (1967),
430–432. MR 0240952
(39 #2297)
 [12]
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 0225481
(37 #1074)
 [13]
Ichizo
Ninomiya, Best rational starting approximations
and improved Newton iteration for the square root, Math. Comp. 24 (1970), 391–404. MR 0273809
(42 #8685), http://dx.doi.org/10.1090/S00255718197002738094
 [14]
David
L. Phillips, Generalized logarithmic error and
Newton’s method for the 𝑚th root., Math. Comp. 24 (1970), 383–389. MR 0283982
(44 #1212), http://dx.doi.org/10.1090/S0025571819700283982X
 [15]
I.
F. Ganžela and C.
T. Fike, Sterbenz, P. H, Math. Comp. 23 (1969), 313–318. MR 0245199
(39 #6511), http://dx.doi.org/10.1090/S00255718196902451996
 [16]
G.
D. Taylor, Optimal starting approximations for Newton’s
method, J. Approximation Theory 3 (1970),
156–163. MR 0263234
(41 #7839)
 [17]
J. S. WALTHER, A Unified Algorithm for Elementary Functions, Proc. AFIPS, Spring Joint Computer Conference, v. 38, 1971, pp. 379385.
 [18]
M.
Wayne Wilson, Optimal starting approximations for generating square
root for slow or no divide, Comm. ACM 13 (1970),
559–560. MR 0285114
(44 #2338)
 [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. 359367.
 [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. 185191.
 [4]
 T. C. CHEN, The Automatic Computation of Exponentials, Logarithms, Ratios and Square Roots, IBM Research Memo, RJ970 (#16884), San Jose, Calif., February 1972. MR 0336965 (49:1738)
 [5]
 W. J. CODY, "Doubleprecision square root for the CDC3600," Comm. ACM, v. 7, 1964, pp. 715718.
 [6]
 J. B. GIBSON, "Optimal rational starting approximations," J. Approximation Theory, v. 12, 1974, pp. 182189. MR 0381244 (52:2141)
 [7]
 E. H. KAUFMAN, JR. & G. D. TAYLOR, "Uniform rational approximation of functions of several variables," Internat. J. Numer. Methods Engrg., v. 9, 1975, pp. 297323. MR 0454460 (56:12711)
 [8]
 R. F. KING & D. L. PHILLIPS, "The logarithmic error and Newton's method for the square root," Comm. ACM, v. 12, 1969, pp. 8788. MR 0285109 (44:2333)
 [9]
 W. JAMES & P. JARRATT, "The generation of square roots on a computer with rapid multiplication compared with division," Math. Comp., v. 19, 1965, pp. 497502. MR 0178587 (31:2844)
 [10]
 G. MEINARDUS & G. D. TAYLOR, "Optimal starting approximations for iterative schemes," J. Approximation Theory, v. 9, 1970, pp. 119. MR 0422964 (54:10948)
 [11]
 D. G. MOURSUND, "Optimal starting values for the NewtonRaphson calculation of ," Comm. ACM, v. 10, 1967, pp. 430432. MR 0240952 (39:2297)
 [12]
 D. G. MOURSUND & G. D. TAYLOR, "Optimal starting values for the NewtonRaphson calculation of inverses of certain functions," SIAM J. Numer. Anal., v. 5, 1968, pp. 138150. MR 0225481 (37:1074)
 [13]
 I. NINOMIYA, "Best rational starting approximations and improved Newton iteration for the square root," Math. Comp., v. 24, 1970, pp. 391404. MR 0273809 (42:8685)
 [14]
 D. L. PHILLIPS, "Generalized logarithmic error and Newton's method for the mth root," Math. Comp., . v. 24, 1970, pp. 383389. MR 0283982 (44:1212)
 [15]
 P. H. STERBENZ & C. T. FIKE, "Optimal starting approximations for Newton's method," Math. Comp., v. 23, 1969, pp. 313318. MR 0245199 (39:6511)
 [16]
 G. D. TAYLOR, "Optimal starting approximations for Newton's method," J. Approximation Theory, v. 3, 1970, pp. 156163. MR 0263234 (41:7839)
 [17]
 J. S. WALTHER, A Unified Algorithm for Elementary Functions, Proc. AFIPS, Spring Joint Computer Conference, v. 38, 1971, pp. 379385.
 [18]
 M. W. WILSON, "Optimal starting approximations for generating square root for slow or no divide," Comm. ACM, v. 13, 1970, pp. 559560. MR 0285114 (44:2338)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H05,
41A30
Retrieve articles in all journals
with MSC:
65H05,
41A30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198005834995
PII:
S 00255718(1980)05834995
Keywords:
Computation of roots,
optimal initialization of Newton's method for computing roots,
best piecewise starting approximations
Article copyright:
© Copyright 1980
American Mathematical Society
