General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Model. Anal. Inform. Sist.:

Personal entry:
Save password
Forgotten password?

Model. Anal. Inform. Sist., 2018, Volume 25, Number 3, Pages 291–311 (Mi mais629)  

This article is cited in 2 scientific papers (total in 2 papers)

Computational Geometry

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

M. V. Nevskii, A. Yu. Ukhalov

Centre of Integrable Systems, P.G. Demidov Yaroslavl State University, 14 Sovetskaya str., Yaroslavl, 150003, Russian Federation

Abstract: 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({\mathbb R}^n)$ — 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(x^{(j)})= f(x^{(j)})$. 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$.

Keywords: $n$-dimensional simplex, $n$-dimensional cube, interpolation, projector, norm, numerical methods.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation 1.12873.2018/12.1
This work was carried out within the framework of the state programme of the Ministry of Education and Science of the Russian Federation, project № 1.12873.2018/12.1.


Full text: PDF file (767 kB)
References: PDF file   HTML file

English version:
Automatic Control and Computer Sciences, 2018, 52:7, 828–842

UDC: 514.17+517.51+519.6
Received: 11.12.2017

Citation: M. V. Nevskii, A. Yu. Ukhalov, “On optimal interpolation by linear functions on an $n$-dimensional cube”, Model. Anal. Inform. Sist., 25:3 (2018), 291–311; Automatic Control and Computer Sciences, 52:7 (2018), 828–842

Citation in format AMSBIB
\by M.~V.~Nevskii, A.~Yu.~Ukhalov
\paper On optimal interpolation by linear functions on an $n$-dimensional cube
\jour Model. Anal. Inform. Sist.
\yr 2018
\vol 25
\issue 3
\pages 291--311
\jour Automatic Control and Computer Sciences
\yr 2018
\vol 52
\issue 7
\pages 828--842

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. M. V. Nevskii, A. Yu. Ukhalov, “Lineinaya interpolyatsiya na evklidovom share v ${\mathbb R}^n$”, Model. i analiz inform. sistem, 26:2 (2019), 279–296  mathnet  crossref
    2. M. V. Nevskii, “Geometricheskie otsenki pri interpolyatsii na $n$-mernom share”, Model. i analiz inform. sistem, 26:3 (2019), 441–449  mathnet  crossref
  • Моделирование и анализ информационных систем
    Number of views:
    This page:77
    Full text:28

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020