|
This article is cited in 12 scientific papers (total in 12 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.
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
Linking options:
https://www.mathnet.ru/eng/mais629 https://www.mathnet.ru/eng/mais/v25/i3/p291
|
|