For which error criteria can we solve nonlinear equations? (Q1086984)

For the solution of an equation \(f(x)=0\), involving a real function f on an interval [a,b], the information on f is assumed to consist of sequential (adaptive) evaluations of arbitrary functionals. The error of an algorithm based on these evaluations is defined by its worst performance. For the root criterion as error measure it is shown that there does not exist an algorithm for finding a point x such that \(| x-\alpha | \leq \epsilon\) where \(\alpha\) is a zero of f and \(\epsilon <(b-a)/2\). This holds for arbitrary information and infinitely differentiable f with simple zeros, but without assuming f(a)f(b)\(\leq 0\). For the residual criterion some almost optimal information and algorithm is given and it is shown that for n functional evaluations the residual at the computed point x satisfies \(f(x)=O(n^{-r})\) as \(n\to \infty\), where r defines the smoothness class of f. These results are then generalized to a more general error criterion.