A.A. Vasil’eva. Kolmogorov widths of Sobolev classes on a closed interval with constraints on the variation ... P. 48-66

We study the problem of estimating Kolmogorov widths in $L_q[0,\,1]$ for the Lipschitz classes of functions with fixed values at several points: $\tilde M=\{f\in AC[0,\,1],\; \|\dot{f}\|_\infty \le 1, \; f(j/s)=y_j, \; 0\le j\le s\}$. Applying well-known results about the widths of Sobolev classes, it is easy to obtain order estimates up to constants depending on $q$ and $y_1, \, \dots, \, y_n$.  Here we obtain order estimates up to constants depending only on $q$. To this end, we estimate the widths of the intersection of two finite-dimensional sets: a cube and a weighted Cartesian product of octahedra. If we take the unit ball of $l_p^n$ instead of the cube, we get a discretization of the problem on estimating the widths of the intersection of the Sobolev class and the class of functions with constraints on their variation: $M=\{ f\in AC[0,\,1]:\;\|\dot{f}\|_{L_p[0, \, 1]}\le 1,\; \|\dot{f}\|_{L_1\left[ (j-1)/s, \, j/s\right]} \le \varepsilon_j/s, \; 1\le j \le s\}$. For sufficiently large $n$, order estimates are obtained for the widths of these classes up to constants depending only on $p$ and $q$. If $p>q$ or $p>2$, then these estimates have the form $\varphi(\varepsilon_1, \, \dots, \, \varepsilon_s)n^{-1}$, where $\varphi(\varepsilon_1, \, \dots, \, \varepsilon_s) \to 0$ as $(\varepsilon_1, \, \dots, \, \varepsilon_s) \to 0$ (explicit formulas for $\varphi$ are given in the paper). If $p\le q$ and $p\le 2$, then the estimates have the form $n^{-1}$ (hence, the constraints on the variation do not improve the estimate for the widths). The upper estimates are proved with the use of Galeev's result on the intersection of finite-dimensional balls, whereas the proof of the lower estimates is based on a generalization of Gluskin's result on the width of the intersection of a cube and an octahedron.

Keywords: Kolmogorov widths, Sobolev classes, interpolation classes

Received March 15, 2019

Revised May 17, 2019

Accepted May 20, 2019

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 19-01-00332).

Anastasia Andreevna Vasil’eva, Dr. Phys.-Math. Sci., Assoc. Prof., Lomonosov Moscow State University, faculty on mechanics and mathematics, Moscow, Vorobyovy gory, 1, Main Building of MSU, 119991 Russia, e-mail: vasilyeva_nastya@inbox.ru

REFERENCES

1.   Vasil’eva A.A. An existence criterion for a smooth function under constraints. Math Notes, 2007, vol. 82, no. 3-4, pp. 295-308. doi: 10.1134/S0001434607090027 

2.   Tikhomirov V.M. Nekotorye voprosy teorii priblizhenii [Some questions in approximation theory . Moscow: Izdat. Moskov. Gos. Univ., 1976, 304 p.

3.   Tikhomirov V.M. Theory of approximations. Itogi Nauki Tekh., Ser. Sovrem. Probl. Mat., Fundam. Napravleniya, 1987, vol. 14, pp. 103–260.

4.   Pinkus A. n-widths in approximation theory. Berlin: Springer, 1985, 294 p. doi: 10.1007/978-3-642-69894-1 

5.   Galeev E.M. The Kolmogorov diameter of the intersection of classes of periodic functions and of finite-dimensional sets. Math. Notes, 1981, vol. 29, no. 5, pp. 382–388. doi: 10.1007/BF01158363 

6.   Galeev E.M. Kolmogorov n-width of some finite-dimensional sets in a mixed measure. Math. Notes, 1995, vol. 58, no. 1, pp. 774–778. doi: 10.1007/BF02306188 

7.   Galeev E.M. Kolmogorov widths of classes of periodic functions of one and several variables. Math. USSR-Izv., 1991, vol. 36, no. 2, pp. 435–448. doi: 10.1070/IM1991v036n02ABEH002029 

8.   Galeev E.M. Kolmogorov and linear diameters of functional classes and finite dimensional sets. Vladikavkaz. Mat. Zh., 2011, vol. 13, no. 2, pp. 3–14 (in Russian).

9.   Gluskin E.D. Intersections of a cube with an octahedron are poorly approximated by subspaces of small dimension. Approximation of functions by special classes of operators, Interuniv. Collect. Sci. Works, Vologda, 1987, pp. 35–41 (in Russian).

10.   Izaak A.D. Kolmogorov widths in finite-dimensional spaces with mixed norms. Math. Notes, 1994, vol. 55, no. 1, pp. 30–36. doi: 10.1007/BF02110761 

11.   Izaak A.D. Widths of HЈolder–Nikol’skij classes and finite-dimensional subsets in spaces with mixed norm. Math. Notes, 1996, vol. 59, no. 3, pp. 328–330. doi: 10.1007/BF02308549 

12.   Malykhin Yu.V., Ryutin K.S. The product of octahedra is badly approximated in the $\ell_{2,1}$-metric. Math. Notes, 2017, vol. 101, no. 1, pp. 94–99. doi: 10.1134/S0001434617010096 

13.   Ismagilov R.S. Diameters of sets in normed linear spaces and the approximation of functions by trigonometric polynomials. Russian Math. Surveys, 1974, vol. 29, no. 3, pp. 169–186. doi: 10.1070/RM1974v029n03ABEH001287 

14.   Kashin B.S. Diameters of some finite-dimensional sets and classes of smooth functions. Math. USSR-Izv., 1977, vol. 11, no. 2, pp. 317–333. doi: 10.1070/IM1977v011n02ABEH001719 

15.   Gluskin E.D. Norms of random matrices and widths of finite-dimensional sets. Math. USSR-Sb., 1984, vol. 48, no. 1, pp. 173–182. doi: 10.1070/SM1984v048n01ABEH002667 

16.   Maiorov V.E. Discretization of the problem of diameters. Uspekhi Mat. Nauk, 1975, vol. 30, no. 6 (186), pp. 179–180 (in Russian).

17.   Gluskin E.D. On some finite-dimensional problems of the theory of diameters. Vestn. Leningr. Univ., 1981, vol. 13, no. 3, pp. 5–10 (in Russian).

18.   Ioffe A.D., Tikhomirov V.M. Duality of convex functions and extremum problems. Russian Math. Surveys, 1968, vol. 23, no. 6, pp. 53–124. doi: 10.1070/RM1968v023n06ABEH001251 

19.   Fabian M., Habala P., Hajek P., Montesinos Santalucia V., Pelant J., Zizler V. Functional analysis and infinite-dimensional geometry. Ser. CMS Books in Math. N Y: Springer, 2001, 451 p. doi: 10.1007/978-1-4757-3480-5 

Cite this article as: A.A.Vasil’eva. Kolmogorov widths of Sobolev classes on a closed interval with constraints on the variation, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 2, pp. 48–66.