# Comptes Rendus
## Mathématique

François Bertrand

Sur la géométrie des ensembles de nœuds pour l'interpolation de
Lagrange en plusieurs variables

Volume 361 (2023), p. 673-678

Published online: 2 March 2023

https://doi.org/10.5802/crmath.436

<figure><img src="image_1.png" /></figure>
Analyse numérique / Numerical analysis

# Sur la géométrie des ensembles de nœuds pour l'interpolation de Lagrange en plusieurs variables

*On the geometry of unisolvent set for multivariate Lagrange interpolation*

François Bertrand<sup>a</sup>

<sup>a</sup> Institut de Mathématiques de Toulouse, Université de Toulouse III et CNRS (UMR 5219),
31062 Toulouse Cedex 9, France

Courriel: francois.bertrand@dbmail.com

**Résumé.** Étant donné un ensemble de nœuds d'interpolation valide pour l'interpolation de Lagrange de degré *d* à *n* variables, on étudie le nombre de sous-ensembles qui forment un ensemble d'interpolation valide de degré *d* − 1. Cela conduit à une estimation du nombre de structures de Newton, nombre qui fournit à son tour le nombre de tableaux unisolvants distincts que l'on peut obtenir par le procédé d'enlacement qui est rappelé dans le texte.

**Abstract.** Given a valid set $X$ of interpolation points for Lagrange interpolation of degree $d$ in $n$ variables we study how many subsets of $X$ can be chosen in order to obtain a valid set of interpolation points of degree $d-1$. This leads to an estimate of the number of Newton structures for $X$ which, in turn, gives the number of different unisolvent sets that can be obtainend by the process of interwinning which is recalled in the text.

**Classification Mathématique (2020).** 41A05, 41A63, 46A32.

Manuscrit reçu le 3 juin 2021, révisé le 4 juillet 2022, accepté le 11 octobre 2022.

## 1. Introduction

On sait bien que la donnée de $d+1$ complexes, deux à deux distincts, permet de définir un projecteur de Lagrange unidimensionnel de degré $d$ et n'importe quel arrangement de ces $d+1$ points conduira par exemple à une forme de Newton particulière comme aussi à un algorithme de Neville–Aitken particulier. Il en est tout autrement dans l'interpolation de Lagrange multidimensionnelle en effet, si $X$ est un ensemble de cardinal $N_d(n) = \dim P_d(\mathbb{K}^n)$, $n > 1$, unisolvant (de degré $d$), voir ci-dessous, un sous-ensemble de $X$ de cardinal $N_{d-1}(n)$ ne sera pas nécessairement unisolvant de degré $d-1$. Le problème de combinatoire géométrique étudié dans cette note consiste essentiellement à estimer le nombre de sous-ensembles d'un tel $X$ qui soient unisolvants de degré $d-1$. Le problème et sa motivation sont explicités ci-après.
## 2. Notations et problématique

La dimension $N_d = N_d(n)$ de l'espace $P_d(\mathbb{K}^n)$ des polynômes à $n$ variables de degré (total) inférieur ou égal à $d$, et à coefficients dans $\mathbb{K} = \mathbb{R}$ ou $\mathbb{C}$ vaut $\binom{d+n}{n} = \binom{d+n}{d}$. C'est aussi le nombre de multi-indices $\alpha \in \mathbb{N}^n$ de longueur $|\alpha| \le d$ dont l'ensemble sera noté $\mathbb{N}_d^n$. La notation $X_d = \{A_1, \dots, A_{N_d(n)}\}$ représentera une partie unisolvante de $\mathbb{K}^n$ pour $P_d(\mathbb{K}^n)$. Cela signifie que $X_d$ est un ensemble de nœuds valide pour l'interpolation par des polynômes de degré au plus $d$. Si $(e_\alpha: x \to x^\alpha)_{\alpha \in \mathbb{N}_d^n}$ est la base canonique de $P_d(\mathbb{K}^n)$, l'unisolvance de $X_d$ signifie (où $[1, N_d]$ désigne classiquement l'ensemble des entiers de l'intervalle $[1, N_d]$) que la matrice de Vandermonde $vdm(X_d)$ de $X_d$ :

$$ vdm(X_d) = (e_\alpha(A_i))_{(i,\alpha) \in [1, N_d] \times \mathbb{N}_d^n}, $$

est une matrice inversible dont le déterminant (non nul) sera noté $VDM(X_d)$. Dans ces conditions, pour toute fonction $f$ définie sur $X_d$, à valeurs dans $\mathbb{K}$, il existe un unique polynôme, noté $L[X_d](f)$, et appelé polynôme d'interpolation de Lagrange de $f$ pour $X_d$, de degré au plus $d$ tel que $L[X_d](f)(A_i) = f(A_i)$ pour $i = 1, \dots, N_d$. Ce polynôme s'obtient par exemple sous la forme de Lagrange par l'expression

$$ L[X_d](f) = \sum_{i=1}^{N_d} f(A_i) \ell_i, \quad \ell_i(x) = \frac{VDM\left(\underset{i}{\overset{i}{X_d}} x\right)}{VDM(X_d)}; \qquad (1) $$

où $\ell_i$ est le polynôme fondamental de Lagrange qui s'annule en tout point de $X_d$ excepté en $A_i$ où il prend la valeur 1. Dans la relation (1), la notation $X_d \stackrel{i}{\rightleftharpoons} x$ signifie qu'on substitue $x$ à $A_i$ dans $X_d$.

Puisque $VDM(X_d)$ est non nul, les $\binom{n+d-1}{d-1} = N_{d-1}$ premières colonnes de ce déterminant forment une famille libre, ce qui met en évidence des entiers $1 \le i_1 < \dots < i_{N_{d-1}} \le N_d$ correspondant à $N_{d-1}$ lignes indépendantes de sorte qu'en posant

$$ X_{d-1} = \{A_{i_1}, \dots, A_{i_{N_{d-1}}}\}, $$

il vient $VDM(X_{d-1}) \neq 0$. Ainsi $X_{d-1}$ se trouve être une partie unisolvante de $\mathbb{K}^n$ de cardinal $N_{d-1}$ et, par la même occasion, on initie un processus qui conduit à une suite de parties unisolvantes dans $\mathbb{K}^n$, de degré $k$ (i.e., pour $0 \le k \le d$, $X_k$ admet $k$ pour degré) : $X_0 \subset \dots \subset X_{d-1} \subset X_d$ ce qui nous conduit à la définition suivante.

**Définition 1.** On appelle structure de Newton d'un ensemble unisolvant $X_d$ de degré $d$ dans $\mathbb{K}^n$ toute suite d'ensembles $X_i$, unisolvant de degré $i$, $i = 0, \dots, d-1$, telle que $X_0 \subset X_1 \subset X_2 \subset \dots \subset X_{d-1} \subset X_d$.

Cette notion a été introduite par Sauer et Xu dans [5] (avec une autre terminologie) dans le but de développer une formule de Newton multidimensionnelle, puis elle a été utilisée par Calvi [2] pour définir de nouveaux tableaux d'interpolation par un procédé d'enlacement (il en existe d'autres mais plus particuliers voir [4] par exemple), dont la généralisation, devenue le produit de Newton, est introduite dans [1] : si $X_0 \subset X_1 \subset X_2 \subset \dots \subset X_{d-1} \subset X_d$ est une structure de Newton de $X_d$ dans $\mathbb{K}^n$ et $Y_0 \subset Y_1 \subset Y_2 \subset \dots \subset Y_{d-1} \subset Y_d$ est une structure de Newton de $Y_d$ dans $\mathbb{K}^m$ alors, voir [2], l'ensemble

$$ Z = \bigcup_{i+j \le d} (X_i \times Y_j) \subset \mathbb{K}^{n+m} $$

est unisolvant de degré $d$ dans $\mathbb{K}^{n+m}$ (avec des règles de calcul s'obtenant à partir de celles sur $X_d$ et $Y_d$). Il est par ailleurs montré dans [1] que des structures différentes sur $X_d$ et $Y_d$ conduisent à des ensembles $Z$ distincts. Du nombre de structures de Newton sur $X_d$ et $Y_d$ découle donc directement le nombre d'ensembles $Z$ distincts pouvant être obtenus à partir de $X_d$ et $Y_d$. Le nombre (plutôt conséquent, nous allons le voir) de telles structures fournit ainsi au numéricien
<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Configuration possible de six points d’interpolation dans $\mathbb{R}^2$</figcaption></figure>

(suivant le problème qu'il étudie) une véritable richesse de possibilités d'interpolation (que l'on pourrait penser à optimiser en comparant par exemple leur constante de Lebesgue mais nous ne nous engagerons pas dans cette voie cf. [2] néanmoins).

Dans la première partie nous étudions en détail le cas $n = 2$ et $d = 2$. Le résultat a été énoncé sans preuve dans [1, 3.5.2]. Dans la seconde partie, on obtient une minoration du nombre de structures de Newton dans le cas général.

Concluons en formulant le problème géométrique équivalent au nôtre qui paraît intéressant en lui-même.

**Problème 2.** Supposons que l'on dispose d'un ensemble $X$ de $N_d(n)$ non situé sur une hypersurface algébrique de degré $d$. Donner une estimation de nombre de sous-ensembles de $X$ de cardinal $N_{d-1}(n)$ non situés sur une hypersurface algébrique de degré $d-1$.

### 3. Le cas $d=2$

On dispose de six points $A_1, \dots, A_6$ du plan, non situés sur une même courbe de degré 2 et donc de $\binom{6}{3} = 20$ sous-ensembles à trois éléments de $X_2$ qui, sous réserve d'unisolvance (ici, non alignés), donneront naissance à un projecteur de Lagrange de degré 1 et donc un ensemble $X_1$ valide. On distingue plusieurs cas suivant la configuration de nos six points.

#### Cas 1 : Aucune droite ne passe par trois points de $X_2$

Ce cas correspond à la figure 1(a). On obtient alors 20 projecteurs de Lagrange de degré 1 ou 20 $X_1$ et par suite $60 = 3 \times 20$ structures de Newton pour $X_2$ puisque n'importe lequel des 3 points de $X_1$ peut servir de $X_0$.

#### Cas 2 : Une seule droite $D$ contient trois points de $X_2$.

Ce cas correspond à la figure 1(b). Cette droite $D$ ne peut alors contenir un quatrième point, car alors, en notant $D'$ la droite passant par les deux points restants, $X_2$ serait inclus dans $D \cup D'$ et ne serait pas unisolvant. On obtient $20 - 1 = 19$ ensembles $X_2$ possibles et 57 structures de Newton possibles.
### Cas 3 : Outre D, une autre droite au moins, nommée $\Delta$, contient trois points de $X_2$

Observons que $D \cap \Delta \cap X_2$ ne peut être vide (car alors $X_2 \subset D \cup \Delta$ avec trois points et trois dans l'autre) et ne peut contenir deux points puisque les droites sont supposées différentes. Supposons donc que $A_1$ soit l'unique point de cette intersection et prenons par exemple $D \cap X_2 = \{A_1, A_2, A_3\}$ et $X_2 \cap \Delta = \{A_1, A_4, A_5\}$, avec $A_6 \notin D \cup \Delta$. S'il existe une autre droite contenant trois points de $X_2$, elle doit passer par $A_6$ et ce peut être qu'une des quatre droites ($A_2A_4$), ($A_2A_5$), ($A_3A_4$) ou ($A_3A_5$). Notons que c'est dans ce contexte seulement que l'on trouve des réseaux de Chung-Yao (cf. [3]).

(1) $A_6$ n'est sur aucune de ces droites (voir Figure 1(c), où $A'_6 = A_6$), il y a donc $18 = 20 - 2$ choix possibles pour $X_1$ et 54 structures de Newton.

(2) $A_6$ est sur une seule de ces droites (voir Figure 1(c) où $A''_6 = A_6$.) qui conduit 17 $X_1$ valides et 51 structures de Newton.

(3) $A_6$ est sur deux de ces droites (voir Figure 1(c), où $A'''_6 = A_6$), on dispose alors de 16 solutions.

Nous avons établi le théorème suivant.

**Théorème 3.** Pour un ensemble plan unisolvant de degré 2, il existe 3(20-k) structures de Newton avec $k \in \{0, 1, 2, 3, 4\}$ et les cinq éventualités peuvent se produire.

**Remarque 4.** Il est naturel de rechercher des ensembles de points unisolvants de degré $d$ sur des hypersurfaces algébriques de degré $d+1$. Considérons la courbe $\Delta$ d'équation $x^3 = y^2$ paramétrée (en dehors de l'origine) par $C(t) = (1/t^2, 1/t^3)$. Un calcul simple montre qu'une famille de trois points $\{A_1 = C(t_1), A_2 = C(t_2), A_3 = C(t_3)\}$ où les $t_i$ sont deux à deux distincts et non nuls est unisolvante de degré 1 si et seulement si $t_1 + t_2 + t_3 \neq 0$. De même, on vérifie sans difficulté que six points $\{A_i = C(t_i), i = 1, \dots, 6\}$ formeront un ensemble unisolvant de degré 2 si et seulement si $\sum_{i=1}^6 t_i \neq 0$. Quatre des cinq types de configurations possibles peuvent être obtenues avec des points situés sur $\Delta$. Par exemple le cas (a) est obtenue en prenant des paramètres $t_i$ de même, le cas (b) est obtenu par exemple avec $t_1 = -3$, $t_2 = 1$ et $t_3 = 1$ qui conduit à l'alignement des trois premiers points, puis, par exemple $t_4 = 3$, $t_5 = 4$ et $t_6 = 5$ qui rend impossible tout autre alignement. La première occurrence du cas (c) s'obtient par exemple avec $t_1 = -3$, $t_2 = 1$ et $t_3 = 1$ et $t_4 = -1$, $t_5 = -6$ et $t_6 = 6$ pour laquelle les points $A_1, A_2, A_3$ puis $A_1, A_4, A_5$ sont alignés. La troisième occurrence s'obtient à partir de la précédente en modifiant la valeur de $t_6$ à -6. La quatrième occurrence ne peut être obtenue car, comme on le vérifie facilement, les conditions d'alignement $t_1+t_4+t_5=0$, $t_1+t_2+t_3=0$, $t_3+t_4+t_6=0$ et $t_2+t_5+t_6=0$ ne peuvent être satisfaites avec des paramètres deux à deux distincts. En revanche, une telle configuration, illustrée sur la Figure 2, peut être obtenue sur la cubique nodale $y^3 - x^3 - yx = 0$.

## 4. Le cas général

On reprend, pour $d \geq 3$ et un espace de dimension $n \geq 2$ quelconque les notations générales et le contexte de la section précédente, en particulier $X_d$ désigne maintenant un ensemble unisolvant de degré $d$ dans $\mathbb{K}^n$ (donc de cardinal $N_d(n)$). Pour simplifier les notations, on posera $N = N_{d-1}(n)$. Supposons que $X_{d-1} = \{A_{i_1}, \dots, A_{i_N}\}$ soit unisolvant de degré $d-1$. On a vu qu'un tel $X_{d-1}$ existe. La matrice de Vandermonde de $X_{d-1} = \{A_{i_1}, \dots, A_{i_N}\}$ étant inversible, si on en supprime la k-ième ligne, on obtient une matrice de rang $N-1$; par conséquent il passe une et une seule hypersurface algébrique $\Gamma$ de degré $\leq d-1$ par tous les points de $X'_k = X_{d-1} \setminus \{A_{i_k}\}$. Cette hypersurface n'est autre que

$$ \Gamma = \{ \ell_{i_k} = 0 \} $$
<figure><img src="image_3.png" /><figcaption>**FIGURE 2** – Exemple de configuration sur la cubique nodale $y^3 - x^3 - yx = 0$ avec quatre droites d'alignement.</figcaption></figure>

où $\ell_{i_k}$ est le polynôme fondamental de Lagrange pour $X_{d-1}$ correspondant au nœud $A_{i_k}$. En effet, il est évident que cette hypersurface convient et si $\{p=0\}$ avec $p \in P_{d-1}(\mathbb{K}^n)$ en est une autre, l'identité

$$p = \sum_{s=1}^{N} p(A_{i_s}) \ell_{i_s}$$

implique que $p = \alpha \ell_{i_k}$ avec $\alpha \neq 0$ de sorte que $\{p=0\} = \Gamma$.

De plus $X_d \cap (\mathbb{K}^n \setminus \Gamma)$ comporte au moins $n+1$ points (dont un est nécessairement $A_{i_k}$). En effet, sinon $X_d$ serait inclus dans la réunion de $\Gamma$ et d'un hyperplan passant par $A_{i_k}$ ce qu'interdit son unisolvance (le polynôme $\ell_{i_k} \times h$ où $h$ est une équation de l'hyperplan serait un polynôme non nul de degré $d$ qui s'annulerait sur $X_d$).

Considérons alors $M_1, \dots, M_n$, $n$ points distincts de $A_{i_k}$, dans $X_d$ et en dehors de $\Gamma$ et posons

$$X_k^r = X_k' \cup \{M_r\}, \quad r = 1, \dots, n.$$

Nous affirmons que chacun de ces $X_k^r$ est unisolvant de degré $d-1$. Pour le montrer, supposons $P \in P_{d-1}(\mathbb{K}^n)$ s'annule sur $X_k^r$. Si $P \neq 0$ alors $P=0$ est une équation de $\Gamma$ (en raison du degré et de l'annulation sur $X_k'$ de $P$) mais $P(M_r) = 0$ et ainsi $M_r$ appartiendrait à $\Gamma$ ce qui n'est pas. Nous avons ainsi montré que la donnée d'un sous-ensemble unisolvant de degré $d-1$ implique, en faisant varier $r$ et $i_k$ l'existence de $N_{d-1} \times n$ autres sous-ensemble unisolvant de degré $d-1$ pour obtenir un total au moins égal à $nN_{d-1}(n) + 1$. Nous avons établi le théorème suivant.

**Théorème 5.**

(1) Pour $d \ge 3$, de tout système unisolvant de degré $d$ dans $\mathbb{K}^n$, on peut extraire au moins $nN_{d-1} + 1$ systèmes unisolvants de degré $d-1$.

(2) Pour tout ensemble unisolvant de degré $d \ge 3$ dans $\mathbb{K}^n$, on dispose d'au moins

$$m_d = (n+1) \prod_{k=2}^{d} (nN_{k-1}(n) + 1) \quad (2)$$

structures de Newton.

**Remarque 6.** En tenant compte du Théorème 3, dans le cas $n=2$, on obtient au moins $48 \prod_{k=3}^{d} (k^2 + k + 1)$ structures de Newton.
**Remarque 7.** En négligeant l'unité dans (2), on a

$$m_d \ge \frac{(n+1)n^{d-1}}{n!^{n-1}} \prod_{k=1}^{d-1} \left(\frac{n+k}{k}\right)^{d-k}.$$

**Remarque 8.** Dans le cas $n = 2$ et $d = 3$, on obtient ainsi une légère amélioration du [1, Théorème 3.11] puisque la minoration 576 donnée dans cette référence peut se remplacer par 624. Il en va de même de celle donnée (dans un cadre plus général) en [1, Section 3.8] dans notre contexte.

**5. Problèmes**

(1) Le Théorème 3 montre que le nombre de configurations possibles est soumis à des conditions arithmétiques. Il serait intéressant de connaître ces conditions dans d'autres cas et d'estimer le nombre de valeurs possibles en général pour le nombre total de structures de Newton.

(2) Il serait souhaitable d'estimer la précision de la minoration donnée au Théorème 5 et de caractériser les configurations possédant un nombre minimal ou quasi minimal de structures de Newton.

(3) Estimer le nombre de structures de Newton d'un ensemble unisolvant $X_d$ de degré $d$ sous l'hypothèse supplémentaire que les points de $X_d$ soient situés sur une hypersurface algébrique de degré $d+1$.

*Remerciements*

Nous remercions Jean-Paul Calvi (Toulouse) pour d'utiles conversations sur le sujet de cette note.

**Références**

[1] F. Bertrand, J.-P. Calvi, « The Newton product of polynomial projectors Part 1 : Construction and algebraic properties », *Int. J. Math.* **30** (2019), n° 6, article no. 1950030 (45 pages).

[2] J.-P. Calvi, « Intertwining unisolvent arrays for multivariate Lagrange interpolation », *Adv. Comput. Math.* **23** (2005), n° 4, p. 393-414.

[3] K. C. Chung, T. Yao, « On lattices admitting unique Lagrange interpolations », *SIAM J. Numer. Anal.* **14** (1977), n° 4, p. 735-743.

[4] M. S. Floater, « Polynomial interpolation on interlacing rectangular grids », *J. Approx. Theory* **222** (2017), p. 64-73.

[5] T. Sauer, Y. Xu, « On multivariate Lagrange interpolation », *Math. Comput.* **64** (1995), n° 211, p. 1147-1170.