Average-case analysis of numerical problems / Klaus Ritter

This research monograph is devoted to the analysis of numerical problems in an average case setting. The author studies the average error and cost and is looking for optimal methods with respect to these two quantities. A probability measure is used to specify the smothness and geometrical properties of the underlying functions. Equivalently, a random function or stochastic process is considered. The choice of the measure in the average case setting corresponds to the choice of the function class in the worst case setting.

The authors studies continuous problems on infinite-dimensional function spaces, where only partial information such as a finite number of function values is available. The average case and worst case setting are among the several settings that are used in information-based complexity to analyze such problems. The first three chapters contain some background material concerning the average case setting for linear problems. Furthermore, they contain some definitions and facts about measures on function spaces and basic properties of reproducing kernel Hilbert spaces.

Chapters IV–VI are concerned with minimal average errors for integration, approximation, and differentiation in the linear case. Chapter VII deals with nonlinear methods for linear problems. The author discusses integration and approximation of univariate functions with unknown local smothness. Integration of monotone functions are also discussed. The final chapter presents average case results for nonlinear problems of zero finding and global optimization.

The monograph is carefully written and gives a systematic up-to-date treatment of theoretical questions concerning the average-case analysis of numerical problems. It is helpful for both theoretical research and practical applications. (Zentralblatt)