ASYMPTOTIC NEAR OPTIMALITY OF THE BISECTION METHOD

We seek a approximation to a zero of an infinitely differentiable function f: [0, 1]→ℜ such that f(0)≦0 and f(1)≧0. It is known that the error of the bisection method using n function evaluations is 2-(n+1). If the information used are function values, then it is known that bisection information and the bisection algorithm are optimal. Traub and Woźniakowski conjectured in [5] that the bisection information and algorithm are optimal even if far more general information is permitted. They permit adaptive (sequential) evaluations of arbitrary linear functionals and arbitrary transformations of this information as algorithms. This conjecture was established in [2]. That is for n fixed, the bisection information and algorithm are optimal in the worst case setting. Thus nothing is lost by restricting oneself to function values. One may then ask whether bisection is nearly optimal in the asymptotic worst case sense, that is, possesses asymptotically nearly the best rate of convergence. Methods converging fast asymptotically, like Newton or secant type, are of course, widely used in scientific computation. We prove that the answer to this question is positive for the class F of functions having zeros of infinite multiplicity and information consisting of evaluations of continuous linear functionals. Assuming that every f in F has zeroes with bounded multiplicity, there are known hybrid methods which have at least quadratic rate of convergence as n tends to infinity, see e.g., Brent [1], Traub [4] and Sect. 1. © 1990 Springer-Verlag.