ISSN:
0945-3245
Keywords:
AMS(MOS): 65H10
;
CR: G1.5
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Summary We seek a approximation to a zero of an infinitely differentiable functionf: [0, 1]→ℜ such thatf(0)≦0 andf(1)≧0. It is known that the error of the bisection method usingn 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 forn 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 theasymptotic 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 classF of functions having zeros ofinfinite multiplicity and information consisting of evaluations of continuous linear functionals. Assuming that everyf inF has zeroes withbounded multiplicity, there are known hybrid methods which have at least quadratic rate of convergence asn tends to infinity, see e.g., Brent [1], Traub [4] and Sect. 1.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01386421
Permalink
