Deterministic and Stochastic Error Bounds in Numerical Analysis

In these notes different deterministic and stochastic error bounds of numerical analysis are investigated. For many computational problems we have only partial information (such as n function values) and consequently they can only be solved with uncertain

  • PDF / 7,397,481 Bytes
  • 118 Pages / 468 x 684 pts Page_size
  • 89 Downloads / 212 Views

DOWNLOAD

REPORT


1349 Erich Novak

Deterministic and Stochastic Error Bounds in Numerical Analysis

Springer-Verlag Berlin Heidelberg New York London Paris Tokyo

Author

Erich Novak Mathematisches Institut, Universitat Erlanqen-Nurnberq Bismarckstr. 11/2, D-8520 Erlangen, Federal Republic of Germany

Mathematics Subject Classification (1980): 65-02, 41 A46, 65C05, 65J05, 68025,28C20 ISBN 3-540-50368-4 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-50368-4 Springer-Verlag New York Berlin Heidelberg

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in other ways, and storage in data banks. Duplication of this publication or parts thereof is only permitted under the provisions of the German Copyright Law of September 9, 1965, in its version of June 24, 1985, and a copyright fee must always be paid. Violations fall under the prosecution act of the German Copyright Law.

© Springer-Verlag Berlin Heidelberg 1988 Printed in Germany Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr. 2146/3140-543210

Acknowledgments This is a revised version of my notes "Deterministic, stochastic, and average error bounds in optimal recovery", written in 1984-1986. The author is indebted to several people for generous advice and comments, in particular to Professor D. Kolzow who also initiated and supervised his doctoral thesis. Erlangen, June 1988

Erich Novak

Contents Introduction 1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9

Deterministic error bounds

9

1.1 Basic assumptions and definitions 1.2 Deterministic error bounds and n-widths

14

1.3 Results for special problems

22

2.

43

Error bounds for Monte Carlo methods

2.1 Basic properties of Monte Carlo methods

43

2.2 Results for special problems

53

3.

66

A verage error bounds

3.1 Averages over the class of problem elements

66

3.2 The average over the set of information

79

Appendix: Existence and uniqueness of optimal algorithms

...

90

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Notations Index

. . . . . . . . . . . . • . • . . . . . . . . . . . . 110 112

Introduction In these notes we want to investigate different deterministic and stochastic error bounds of numerical analysis. For many computational problems (such as approximation, optimization, and quadrature) we have only partial information and consequently such problems can only be solved with uncertainty in the answer. The information-centered approach asks for optimal methods and optimal error bounds if only the type of information available is indicated. We begin with worst case error bounds for deterministic methods and consider relations between these error bounds and the n-widths of the class of problem elements (1.2). In 1.3 we give worst case error bounds for some special problems. We are mainly interested in the problems of approximation (App), optimization (Opt