Kolmogorov widths of Sobolev classes on a closed interval with constraints on the variation

A. A. Vasil'eva

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 2, pp. 48-66

Résumé

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.

Détail

Keywords: Kolmogorov widths, Sobolev classes
Mots-clés : interpolation classes.

Bibliographie

[1] Vasileva A.A., “Kriterii suschestvovaniya gladkoi funktsii pri ogranicheniyakh”, Mat. zametki, 82:3 (2007), 335–346 | DOI | MR | Zbl

[2] Tikhomirov V.M., Nekotorye voprosy teorii priblizhenii, Izd-vo MGU, M., 1976, 304 pp.

[3] Tikhomirov V.M., “Teoriya priblizhenii”, Sovremennye problemy matematiki. Fundamentalnye napravleniya, Itogi nauki i tekhniki, 14, VINITI AN SSSR, Moskva, 1987, 103–260

[4] Pinkus A., n-widths in approximation theory, Springer, Berlin, 1985, 294 pp. | DOI | MR | Zbl

[5] Galeev E.M., “Poperechniki po Kolmogorovu peresecheniya klassov periodicheskikh funktsii i konechnomernykh mnozhestv”, Mat. zametki, 29:5 (1981), 749–760 | MR | Zbl

[6] Galeev E.M., “Poperechniki po Kolmogorovu nekotorykh konechnomernykh mnozhestv v smeshannoi norme”, Mat. zametki, 58:1 (1995), 144–148 | MR | Zbl

[7] Galeev E.M., “Poperechniki po Kolmogorovu klassov periodicheskikh funktsii odnoi i neskolkikh peremennykh”, Izv. AN SSSR. Ser. matematicheskaya, 54:2 (1990), 418–430

[8] Galeev E.M., “Poperechniki funktsionalnykh klassov i konechnomernykh mnozhestv”, Vladikavkazskii mat. zhurn., 13:2 (2011), 3–14 | MR | Zbl

[9] Gluskin E.D., “Peresecheniya kuba s oktaedrom plokho approksimiruyutsya podprostranstvami maloi razmernosti”, Priblizhenie funktsii spetsialnymi klassami operatorov, mezhvuz. sb. nauchn. tr., Min. pros. RSFSR; Vologodskii gos. ped. in-t, Vologda, 1987, 35–41 | MR

[10] Izaak A.D., “Poperechniki po Kolmogorovu v konechnomernykh prostranstvakh so smeshannoi normoi”, Mat. zametki, 55:1 (1994), 43–52 | MR | Zbl

[11] Izaak A.D., “Poperechniki klassov Geldera - Nikolskogo i konechnomernykh mnozhestv v prostranstvakh so smeshannoi normoi”, Mat. zametki, 59:3 (1996), 459–461 | DOI | MR | Zbl

[12] Malykhin Yu.V., Ryutin K.S., “Proizvedenie oktaedrov plokho priblizhaetsya v metrike $\ell_{2,1}$”, Mat. zametki, 101:1 (2017), 85–90 | DOI | MR | Zbl

[13] Ismagilov R.S., “Poperechniki mnozhestv v lineinykh normirovannykh prostranstvakh i priblizhenie trigonometricheskimi mnogochlenami”, Uspekhi mat. nauk, 29:3 (1974), 161–178 | MR | Zbl

[14] Kashin B.S., “Poperechniki nekotorykh konechnomernykh mnozhestv i klassov gladkikh funktsii”, Izv. AN SSSR. Cer. matematicheskaya, 41:2 (1977), 334–351 | MR | Zbl

[15] Gluskin E.D., “Normy sluchainykh matrits i poperechniki konechnomernykh mnozhestv”, Mat. sbornik, 120 (162):2 (1983), 180–189 | MR | Zbl

[16] Maiorov V.E., “Diskretizatsiya zadachi o poperechnikakh”, Uspekhi mat. nauk, 30:6 (1975), 179–180 | MR | Zbl

[17] Gluskin E.D., “O nekotorykh konechnomernykh zadachakh teorii poperechnikov”, Vestn. LGU, 13 (1981), 5–10 | Zbl

[18] Ioffe A.D., Tikhomirov V.M., “Dvoistvennost vypuklykh funktsii i ekstremalnye zadachi”, Uspekhi mat. nauk, 23:6 (1968), 51–116 | MR | Zbl

[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., Springer, N Y, 2001, 451 pp. | DOI | MR | Zbl