Estimation of interpolation projectors using Legendre polynomials

M. V. Nevskii

Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 3, pp. 316-337.

Résumé

We give some estimates for the minimum projector norm under linear interpolation on a compact set in ${\mathbb R}^n$. Let $\Pi_1({\mathbb R}^n)$ be the space of polynomials in $n$ variables of degree at most $1$, $\Omega$ is a compactum in ${\mathbb R}^n$, $K={\mathrm conv}(\Omega)$. We will assume that ${\mathrm vol}(K)\geq 0$. Let the points $x^{(j)}\in \Omega$, $1\leq j\leq n+1,$ be the vertices of an $n$-dimensional nondegenerate simplex. The interpolation projector $P:C(\Omega)\to \Pi_1({\mathbb R}^n)$ with the nodes $x^{(j)}$ is defined by the equations $Pf\left(x^{(j)}\right)=f\left(x^{(j)}\right)$. By $\|P\|_\Omega$ we mean the norm of $P$ as an operator from $C(\Omega)$ to $C(\Omega)$. By $\theta_n(\Omega)$ we denote the minimal norm $\|P\|_\Omega$ of all operators $P$ with nodes belonging to $\Omega$. By ${\mathrm simp}(E)$ we denote the maximal volume of the simplex with vertices in $E$. We establish the inequalities $\chi_n^{-1}\left(\frac{{\mathrm vol}(K)}{{\mathrm simp}(\Omega)}\right)\leq \theta_n(\Omega)\leq n+1.$ Here $\chi_n$ is the standardized Legendre polynomial of degree $n$. The lower estimate is proved using the obtained characterization of Legendre polynomials through the volumes of convex polyhedra. More specifically, we show that for every $\gamma\ge 1$ the volume of the set $\left\{x=(x_1,\dots ,x_n)\in{\mathbb R}^n : \sum |x_j| +\left|1- \sum x_j\right|\le\gamma\right\}$ is equal to ${\chi_n(\gamma)}/{n!}$. In the case when $\Omega$ is an $n$-dimensional cube or an $n$-dimensional ball, the lower estimate gives the possibility to obtain the inequalities of the form $\theta_n(\Omega)\geqslant c\sqrt{n}$. Also we formulate some open questions.

Détail

Mots-clés : polynomial interpolation, norm, Legendre polynomials.
Keywords: projector, esimate

Bibliographie

[1] R. A. DeVore, G. G. Lorentz, Constructive Approximation, Springer-Verlag, Berlin–Heidelberg, 1993 | MR | Zbl

[2] V. Barthelmann, E. Novak, K. Ritter, “High dimensional polynomial interpolation on sparse grids”, Advances in Computational Mathematics, 12:4 (2000), 273–288 | DOI | MR | Zbl

[3] C. De Boor, “Polynomial interpolation in several variables”, Studies in Computer Science, Plenum Press, 1994, 87–119 | DOI

[4] S. De Marchi, Lectures on Multivariate Polynomial Interpolation, Gottingen–Padova, 2015

[5] M. Gasca, R. Sauer, “Polynomial interpolation in several variables”, Advances in Computational Mathematics, 12:4 (2000), 377–410 | DOI | MR | Zbl

[6] M. Gunzburger, A. Teckentrup, Optimal point sets for total degree polynomial interpolation in moderate dimensions, 2014, arXiv: 1407.3291 [math.NA]

[7] V. Kaarnioja, On applying the maximum volume principle to a basis selection problem in multivariate polynomial interpolation, 2017, arXiv: 1512.07424 [math.NA] | Zbl

[8] S. Pashkovskij, Vychislitel'nye Primeneniya Mnogochlenov i Ryadov Chebysheva, Nauka, 1983 (in Russian)

[9] T. J. Rivlin, The Chebyshev Polynomials, John Wiley Sons, 1974 | MR | Zbl

[10] M. Nevskii, Optimal lagrange interpolation projectors and legendre polynomials, 2024, arXiv: 2405.01254 [math.MG]

[11] M. Nevskii, Geometric estimates in linear interpolation on a cube and a ball, 2024, arXiv: 2402.11611 [math.CA]

[12] M. V. Nevskii, Geometricheskie Ocenki v Polinomial'noj Interpolyacii, P. G. Demidov Yaroslavl State University, 2012, 218 pp. (in Russian)

[13] M. V. Nevskii, “Inequalities for the norms of interpolation projectors”, Modeling and Analysis of Information Systems, 15:3 (2008), 28–37 (in Russian)

[14] M. Hall Jr., Combinatorial Theory, Blaisdall Publishing Company, 1967 | MR | Zbl

[15] K. J. Horadam, Hadamard Matrices and Their Applications, Princeton University Press, 2007 | MR | Zbl

[16] P. K. Manjhi, M. K. Rama, “Some new examples of circulant partial Hadamard matrices of type $4-H(k\times n)$”, Advances and Applications in Mathematical Sciences, 21:5 (2022), 2559–2564 | MR

[17] M. Hudelson, V. Klee, D. Larman, “Largest $j$-simplices in $d$-cubes: some relatives of the Hadamard maximum determinant problem”, Linear Algebra and its Applications, 241–243 (1996), 519–598 | DOI | MR | Zbl

[18] J. Hadamard, “Resolution d"une question relative aux determinants”, Bulletin des Sciences Mathematiques, 2 (1893), 240–246

[19] G. F. Clements, B. Lindstrom, “A sequence of $(\pm1)$ determinants with large values”, Proceedings of the American Mathematical Society, 16:3 (1965), 548–550 | MR | Zbl

[20] G. M. Fikhtengol'ts, Kurs Differencial'nogo i Integral'nogo Ischisleniya, v. 3, Fizmatlit, M., 2001 (in Russian)

[21] L. Fejes Tot, Regular Figures, Macmillan/Pergamon, New York, 1964 | MR

[22] D. Slepian, “The content of some extreme simplices”, Pacific Journal of Mathematics, 31 (1969), 795–808 | DOI | MR | Zbl

[23] D. Vandev, “A minimal volume ellipsoid around a simplex”, Proceedings of the Bulgarian Academy of Sciences, 45:6 (1992), 37–40 | MR | Zbl

[24] M. Lassak, “Approximation of convex bodies by inscribed simplices of maximum volume”, Beitrage zur Algebra und Geometrie/Contributions to Algebra and Geometry, 52 (2011), 389–394 | DOI | MR | Zbl

[25] P. K. Suetin, Klassicheskie ortogonal'nye mnogochleny, Nauka, 1979 (in Russian) | MR

[26] G. Szego, Orthogonal Polynomials, American Mathematical Society, Providence, 1975 | MR | Zbl

[27] A. P. Prudnikov, Y. A. Brychkov, O. I. Marichev, Integraly i Ryady, Nauka, 2002 (in Russian) | MR

[28] M. V. Nevskii, “Geometric estimates in interpolation on an $n$-dimensional ball”, Modeling and Analysis of Information Systems, 26:3 (2019), 441–449 (in Russian) | DOI | MR | Zbl

[29] M. V. Nevskii, “On the minimal norm of the projection operator for linear interpolation on an $n$-dimensional ball”, Matematicheskie Zametki, 114:3 (2023), 477–480 (in Russian) | DOI | MR

[30] H. Bauer, “Minimalstellen von funktionen und extremal punkte”, Archiv der Mathematik, 9:4 (1958), 389–393 (in German) | DOI | MR | Zbl

[31] M. Nevskii, “Properties of axial diameters of a simplex”, Discrete Computational Geometry, 46:2 (2011), 301–312 | DOI | MR | Zbl

[32] M. Nevskii, A. Ukhalov, “Perfect simplices in $\mathbb{R}^5$”, Beitrage zur Algebra und Geometrie/Contributions to Algebra and Geometry, 59:3 (2018), 501–521 | DOI | MR | Zbl

[33] M. V. Nevskii, “On a certain relation for the minimal norm of an interpolation projector”, Modeling and Analysis of Information Systems, 16:1 (2009), 24–43 (in Russian)

[34] M. V. Nevskii, “On some estimate for the norm of an interpolation projector”, Modeling and Analysis of Information Systems, 29:2 (2022), 92–103 (in Russian) | DOI | MR

[35] M. V. Nevskii, A. Y. Ukhalov, Izbrannye Zadachi Analiza i Vychislitel'noj Geometrii, v. 2, P. G. Demidov Yaroslavl State University, 2022 (in Russian)

[36] M. V. Nevskii, A. Y. Ukhalov, “On optimal interpolation by linear functions on an $n$-dimensional cube”, Modeling and Analysis of Information Systems, 25:3 (2018), 291–311 (in Russian) | DOI | MR

[37] M. V. Nevskii, “On some problems for a simplex and a ball in $\mathbb{R}^n$”, Modeling and Analysis of Information Systems, 25:6 (2018), 680–691 (in Russian) | DOI | MR

[38] M. V. Nevskii, A. Y. Ukhalov, “Linear interpolation on a Euclidean ball in $\mathbb{R}^n$”, Modeling and Analysis of Information Systems, 26:2 (2019), 279–296 (in Russian) | DOI | MR | Zbl

[39] M. V. Nevskii, “On properties of a regular simplex inscribed into a ball”, Modeling and Analysis of Information Systems, 28:2 (2021), 186–197 (in Russian) | DOI | MR | Zbl