Browse Prior Art Database

Optimal Integration for Functions of Bounded variation

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

Publishing Venue

Software Patent Institute

Related People

J. F. Traub: AUTHOR [+4]

Abstract

The unique optimal information and the unique optimal linear algorithm are obtained for the integration of functions of bounded variation.

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Optimal Integration for Functions of Bounded variation

J. F. Traub Departments of Computer Science and Mathematic Columbia University New York, New York 10027

and

D. Le:e Department of Computer Science Columbia University New York, New York 10027

May 1983

This research was supported in part by the National Science Foundation under Grant MCS- 7823676 and the Advanced Research Projects Agency under Contract. N00039-82-C-0427.

Abstract.

The unique optimal information and the unique optimal linear algorithm are obtained for the integration of functions of bounded variation.

1. Introduction

For a class of real valued functions, we seek an approxi-mation to the integral of any function in the class, provided that the function values are given at n points. A summary of what is currently known about this problem may be found in [1, Section 6.4]. in this paper, we study the class F of real valued functions of uniformly bounded variation on the unit interval. concepts used in this paper are defined for very general settings in [1] and [2]. To aid the reader, they are de- fined in this paper for the special case of integration. we summarize the results of this paper. (i) If n function evaluation are used, then the intrinsic uncertainty in -the integral is at least

(Equation Omitted)

function evaluations guarantee an --approximation. (ii) The optimal function evaluation points are

(Equation Omitted)

and this optimal information is unique.

(iii) The optimal algorithm using the optimal information

is the averaging algorithm:

(Equation Omitted)

is the unique optimal linear algorithm. (iv) The averaging algorithm is within at most one unit of being an optimal complexity algorithm. (v) The averaging algorithm is only a constant factor better than the composite trapezoidal and Simpson algorithms.

Columbia University Page 1 Dec 31, 1983

Page 2 of 12

Optimal Integration for Functions of Bounded variation

2. Basic Conceots.

R function f defined on the unit interval is of bounded variation if there exists M > 0 such that for any partition

(Equation Omitted)

The total variation of f is defined as

(Equation Omitted)

We say a class F of rr functions is of uniformly bounded variation if

(Equation Omitted)

and

(Equation Omitted)

where B > 0. Without loss of generality, we take the bound B to be unity. We seek an approximation to

(Equation Omitted)

given function values at an n-partition, that is, at points

(Equation Omitted)

That is, the information N is defined as

(Equation Omitted)

and

(Equation Omitted)

We denote

(Equation Omitted)

We have

(Equation Omitted)

(Equation Omitted)

The pZoof is trivial, and is omitted. <> Given information N and f E F, the set of indistin- guishable elements from f in F is

Columbia University Page 2 Dec 31, 1983

Page 3 of 12

Optimal Integration for Functions of Bounded variation

(Equation Omitted)

The following lemma measures the uncertainty in the integral caus...