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