Browse Prior Art Database

Optimal Solution of Nonlinear Equations Satisfying a Lipschitz Condition

IP.com Disclosure Number: IPCOM000127970D
Original Publication Date: 1970-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 22 page(s) / 40K

Publishing Venue

Software Patent Institute

Related People

K. Sikorski: AUTHOR [+3]

Abstract

For a given nonnegative E we seek a point x* that [Equation ommitted] where f is a nonlinear transformation of the cube [Equation ommitted] 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 consist 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 non-linear equations in our class of functions. We also prove that the simple search algorithm which yields a point [Equation ommitted] such that [Equation ommitted] is nearly optimal. The complexity, [Equation ommitted] the mirtimal cost of solving our problem is roughly equal to [Equation ommitted]

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 22

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Optimal Solution of Nonlinear Equations Satisfying a Lipschitz Condition

K. Sikorski Department of Computer Science Columbia University New York, New York (On leave from the University of Warsaw)

AMS (MOS) Subject classifications (1970) Primary 65H10.

Key words and phrases: algorithm, complexity, information operator, Lipschitz condition, nonlinear equations.

Abstract.

For a given nonnegative E we seek a point x* that

(Equation Omitted)

where f is a nonlinear transformation of the cube

(Equation Omitted)

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 consist 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 non- linear equations in our class of functions. We also prove that the simple search algorithm which yields a point

(Equation Omitted)

such that

(Equation Omitted)

is nearly optimal. The complexity,

(Equation Omitted)

the mirtimal cost of solving our problem is roughly equal to

(Equation Omitted)

Columbia University Page 1 Dec 31, 1970

Page 2 of 22

Optimal Solution of Nonlinear Equations Satisfying a Lipschitz Condition

0. Introduction.

Let B denote the real line, B be the m-dimensional unit cube and let a be a nonnegative number. Two basic error criteria are used for determining an approximate solution x* of a nonlinear equation

(Equation Omitted)

where

(Equation Omitted)

, we show in Section 1 how to transform this to the case p = 1.) Assuming that f(a) = 0 these two error criteria are defined as follows:

(0.2) root criterion:

(Equation Omitted)

(0.3) residual criterion:

(Equation Omitted)

We assume that f belongs to the class F of transformations satisfying a Lipschitz condition in the infinity norm with a constant K and having a zero in B. The information operator Nn on f consists of n function values, or more generaly of n values of arbitrary linear functionals which are computed adaptively. The approximation x* to a is constructed by means of an algorithm V which is a mapping depending on the information operator. It was shown in [6] that there exist functions in F such that for every E < 1/2 itis impossible to find x* 2

satisfying the root criterion (0.2) no matter how large is n and no matter what algorithm is used. Therefore in...