Approximate Nikolskii And Sobolev Functions Using Linear Information

From 1950's,some people,such as Traub and Wozniakowski,began to study computational complexity of numerical integration and approximation of multivariate functions,and they obtained some important results.Directed by their methods,I generalized and proved computational complexity about approximation problem in some classical multivariate functional spaces,in order to make the complexity research for approximation problem in these spaces more perfect. For example,HSlder space and Sobolev space.I also provided some suggestions for complexity of approximation problem in anisotropic Nikolskii space and Sobolev space, I obtained optimal algorithms and estimates for the approximation problem,and I explained the convergence speed.I proved the common research methods for approximation problem is feasible in anisotropic multivariate functional spaces,and I demonstrated the sameness and difference about the computation complexity of approximation problem in isotropic and anisotropic Nikolskii and Soboble spaces.Then,I revealed the deviation and influence of the approximation problem because of the anisotropic defferential coordinate.As far as the approximation problem in classical multivariate periodic functional spaces, there are many important results,including the accuracy and veracity about approximation problem, such as interpolation algorithm of trigonometric polynomiMs,imbedding theorems in functional spaces.We want to crystallize these results in the field of Information-based complexity in several settings.For example,we introduce the Dirichlet and Vallee-Poussin kernel function for.building liner algorithm in order to solve the upper estimate of approximation problem in anisotropic and periodic Sobolev space,and we try to choose trigonometric polynomial to build optimal algorithm for the approximation problem in anisotropic Besov space.I think the results might play a role in the developement of approximation problem in multivariate functional spaces. I mainly use functional analysis as tools,especially, embedding theorem,Gelfand number, and F function.ln the deterministic,stocastic,and average settings,I seek the optimal numerical algorithms for approximation problem in some funtional spaces and its subspaces,with the standard information and linear information as the information operator, and I prove the accuracy of the algorithms.On the other hand,I mainly want to obtain the error estimates of the algorithms,especially, the n-th minimal error.Then,we know the computational efficiency of the algorithm,that is computational complexity.Another problem is we need to choose different information classes in order to compare the convergence speed of the identical algorithm,to find the influence to the n-th minimal error,and to reveal the tractability and intractability for approximation problem. We will also compare the difference of convergence of the n-th minimal error in the deterministic and stocastic settings.So,we proved the convergence speed of the n-th minimal error is the crucial factor again.This paper have three chapters:Chapterl.Preliminary knowledge.I described the develop course and current research directions of Information-based complexity, and I instructed the general theory of the Information-based complexity. I explained in some funtional spaces and with special information classes,the n-th minimal error is a crucial method in order to study the complexity of approximation problem.Chapter2.I described mainly results of some people,such as Traub,Wozniakowski, Heinrich,Novak, and the computational complexity for approximation problem of several funtional spaces,and I want to make the approximation problem more perfect. For Holder space,we have For classical Sobolev space,we have That is, the complexity in this space for approximation is O(n^-((r+a)/d)).For the classical Sobolev space,the complexity for approximation problem is O(n^-(r/d)) In this chapter,I give the general research method for approximation problem in multivariate functional spaces.Chapter3.We mainly introduced the approximation problem in anisotropic and non-periodic functional spaces. I described what is anisotropy, and I build several polynomials algorithm Gelfand number method.I explained that we can use the same method,just like in classical spaces,to study the computational complexity in anisotropic Nikolskii and anisotropic Sobolev spaces.Then,in the deterministic setting, I give the error estimates of approximation problem with two kinds of information classes. Chapter4.We mainly research the approximation problem in anisotropic and periodic functional spaces,including Sobolev,Nikolskii,and Besov spaces.We build trigonometric polynomials algorithm to estimate the upper bound using a new method,and we use the general methods, which are bump function and Gelfand number in order to estimate the lower bound. Especially, in Besov space,I choose two different information classes,and give some results of approximation problem in stocastic setting for convenience.Then,I provide some open problems.