Optimal solution of nonlinear equations satisfying a Lipschitz condition

Summary For a given nonnegative we seek a pointx ^* such that |f(x ^*)| wheref is a nonlinear transformation of the cubeB=0,1] ^m into (or ^p ,p>1) satisfying a Lipschitz condition with the constantK and having a zero inB.The information operator onf consists ofn values of arbitrary linear functionals which are computed adaptively. The pointx ^* is constructed by means of an algorithm which is a mapping depending on the information operator. We find an optimal algorithm, i.e., algorithm with the smallest error, which usesn function evaluations computed adaptively. We also exhibit nearly optimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is almost minimal. Nearly optimal information operators consists ofn nonadaptive function evaluations at equispaced pointsx _j in the cubeB. This result exhibits the superiority of the T. Aird and J. Rice procedure ZSRCH (IMSL library 1]) over Sobol's approach 7] for solving nonlinear equations in our class of functions. We also prove that the simple search algorithm which yields a pointx ^*=x _k such that is nearly optimal. The complexity, i.e., the minimal cost of solving our problem is roughly equal to (K/) ^m .