On optimal interpolation by linear functions on an $n$-dimensional cube

M. V. Nevskii ; A. Yu. Ukhalov

Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 3, pp. 291-311.

Résumé

Let $n\in{\mathbb N}$, and let $Q_n$ be the unit cube $[0,1]^n$. By $C(Q_n)$ we denote the space of continuous functions $f:Q_n\to{\mathbb R}$ with the norm $\|f\|_{C(Q_n)}:=\max\limits_{x\in Q_n}|f(x)|,$ by $\Pi_1\left({\mathbb R}^n\right)$ — the set of polynomials of $n$ variables of degree $\leq 1$ (or linear functions). Let $x^{(j)},$ $1\leq j\leq n+1,$ be the vertices of $n$-dimnsional nondegenerate simplex $S\subset Q_n$. An interpolation projector $P:C(Q_n)\to \Pi_1({\mathbb R}^n)$ corresponding to the simplex $S$ is defined by equalities $Pf\left(x^{(j)}\right)= f\left(x^{(j)}\right)$. The norm of $P$ as an operator from $C(Q_n)$ to $C(Q_n)$ may be calculated by the formula $\|P\|=\max\limits_{x\in\mathrm{ver}(Q_n)} \sum\limits_{j=1}^{n+1} |\lambda_j(x)|$. Here $\lambda_j$ are the basic Lagrange polynomials with respect to $S,$ $\mathrm{ver}(Q_n)$ is the set of vertices of $Q_n$. Let us denote by $\theta_n$ the minimal possible value of $\|P\|$. Earlier, the first author proved various relations and estimates for values $\|P\|$ and $\theta_n$, in particular, having geometric character. The equivalence $\theta_n\asymp \sqrt{n}$ takes place. For example, the appropriate, according to dimension $n$, inequalities may be written in the form $\frac{1}{4}\sqrt{n}$ $\theta_n$ $3\sqrt{n}$. If the nodes of the projector $P^*$ coincide with vertices of an arbitrary simplex with maximum possible volume, we have $\|P^*\|\asymp\theta_n$. When an Hadamard matrix of order $n+1$ exists, holds $\theta_n\leq\sqrt{n+1}$. In the paper, we give more precise upper bounds of numbers $\theta_n$ for $21\leq n \leq 26$. These estimates were obtained with the application of maximum volume simplices in the cube. For constructing such simplices, we utilize maximum determinants containing the elements $\pm 1$. Also, we systematize and comment the best nowaday upper and low estimates of numbers $\theta_n$ for a concrete $n$.

Détail

Keywords: $n$-dimensional simplex, $n$-dimensional cube, projector, numerical methods.
Mots-clés : interpolation, norm

Bibliographie

[1] Esipova E. M., “Geometricheskie haracteristiki simpleksov, obladayuschih svoistvom ravnootsecheniya”, Sovremennye problemy matematiki i informatiki, 17, P. G. Demidov Yaroslavl State University, Yaroslavl, 2017, 49–61 (in Russian)

[2] Kudryavtsev I. S., Ozerova E. A., Ukhalov A. Yu., “Novye ocenki dlya norm minimalnyh proektorov”, Sovremennye problemy matematiki i informatiki, 17, P. G. Demidov Yaroslavl State University, Yaroslavl, 2017, 74–81 (in Russian)

[3] Nevskij M. V., “Orthogonal projection and minimal linear interpolation on an n-dimensional cube”, Modeling and Analysis of Information Systems, 14:3 (2007), 8–28 (in Russian)

[4] Nevskij M. V., Hlestkova I. V., “On minimal linear interpolation”, Sovremennye problemy matematiki i informatiki, 9, P. G. Demidov Yaroslavl State University, Yaroslavl, 2008, 31–37 (in Russian)

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

[6] Nevskii M. V., “On a property of $n$-dimensional simplices”, Math. Notes, 87:4 (2010), 543–555 | DOI | DOI | MR | Zbl

[7] Nevskii M. V., Geometricheskie ocenki v polinomialnoy interpolyacii, P. G. Demidov Yaroslavl State University, Yaroslavl, 2012 (in Russian)

[8] Nevskii M. V., Ukhalov A. Yu., “On numerical charasteristics of a simplex and their estimates”, Modeling and Analysis of Information Systems, 23:5 (2016), 602–618 (in Russian) | MR

[9] Nevskii M. V., Ukhalov A. Yu., “New estimates of numerical values related to a simplex”, Modeling and Analysis of Information Systems, 24:1 (2017), 34–50 (in Russian) | MR

[10] Nevskii M. V., Ukhalov A. Yu., “On $n$-Dimensional Simplices Satisfying Inclusions $S\subset [0,1]^n\subset nS$”, Modeling and Analysis of Information Systems, 24:5 (2017), 578–595 (in Russian) | MR

[11] Nevskii M. V., Ukhalov A. Yu., “On Minimal Absorption Index for an $n$-Dimensional Simplex”, Modeling and Analysis of Information Systems, 25:1 (2018), 140–150 (in Russian)

[12] Szego G., Orthogonal Polynomials, American Mathematical Society, New York, 1959 (in English) | MR | Zbl

[13] Suetin P. K., Klassicheskie ortogonalnye mnogochleny, Nauka, M., 1979 (in Russian) | MR

[14] Hall M., Jr, Combinatorial theory, Blaisdall publishing company, Waltham (Massachusets)–Toronto–London, 1967 (in English) | MR | Zbl

[15] Butzer P. L., Schmidt M., Stark E. L., “Observations on the history of central $B$-splines”, Archive for History of Exact Sciences, 1988, no. 2, 137–156 | MR | Zbl

[16] Comtet L., “Permutations by number of rises; Eulerian numbers”, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel, Dordrecht, Netherlands, 1974 | MR | Zbl

[17] Ehrenborg R., Readdy M., Steingrimsson E., “Mixed volumes and slices of the cube”, Journal of Combinatorial Theory. Series A, 81 (1998), 121–126 | DOI | MR | Zbl

[18] Graham R. L., Knuth D. E., Patashnik O., Concrete mathematics: A foundation for computer science, Addison–Wesley, Reading, MA, 1994 | MR | Zbl

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

[20] de Laplace M., Oeuvres complétes, v. 7, Réédite par Gauthier–Villars, Paris, 1886

[21] Mangano S., Mathematica cookbook, O'Reilly Media Inc., Cambridge, 2010

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

[23] Scott P. R., “Lattices and convex sets in space”, Quart. J. Math. Oxford (2), 36 (1985), 359–362 | DOI | MR | Zbl

[24] Scott P. R., “Properties of axial diameters”, Bull. Austral. Math. Soc., 39 (1989), 329–333 | DOI | MR | Zbl

[25] Sommerfeld A., “Eine besonders anschauliche Ableitung des Gaussischen Fehlergesetzes”, Festschrift Ludwig Boltzmann gewidmet zum 60 Geburstage (20 Februar, 1904), Barth, Leipzig, 1904

[26] Stanley R. P., “Eulerian partitions of a unit hypercube”, Higher Combinatorics, Proceedings of the NATO Advanced Study Institute (Berlin, West Germany, September 1–10, 1976), Reidel, Dordrecht/Boston, 1977 | MR