A rapid robust rootfinder
Author:
Richard I. Shrager
Journal:
Math. Comp. 44 (1985), 151165
MSC:
Primary 65H05
MathSciNet review:
771037
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A numerical algorithm is presented for solving one nonlinear equation in one real variable. Given with brackets A and B, i.e., , the algorithm finds a zero of F, . Alternately, a crossover pair is found, i.e., (X, Y): where there is no floatingpoint number in the system between X and Y. This feature allows full use of machine precision. Optionally, a tolerance may be given, to permit termination when . The method, once rapid convergence sets in, is alternation of one linear interpolation or extrapolation with one inverse quadratic interpolation. The resulting asymptotic convergence rate is competitive with other methods that refine both brackets and do not require . Other merits of the algorithm are: robust calculation, efficient threepoint interpolation, and superior behavior in bad cases. The algorithm is tested and compared with others.
 [1]
Richard
P. Brent, Algorithms for minimization without derivatives,
PrenticeHall Inc., Englewood Cliffs, N.J., 1973. PrenticeHall Series in
Automatic Computation. MR 0339493
(49 #4251)
 [2]
J.
C. P. Bus and T.
J. Dekker, Two efficient algorithms with guaranteed convergence for
finding a zero of a function, ACM Trans. Math. Software
1 (1975), no. 4, 330–345. MR 0386254
(52 #7112)
 [3]
T.
J. Dekker, Finding a zero by means of successive linear
interpolation, Constructive Aspects of the Fundamental Theorem of
Algebra (Proc. Sympos., ZürichRüschlikon, 1967),
WileyInterscience, New York, 1969, pp. 37–48. MR 0256551
(41 #1207)
 [4]
T. J. Dekker, "Correctness proof and machine arithmetic," in Performance Evaluation of Numerical Software (L. D. Fosdick, ed.), Elsevier, New York, 1979.
 [5]
George
E. Forsythe, Michael
A. Malcolm, and Cleve
B. Moler, Computer methods for mathematical computations,
PrenticeHall Inc., Englewood Cliffs, N.J., 1977. PrenticeHall Series in
Automatic Computation. MR 0458783
(56 #16983)
 [6]
William
M. Kahan, Personal calculator has key to solve any equation
𝑓(𝑥)=0, HewlettPackard J. 30 (1979),
no. 12, 20–26. MR 574853
(81k:65002)
 [7]
A.
M. Ostrowski, Solution of equations and systems of equations,
Second edition. Pure and Applied Mathematics, Vol. 9, Academic Press, New
York, 1966. MR
0216746 (35 #7575)
 [8]
D. Stevenson & IEEE Task P754 (A working group), "A proposed standard for binary floatingpoint arithmetic," Computer, v. 12, no. 3, 1981, pp. 5162.
 [1]
 R. P. Brent, Algorithms for Minimization without Derivatives, PrenticeHall, Englewood Cliffs, N. J., 1973. MR 0339493 (49:4251)
 [2]
 J. C. P. Bus & T. J. Dekker, "Two efficient algorithms with guaranteed convergence for finding a zero of a function," ACM Trans. Math. Software, v. 1, no. 4, 1975, pp. 330345. MR 0386254 (52:7112)
 [3]
 T. J. Dekker, "Finding a zero by means of successive linear interpolation," in Constructive Aspects of the Fundamental Theorem of Algebra (B. Dejon and P. Henrici, eds.), WileyInterscience, London, 1969. MR 0256551 (41:1207)
 [4]
 T. J. Dekker, "Correctness proof and machine arithmetic," in Performance Evaluation of Numerical Software (L. D. Fosdick, ed.), Elsevier, New York, 1979.
 [5]
 G. E. Forsythe, M. A. Malcolm & C. B. Moler, Computer Methods for Mathematical Computations, PrenticeHall, Englewood Cliffs, N. J., 1977. MR 0458783 (56:16983)
 [6]
 W. M. Kahan, "Personal calculator has key to solve any equation ," HewlettPackard J., Dec., 1979, pp. 2026. MR 574853 (81k:65002)
 [7]
 A. M. Ostrowski, Solution of Equations and Systems of Equations, Academic Press, New York, 1960; or 2nd ed., 1966. MR 0216746 (35:7575)
 [8]
 D. Stevenson & IEEE Task P754 (A working group), "A proposed standard for binary floatingpoint arithmetic," Computer, v. 12, no. 3, 1981, pp. 5162.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H05
Retrieve articles in all journals
with MSC:
65H05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198507710378
PII:
S 00255718(1985)07710378
Article copyright:
© Copyright 1985 American Mathematical Society
