1983 Reports
Optimal Solution of Nonlinear Equations Satisfying a Lipschitz Condition
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.
Subjects
Files
- cucs-042-83.pdf application/pdf 772 KB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-042-83
- Published Here
- October 19, 2011