On Optimal Interpolation by Linear Functions on an n-Dimensional Cube

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 ver(Q_n)} \sum\limits_{j=1}^{n+1} |\lambda_j(x)|.\) Here \(\lambda_j\) are the basic Lagrange polynomials with respect to \(S,\) \(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 \linebreak \(\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.\)

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 ndimensional 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

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).

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).

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

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).

13. Suetin P. K., Klassicheskie ortogonalnye mnogochleny, Nauka, Moscow, 1979, (in Russian).

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

15. Butzer P. L., Schmidt M., Stark E. L., “Observations on the history of central B-splines”, Archive for History of Exact Sciences, 1988, № 2, 137–156.

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

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

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

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.

20. de Laplace M., Oeuvres compl´etes. V. 7, R´e´edite 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.

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

24. Scott P. R., “Properties of axial diameters”, Bull. Austral. Math. Soc., 39 (1989), 329–333.

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.