An infinite precision bracketing algorithm with guaranteed convergence (Q1293733)

The bisection and the secant method are both well-known examples of bracketing algorithms for determining with prescribed accuracy the roots of a given function (typically a polynomial). However, in the case of finite precision arithmetics, some problems arise. Assume for a minute, that the number of bits used is sufficient to determine an interval of the required length. Then the computational cost can be given in terms of the number of function evaluations. However, for practical purposes, it is desirable not to work with fixed accuracy but to let the number bits used depend on the problem. For example, recall the fact that it is quite easy to test two real numbers, say, \(x\) and \(y\), for \(x<y\) or \(x>y\), but that there is no effective procedure to decide whether or not the given two numbers are equal. Consequently, one has to consider the bit model of computation where the cost of evaluating the functions depends on the values of the argument as well as the number of required digits. Using the complexity measure proposed in the present paper, the authors prove that convergence of the classical bisection method is not guaranteed when no information about the behavior of the function in question is available. In addition, the authors establish a modification with guaranteed convergence. Furthermore, an upper bound for its computational costs is given.