Algorithm 748: enclosing zeros of continuous functions

ABSTRACT

Two efficient algorithms for enclosing a zero of a continuous function are presented. They are similar to the recent methods, but together with quadratic interpolation they make essential use of inverse cubic interpolation as well. Since asymptotically the inverse cubic interpolation is always chosen by the algorithms, they achieve higher-efficiency indices: 1.6529… for the first algorithm, and 1.6686… for the second one. It is proved that the second algorithm is optimal in a certain family. Numerical experiments show that the two new methods compare well with recent methods, as well as with the efficient solvers of Dekker, Brent, Bus and Dekker, and Le. The second method from the present article has the best behavior of all 12 methods especially when the termination tolerance is small.

REFERENCES

• 1: ALEFELD, G. AND POTRA, F.A. 1988. On two higher order enclosing methods of J. W. Schmidt. Z. angew. Math. Mech. 68, 8, 331-337.
• 2: Götz E. Alefeld , Florian A. Potra, Some efficient methods for enclosing simple zeros of nonlinear equations, BIT, v.32 n.2, p.334-344, 1992 [doi>10.1007/BF01994885]
• 3: ALEFELD, G., POTRA, F. A., AND SHI, Y. 1993. On enclosing simple roots of nonhnear equations. Math. Comput. 61,733-744
• 4: ANDERSON, N. AND BJORCK, A. 1973. A new high order method of regula falsi type for computing a root of an equation. BIT 13, 253-264.
• 5: ATKINSON, K. 1989. An Introductzon to Numer~calAnalysis. John Wiley & Sons, New York.
• 6: BRENT, R. P. 1972. Algorithms for Minzmizatzon Without Derivatwes. Prentice-Hall, Englewood Cliffs, N.J.
• 7: J. C. P. Bus , T. J. Dekker, Two Efficient Algorithms with Guaranteed Convergence for Finding a Zero of a Function, ACM Transactions on Mathematical Software (TOMS), v.1 n.4, p.330-345, Dec. 1975 [doi>10.1145/355656.355659]
• 8: DEKKER, T.J. 1969. Finding a zero by means of successive linear interpolation. In Constructive Aspects of the Fundamental Theorem of Algebra, B. Dejon and P. Henrici, Eds. Wiley Interscience, New York.
• 9: KINC, R.F. 1976. Methods without secant steps for finding a bracketed root. Computing 17, 49-57.
• 10: D. Le, An efficient derivative-free method for solving nonlinear equations, ACM Transactions on Mathematical Software (TOMS), v.11 n.3, p.250-262, Sept. 1985 [doi>10.1145/214408.214416]
• 11: OSTROWSKI, A.M. 1973. Solutwn of Equations ~n Banach Spaces. Academic Press, New York.
• 12: POTRA, F. A. 1989. On Q-order and R-order of convergence J. Optim. Theor. Appl. 63, 415-431.
• 13: SCHMIDT, J.W. 1971. Eingrenzung der Lbsfingen nichtlinearer Gleichungen mit hdherer Konvergenzgeschwindigkeit. Computing 8, 208-215.
• 14: STOER, J. AND BULIRSCH, R. 1980. Introductwn to Numerical Analysis. Springer-Verlag, New York

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Convergence

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods

General Terms:
Algorithms, Theory

Keywords:
asymptotic efficiency index, enclosing method, inverse cubic interpolation, quadratic interpolation, simple root