Complexity of integration and approximation in function spaces (Subprojekt des SFB F-55)
Sprache der Bezeichnung:
In this project part, which is a new addition to the SFB for the second period, we aim at studying the inherent complexity of multivariate integration and approximation problems. This includes both the study of efficient numerical algorithms, in particular quasi-Monte Carlo and more general integration rules, and the derivation of lower bounds for the integration and approximation errors of any conceivable algorithm. Ideally, the obtained lower and upper bounds have the same order and similar dependence on the number of variables, thus providing satisfactory conclusions about the complexity of the problem.
Proving upper bounds means the invention and study of concrete algorithms. Here we will focus on the main known deterministic constructions which are digital nets and their relatives, and on probabilistic constructions, which are efficient especially in high dimensions where no satisfactory deterministic construction is available. Via Koksma-Hlawka type inequalities, the worst case error of an integration rule for functions from the unit ball of a given (Sobolev type) function space can be usually split into a part involving the (Sobolev) norm of the function and a part involving a corresponding norm of the discrepancy function of the sample point set. Hence some of our problems are directly dealing with the discrepancy or the related dispersion of point sets and have a more geometric and number theoretic flavor.
The methods necessary to tackle the proposed problems are expected to come from diverse areas of mathematics: harmonic analysis, probability theory, function spaces and high dimensional geometry. On the other hand, we expect that new methods and insights developed during our project work will have applications in these areas