Approximation Of Infinitely Differentiable Multivariate Functions Is Not Strongly Tractable With L_p Norm

Information Based Complexity (IBC) is one of the most important research di-rections in computational mathematics. When studying numerical problems of multi-variate functions, if the number of variables is very large, such problems almost never be solved analytically. So they can only be solved approximately to within a threshold ε. So the complexity of algorithms is the study of the minimal computational costs of the algorithm needed to solve a problem. It is defined as the minimal computational costs of information operations and combinatory operations used in the algorithm in order to obtain the approximate solution to withinε. The information complexity is defined as the minimal number n(ε, d) of information operations needed to solve the d-variable problem to withinε. For all problems, the information complexity is a lower bound of the computational complexity. Generally speaking, for many linear multivariate problems, the information complexity is proportional to the computation-al complexity. For this reason, we focus on the information complexity.The tractability of multivariate problems is one of the most active research topics about IBC in recent years. It studies that how the information complexity n(ε,d) de-pends on ε-1and d. Huang Fanglun and Zhang Shun proved that the approximation of infinitely differentiable multivariate functions with L∞norm is not strongly tracta-ble. Later Novak and Wozniakowski proved that the approximation of infinitely diffe-rentiable multivariate functions with L∞norm is intractable. In addition, Wojtaszczyk proved that the integration of infinitely differentiable multivariate functions with L∞norm is not strongly tractable. In this thesis we consider this problem in the worst case setting (deterministic setting) with Lp(p≥1) norm. We proved that the approx-imation of infinitely differentiable multivariate functions is not strongly tractable. Moreover, we proved that the approximation problem is intractable with L∞norm by constructing the specific functions for the specific dimension. Furthermore, we proved that the multivariate integration problem is not strongly tractable. Thus we expand the class of L∞function to larger class of Lp function for the research of tractability of multivariate problems.This thesis consists of four chapters. The first chapter is about the preliminaries. We first introduced the history and the background of Information Based Complexity. Then we gave the concepts, notations and some related results of tractability in the worst case setting.The second chapter mainly proved both approximation problem and integration problem are not strongly tractable with Lp(p≥1) norm. In addition, we also gave a new proof by constructing the specific functions for the specific dimension of the approximation problem is intractable with L∞(p≥1) norm.The third chapter expanded the present situation of the research in the integration problem of infinitely differentiable multivariate functions to the other spaces such as Holder space and Korobov space.The last chapter mainly summarized the conclusions of the previous chapters. We will continue to study the tractability of integration and approximation of multiva-riate functions for variety of function spaces in the average case setting and rando-mized setting.