This article is cited in
11 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\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$.
Keywords:
$n$-dimensional simplex, $n$-dimensional cube, interpolation, projector, norm, numerical methods.
UDC:
514.17+
517.51+
519.6 Received: 11.12.2017
DOI:
10.18255/1818-1015-2018-3-291-311