Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A rapid robust rootfinder

Author: Richard I. Shrager
Journal: Math. Comp. 44 (1985), 151-165
MSC: Primary 65H05
MathSciNet review: 771037
Full-text 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 $ {F_X}$ with brackets A and B, i.e., $ \operatorname{sign}({F_A}) = - \operatorname{sign}({F_B}) \ne 0$, the algorithm finds a zero of F, $ A < X < B$. Alternately, a crossover pair is found, i.e., (X, Y): $ \operatorname{sign}({F_X}) = - \operatorname{sign}({F_Y}) \ne 0$ where there is no floating-point number in the system between X and Y. This feature allows full use of machine precision. Optionally, a tolerance $ {\text{TOL}} > 0$ may be given, to permit termination when $ \vert Y - X\vert < {\text{TOL}}$. 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 $ dF/dX$. Other merits of the algorithm are: robust calculation, efficient three-point interpolation, and superior behavior in bad cases. The algorithm is tested and compared with others.

References [Enhancements On Off] (What's this?)

  • [1] Richard P. Brent, Algorithms for minimization without derivatives, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. Prentice-Hall Series in Automatic Computation. MR 0339493
  • [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,
  • [3] T. J. Dekker, Finding a zero by means of successive linear interpolation, Constructive Aspects of the Fundamental Theorem of Algebra (Proc. Sympos., Zürich-Rüschlikon, 1967) Wiley-Interscience, New York, 1969, pp. 37–48. MR 0256551
  • [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, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1977. Prentice-Hall Series in Automatic Computation. MR 0458783
  • [6] William M. Kahan, Personal calculator has key to solve any equation 𝑓(𝑥)=0, Hewlett-Packard J. 30 (1979), no. 12, 20–26. MR 574853
  • [7] A. M. Ostrowski, Solution of equations and systems of equations, Second edition. Pure and Applied Mathematics, Vol. 9, Academic Press, New York-London, 1966. MR 0216746
  • [8] D. Stevenson & IEEE Task P754 (A working group), "A proposed standard for binary floating-point arithmetic," Computer, v. 12, no. 3, 1981, pp. 51-62.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H05

Retrieve articles in all journals with MSC: 65H05

Additional Information

Article copyright: © Copyright 1985 American Mathematical Society