Browse Prior Art Database

For Which Error Criteria Can We Solve Nonlinear Equations?

IP.com Disclosure Number: IPCOM000127969D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 21 page(s) / 37K

Publishing Venue

Software Patent Institute

Related People

K.Sikorski: AUTHOR [+4]

Abstract

For which error criteria can we solve a nonlinear scalar equation f(x) = 0 where f is a real function on the interval [a,bJ? The information on f consists of n adaptive eval-uations of arbitrary linear functionals and an algorithm is any mapping based on these evaluations. For the root criterion we prove there does not exist an algorithm to find a point x such that Ix-al S E where cs is a zero of f and E < (b-a)/2. This holds for arbitrary n andfor the class of infinitely many times differentiable functions with all simple zeros. We. do not assume that f (a) f (b) S 0. For the residual criterion we show almost optimal infor-mation and algorithm. More precisely, we prove that if x is the value computed by our algorithm then f(x) = 0(n r) where r measures the smoothness of the class of functions f. Finally a general error criterion is introduced and some of our results are generalized. 2

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

Page 1 of 21

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

For Which Error Criteria Can We Solve Nonlinear Equations?

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

H. Wozniakowski Institute of Informatics and University of Warsaw Warsaw, Poland

January 1983

Department of Computer Science Columbia University New York, New York 10027 1

Abstract

For which error criteria can we solve a nonlinear scalar equation f(x) = 0 where f is a real function on the interval [a,bJ? The information on f consists of n adaptive eval-uations of arbitrary linear functionals and an algorithm is any mapping based on these evaluations. For the root criterion we prove there does not exist an algorithm to find a point x such that Ix-al S E where cs is a zero of f and E < (b-a)/2. This holds for arbitrary n andfor the class of infinitely many times differentiable functions with all simple zeros. We. do not assume that f (a) f (b) S 0. For the residual criterion we show almost optimal infor-mation and algorithm. More precisely, we prove that if x is the value computed by our algorithm then f(x) = 0(n r) where r measures the smoothness of the class of functions f. Finally a general error criterion is introduced and some of our results are generalized. 2

1. introduction

A number of error criteria are commonly used in practice for the approximate solution of a nonlinear scalar equation

(Equation Omitted)

For instance one may want to find a number x such that one of the following conditions is satisfied:

root criterion

(1.2) relative root criterion

(1.3) residual criterion

(1.4) relative residual criterion

(Equation Omitted)

where cc is a real zero of f and E is a given nonnegative number. We study for which error criteria it is possible to find such a number x and, if it is possible, what is an optimal algorithm for

Columbia University Page 1 Dec 31, 1983

Page 2 of 21

For Which Error Criteria Can We Solve Nonlinear Equations?

finding x. We assume that f belongs to a class of functions and that we know n adaptive evaluations of arbitrary linear func- tionals on f. By an algorithm we mean a mapping depending on these n evaluations; see [6]. For the root criterion we prove that there does not exist an algorithm to find x satisfying (1. 1) with

(Equation Omitted)

for 3

the class of infinitely many times differentiable functions with simple zeros and whose seminorm is bounded by one. (We do not assume that f has opposite signs at a and b.) Note that this result holds for arbitrary large n and indepen-dently of which linear functionals are evaluated. The same result holds for the relative root criterion with

(Equation Omitted)

and a 2 0. For the residual criterion we deal with the class of functions having zeros and whose (r-l)-4t derivative is abso-lutely continuous and the infinity norm of the r-th derivative is bounded by one, r 2 1. We find almost optimal information and algori...