Average-Case Analysis of Numerical Problems

TABLE OF CONTENTS

I Introduction Overview Historical and Bibliographical Remarks

II Linear Problems: Definitions and a Classical Example Measures on Function Spaces Linear Problems Integration and L2-Approximation on the Wiener Space

III Second-Order Results for Linear Problems Reproducing Kernel Hilbert Spaces Linear Problems with Values in a Hilbert Space Splines and Their Optimality Properties Kriging

IV Integration and Approximation of Univariate Functions Sacks-Ylvisaker Regularity Conditions Integration under Sacks-Ylvisaker Conditions Approximation under Sacks-Ylvisaker Conditions Unknown Mean and Covariance Kernel Further Smoothness Conditions and Results Local Smoothness and Best Regular Sequences

V Linear Problems for Univariate Functions with Noisy Data Optimality of Smoothing Spline Algorithms Integration and Approximation of Univariate Functions Differentiation of Univariate Functions

VI Integration and Approximation of Multivariate Functions Isotropic Smoothness Tensor Product Problems Tractability or Curse of Dimensionality?

VII Nonlinear Methods for Linear Problems Nonlinear Algorithms, Adaptive Information, and Varying Cardinality Linear Problems with Gaussian Measures Unknown Local Smoothness Integration of Monotone Functions Computational Complexity of Continuous Problems

VIII Nonlinear Problems Zero Finding Global Optimization Bibliography Author Index Subject Index Index of Notation.