Tractability Of Integration And Approximation Of Some Multivariate Function Spaces

The study of tractability of multivariate problems, introduced by professor Wo(?)nia-kowski in 1994, is a new method to analysis multivariate information-based complexity.Especially in the study of tractability of multivariate integration and approximation, therehas recently been studied in numerous papers.There is a host of practical problems that deal with functions of very many variables.The classical estimates on approximation errors are asymptotic in the number, n, of eval-uations and for the number, d, of variables fixed. They are usually of no practical value ifn is fixed and if d is very large. This is why, in the field of information-based complexity,there has recently been an increasing interest in the study of tractability of multivariateproblems. Tractability is studied for various function spaces F_d of d variables. In short,the study of tractability is to help us confirm whether and even how the complexity ofproblems, we considered, is dependant on d. For some applications the dimension d isvery large, even in hundreds or thousands. Examples include applications in financialmathematics, statistics, and computational physics and chemistry.As for the progresses and follow-up problems of the study of tractability, professorWo(?)niakowski proposed several open problems about the tractability of multivariate in-tegration in 2003. Meanwhile, he conjectured that multivariate integration in C~∞([0, 1]~d)is intractable. Later Wojtaszczyk partially answered this problem and proved that multi-variate integration in C~∞([0, 1]~d) is not strongly tractable in the worst case setting.This article is based on the work of professor Wo(?)niakowski and Wojtaszczyk, studiestractability and strong tractability for multivariate approximation of infinitely differen-tiable functions, using either standard information or continuous linear information. Weprove that this approximation problem is not strongly tractable. And we conjecture thatthis approximation problem is intractable. Moreover, we get that L_p-approximation forinfinitely differentiable multivariate functions in the worst case setting by standard infor-mation is still not strongly tractable. As a development, we give a series of analyses and conjectures about integration and approximation problems in the randomized setting.Beginning with Korobov space and Sobolev space, it introduces some conditions for(strong) tractability of integration and approximation of some weighted spaces, and sum-marizes some newly international progesses, including intractability, quasi-Monte Carlomethod, QMC (strong) tractability and path integration. Besides, it gives some analyseson the equivalence of tractability between standard information class and linear informa-tion class, respectively in the worst case setting, average setting and randomized setting.And some personal superficial thoughts are included.There are four parts in this paper.In the first chapter, the preliminary knowledge, it mainly introduces some basicdefinitions about the nth minimal error respectively in the worst case setting, averagesetting and randomized setting, and (strong) tractability correspondingly. Some otherbasic concepts are also included, such as Gelfand number.In chapter 2, it is established in detail that multivariate approximation of infinitelydifferentiable functions is not strongly tractable in the worst case setting. Besides, a seriesof analyses and conjectures about some related problems is given.Chapter 3 summarizes an intractability result for multiple initegration in Korobovclass, some conditions for (strong) tractability of integration and approximation in someweighted spaces, and quasi-Monte Carlo method. In the meantime, it gives some analyseson the equivalence of tractability between standard information class and linear informa-tion class, respectively in the worst case setting, average setting and randomized setting.Chapter 4 recalls tractability of path integration, and gives a bit of personal ideasabout analysis in finite dimensional case for tractability of path integration.