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
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
Data Loading...