Some Nonlinear Operators Are As Easy To Approximate As The Identity Operator
Original Publication Date: 1982-May-31
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Wasilkowski, G.W.: AUTHOR [+2]
G. W. Wasilkowski
Some Nonlinear Operators
Are As Easy To Approximate
As The Identity Operator
G. W. Wasilkowski
Department of Computer Science
New York, New York
Revised May 1-983
This research was supported in part by the National Science Foundation under
Grant KCS 82-14322.
In this paper we study the following problem. Given an operator s and a subset F of some linear space, approximate
~ ( f )
for any f E Fo possessing only partial information on f. Although all operators S considered here are
that these problems are "equivalent" to the problem of approximating S ( f ) = f , i. e. , S = I. This equivalence pro- vides optimal (or nearly optimal) information and algorithms.
There are many Fapers dealing with the following
problem: approximate an elenent f which belongs to a
subclass FO of a linear normed space possessing only partial
information on f. For many subclasses Fo we know optimal
information, optimal algorithals and we krow that adaptive
information is not more ?owerful than nonadantive infomation.
(see e.g. Cl', [ 4 ! ) . This is an example of a linear problem;
that is one wants to approximate S (f) for a linear operator S.
The situation is quite different for nonlinear problems;
that is one wants to approximate S(f) where S is a nonlinear
operator. Nonlinearity of S usually makes the nroblern of
finding optimal information and optimal algorithms more dif-
In this pa?er we give sufficient conditions for a non-
linear problem to be equivalent to the problem of approximating
S(f) = f. This equivalence leads to optimal (or nearly optimal)
information and algoritk~s
for this nonlinear ?roblent. We will
present some nonlinear problems for which these sufficient
We summarize the contents of this Taper. In Section 2
we present the basic definitions and results which will be
needed in this paper. We define what we mean by a problem,
information and an algorithm. W e recall the concept of the error of an algorithm and of the radius of information. W e
show how these concepts become simpler for the problem with
s = I i. e., S (f) = f. In Section 3 we prove two simple
lemmas which give sufficient conditions for a nonlinear pro- blem to be equivalent to the prcblem with S = I. W e illustrate
these lemmas by such problems as approximation of S ( f ) - - - f
or S (f) = J f where f is a function. In Section 4 we consider the problem of estimating S(f) = jlfjl. In the last section w e study three problems which are related to the problem of finding the minimum of a given function f.
For all these problems we exhibit nearly optimal infor-
mation and nearly optimal alg...