Optimal Solution of Nonlinear Equations Satisfying a Lipschitz Condition

Sikorski, Krzysztof A.

For a given nonnegative e we seek a point x* such that if(x*)[ <e where f is a nonlinear transformation of the cube B = [0, 1] m into I( (or F, p, p>l) satisfying a Lipschitz condition with the constant K and having a zero in B. The information operator on f consists of n values of arbitrary linear functionals which are computed adaptively. The point x* 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 uses n 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 of n nonadaptive function evaluations at equispaced points xj in the cube B. 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 point x*=x k such that If(Xk)]= min If(xj)l is nearly optimal. The complexity, i.e., the minimal cost of solving our problem is roughly equal to (K/e)m.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-042-83
Published Here
October 19, 2011