Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).  

Tractability of linear problems defined over Hilbert spaces

We study d$d$-variate approximation problems in the worst and average case settings. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. In the worst case setting, we obtain necessary and sufficient conditions for quasi-polynomial tractability and uniform weak tractability. Furthermore, we give an estimate of the exponent of quasi-polynomial tractability which cannot be improved in general. In the average case setting, we obtain necessary and sufficient conditions for uniform weak tractability. As applications we discuss some examples.  

The average errors for Hermite-Fejér interpolation on the Wiener space

For 1 ? p < ∞, firstly we prove that for an arbitrary set of distinct nodes in [?1, 1], it is impossible that the errors of the Hermite-Fejér interpolation approximation in L _p -norm are weakly equivalent to the corresponding errors of the best polynomial approximation for all continuous functions on [?1, 1]. Secondly, on the ground of probability theory, we discuss the p-average errors of Hermite-Fejér interpolation sequence based on the extended Chebyshev nodes of the second kind on the Wiener space. By our results we know that for 1 ? p < ∞ and 2 ? q < ∞, the p-average errors of Hermite-Fejér interpolation approximation sequence based on the extended Chebyshev nodes of the second kind are weakly equivalent to the p-average errors of the corresponding best polynomial approximation sequence for L _q -norm approximation. In comparison with these results, we discuss the p-average errors of Hermite-Fejér interpolation approximation sequence based on the Chebyshev nodes of the second kind and the p-average errors of the well-known Bernstein polynomial approximation sequence on the Wiener space.  

Exponential Convergence of an Approximation Problem for Infinitely Differentiable Multivariate Functions

We study approximation problems for infinitely differentiable multivariate functions in the worst-case setting. Using a series of information-based algorithms as approximation tools, in which each algorithm is constructed by performing finitely many standard information operations, we prove that the L_∞-approximation problem is exponentially convergent. As a corollary, we show that the corresponding integral problem is exponentially convergent as well.  

Sample Numbers and Optimal Lagrange Interpolation of Sobolev Spaces Wr1*

This paper investigates the optimal recovery of Sobolev spaces W^r₁[?1, 1], r ∈ N in the space L1[?1, 1]. They obtain the values of the sampling numbers of W^r₁[?1, 1] in L₁[?1, 1] and show that the Lagrange interpolation algorithms based on the extreme points of Chebyshev polynomials are optimal algorithms. Meanwhile, they prove that the extreme points of Chebyshev polynomials are optimal Lagrange interpolation nodes.  

一个无限可微函数类的最优Lagrange 插值

本文研究\,$[-1,1]$上的一个无限可微函数类$F_\infty$在空间$L_\infty[-1,1]$及加权空间$L_{p,\omega}[-1,1]$, $1\le p< \infty$ ($\omega$是$(-1,1)$上的非负连续可积函数)的最优Lagrange插值.我们证明了基于首项系数为1且于$L_{p,\omega}[-1,1]$上有最小范数的多项式零点的Lagrange插值对$1\le p< \infty$是最优的. 同时我们给出了当结点组包含端点时的最优结点组.  

The Average Errors for Hermite Interpolation on the 1-Fold Integrated Wiener Space

For the weighted approximation in Lp-norm,the authors determine the weakly asymptotic order for the p-average errors of the sequence of Hermite interpolation based on the Chebyshev nodes on the 1-fold integrated Wiener space.By this result,it is known that in the sense of information-based complexity,if permissible information functionals are Hermite data,then the p-average errors of this sequence are weakly equivalent to those of the corresponding sequence of the minimal p-average radius of nonadaptive information.  

The Gel'fand widths of anisotropic Sobolev classes of smooth functions

In this paper, we obtain some Gel'fand widths of anisotropic Sobolev periodic classes of smooth functions, and average Gel'fand widths of anisotropic Sobolev classes of smooth functions.  

Some extremal properties of multivariate polynomial splines in the metric Lp(ℝd)

We constructed a kind of continuous multivariate spline operators as the approximation tools of the multivariate functions on the (?^d instead of the usual multivariate cardinal interpolation operators of splines, and obtained the approximation error by this kind of spline operators. Meantime, by the results, we also obtained that the spaces of multivariate polynomial splines are weakly asyrnptotically optimal for the Kolrnogorov widths and the linear widths of some anisotropic Sobolev classes of smooth functions on (?^d in the metric L_p((?^d).