Comptes Rendus Mathématique

François Bertrand

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
This article is licensed under the
Creative Commons Attribution 4.0 International License.
http://creativecommons.org/licenses/by/4.0/
Les Comptes Rendus. Mathématique sont membres du
Centre Mersenne pour l’édition scientifique ouverte
www.centre-mersenne.org
e-ISSN : 1778-3569
Comptes Rendus
Mathématique
2023, Vol. 361, p. 673-678
https://doi.org/10.5802/crmath.436
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 Bertranda
a 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 Nd (n) = dimPd (Kn), n > 1,
unisolvant (de degré d), voir ci-dessous, un sous-ensemble de X de cardinal Nd−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.
ISSN (electronic) : 1778-3569 https://comptes-rendus.academie-sciences.fr/mathematique/
674 François Bertrand
2. Notations et problématique
La dimension Nd = Nd (n) de l’espace Pd (Kn) des polynômes à n variables de degré (total)
inférieur ou égal à d , et à coefficients dans K=R ou C vaut (d+nn ) = (d+nd ). C’est aussi le nombre
de multi-indices α ∈ Nn de longueur |α| ≤ d dont l’ensemble sera noté Nnd . La notation Xd =
{A1, . . . , ANd (n)} représentera une partie unisolvante de K
n pour Pd (K
n). Cela signifie que Xd est
un ensemble de nœuds valide pour l’interpolation par des polynômes de degré au plus d . Si (eα :
x → xα)α∈Nnd est la base canonique de Pd (K
n), l’unisolvance de Xd signifie (où 1, Nd  désigne
classiquement l’ensemble des entiers de l’intervalle [1, Nd ]) que la matrice de Vandermonde
vdm(Xd ) de Xd :
vdm(Xd ) =
(
eα(Ai )
)
(i ,α)∈1,Nd ×Nnd
,
est une matrice inversible dont le déterminant (non nul) sera noté V DM(Xd ). Dans ces condi-
tions, pour toute fonction f définie sur Xd , à valeurs dans K, il existe un unique polynôme, noté
L[Xd ]( f ), et appelé polynôme d’interpolation de Lagrange de f pour Xd , de degré au plus d tel
que L[Xd ]( f )(Ai ) = f (Ai ) pour i = 1, . . . , Nd . Ce polynôme s’obtient par exemple sous la forme de
Lagrange par l’expression
L[Xd ]( f ) =
Nd∑
i=1
f (Ai )ℓi , ℓi (x) =
V DM
(
Xd
i←− x
)
V DM(Xd )
; (1)
où ℓi est le polynôme fondamental de Lagrange qui s’annule en tout point de Xd excepté en Ai
où il prend la valeur 1. Dans la relation (1), la notation Xd
i←− x signifie qu’on substitue x à Ai
dans Xd .
Puisque V DM(Xd ) est non nul, les
(n+d−1
d−1
) = Nd−1 premières colonnes de ce déterminant
forment une famille libre, ce qui met en évidence des entiers 1 ≤ i1 < ·· · < iNd−1 ≤ Nd corres-
pondant à Nd−1 lignes indépendantes de sorte qu’en posant
Xd−1 =
{
Ai1 , . . . , AiNd−1
}
,
il vient V DM(Xd−1) ̸= 0. Ainsi Xd−1 se trouve être une partie unisolvante de Kn de cardinal Nd−1
et, par la même occasion, on initie un processus qui conduit à une suite de parties unisolvantes
dans Kn , de degré k (i.e., pour 0 ≤ k ≤ d , Xk admet k pour degré) : X0 ⊂ ·· · ⊂ Xd−1 ⊂ Xd ce qui
nous conduit à la définition suivante.
Définition 1. On appelle structure de Newton d’un ensemble unisolvant Xd de degré d dans Kn
toute suite d’ensembles Xi , unisolvant de degré i , i = 0, . . . ,d − 1, telle que X0 ⊂ X1 ⊂ X2 ⊂ ·· · ⊂
Xd−1 ⊂ Xd .
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 X0 ⊂ X1 ⊂ X2 ⊂ ·· · ⊂ Xd−1 ⊂ Xd est une structure de
Newton de Xd dans K
n et Y0 ⊂ Y1 ⊂ Y2 ⊂ ·· · ⊂ Yd−1 ⊂ Yd est une structure de Newton de Yd dans
Km alors, voir [2], l’ensemble
Z = ⋃
i+ j≤d
(Xi ×Y j ) ⊂Kn+m
est unisolvant de degré d dansKn+m (avec des règles de calcul s’obtenant à partir de celles sur Xd
et Yd ). Il est par ailleurs montré dans [1] que des structures différentes sur Xd et Yd conduisent
à des ensembles Z distincts. Du nombre de structures de Newton sur Xd et Yd découle donc
directement le nombre d’ensembles Z distincts pouvant être obtenus à partir de Xd et Yd . Le
nombre (plutôt conséquent, nous allons le voir) de telles structures fournit ainsi au numéricien
François Bertrand 675
A1
A2
A3
A4A5
A6
(a)
A1 A2 A3
A4 A5
A6
(b)
A1 A2 A3
A4
A5
A′′′6
A′′6
A′6
(c)
Figure 1 – Configuration possible de six points d’interpolation dans R2
(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 Nd (n) non situé sur une hypersurface
algébrique de degré d. Donner une estimation de nombre de sous-ensembles de X de cardinal
Nd−1(n) non situés sur une hypersurface algébrique de degré d −1.
3. Le cas d = 2
On dispose de six points A1, . . . , A6 du plan, non situés sur une même courbe de degré 2 et donc de(6
3
)= 20 sous-ensembles à trois éléments de X2 qui, sous réserve d’unisolvance (ici, non alignés),
donneront naissance à un projecteur de Lagrange de degré 1 et donc un ensemble X1 valide. On
distingue plusieurs cas suivant la configuration de nos six points.
Cas 1 : Aucune droite ne passe par trois points de X2
Ce cas correspond à la figure 1(a). On obtient alors 20 projecteurs de Lagrange de degré 1 ou 20
X1 et par suite 60 = 3×20 structures de Newton pour X2 puisque n’importe lequel des 3 points
de X1 peut servir de X0.
Cas 2 : Une seule droite D contient trois points de X2.
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, X2 serait inclus dans D∪D ′ et ne
serait pas unisolvant. On obtient 20−1 = 19 ensembles X2 possibles et 57 structures de Newton
possibles.
676 François Bertrand
Cas 3 : Outre D, une autre droite au moins, nommée ∆, contient trois points de X2
Observons que D ∩∆∩ X2 ne peut être vide (car alors X2 ⊂ D ∪∆ 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 A1 soit l’unique point de cette intersection et prenons par exemple D∩X2 = {A1, A2, A3}
et X2 ∩∆= {A1, A4, A5}, avec A6 ∉ D ∪∆. S’il existe une autre droite contenant trois points de X2,
elle doit passer par A6 et ce peut être qu’une des quatre droites (A2 A4), (A2 A5), (A3 A4) ou (A3 A5).
Notons que c’est dans ce contexte seulement que l’on trouve des réseaux de Chung–Yao (cf. [3]).
(1) A6 n’est sur aucune de ces droites (voir Figure 1(c), où A′6 = A6), il y a donc 18 = 20−2
choix possibles pour X1 et 54 structures de Newton.
(2) A6 est sur une seule de ces droites (voir Figure 1(c) où A′′6 = A6.) qui conduit 17 X1 valides
et 51 structures de Newton.
(3) A6 est sur deux de ces droites (voir Figure 1(c), où A′′′6 = A6), 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 ∈ {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∆ d’équation x3 = y2 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 {A1 = C (t1), A2 = C (t2), A3 = C (t3)} où les ti sont deux à deux distincts et non nuls est
unisolvante de degré 1 si et seulement si t1 + t2 + t3 ̸= 0. De même, on vérifie sans difficulté que
six points {Ai = C (ti ), i = 1, . . . ,6} formeront un ensemble unisolvant de degré 2 si et seulement
si
∑6
i=1 ti ̸= 0. Quatre des cinq types de configurations possibles peuvent être obtenues avec des
points situés sur ∆. Par exemple le cas (a) est obtenue en prenant des paramètres ti de même,
le cas (b) est obtenu par exemple avec t1 = −3, t2 = 1 et t3 = 1 qui conduit à l’alignement des
trois premiers points, puis, par exemple t4 = 3, t5 = 4 et t6 = 5 qui rend impossible tout autre
alignement. La première occurrence du cas (c) s’obtient par exemple avec t1 =−3, t2 = 1 et t3 = 1
et t4 = −1, t5 = −6 et t6 = 6 pour laquelle les points A1, A2, A3 puis A1, A4, A5 sont alignés. La
troisième occurrence s’obtient à partir de la précédente en modifiant la valeur de t6 à −6. La
quatrième occurrence ne peut être obtenue car, comme on le vérifie facilement, les conditions
d’alignement t1+t4+t5 = 0, t1+t2+t3 = 0, t3+t4+t6 = 0 et t2+t5+t6 = 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 y3 −x3 − y x = 0.
4. Le cas général
On reprend, pour d ≥ 3 et un espace de dimension n ≥ 2 quelconque les notations générales
et le contexte de la section précédente, en particulier Xd désigne maintenant un ensemble
unisolvant de degré d dansKn (donc de cardinal Nd (n)). Pour simplifier les notations, on posera
N = Nd−1(n). Supposons que Xd−1 = {Ai1 , . . . , AiN } soit unisolvant de degré d −1. On a vu qu’un
tel Xd−1 existe. La matrice de Vandermonde de Xd−1 = {Ai1 , . . . , AiN } é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 Γ de degré ≤ d−1 par tous les points de X ′k = Xd−1\{Aik }. Cette
hypersurface n’est autre que
Γ= {ℓik = 0}
François Bertrand 677
g
Figure 2 – Exemple de configuration sur la cubique nodale y3 − x3 − y x = 0 avec quatre
droites d’alignement.
où ℓik est le polynôme fondamental de Lagrange pour Xd−1 correspondant au nœud Aik . En
effet, il est évident que cette hypersurface convient et si {p = 0} avec p ∈ Pd−1(Kn) en est une
autre, l’identité
p =
N∑
s=1
p (Ais )ℓis
implique que p =αℓik avec α ̸= 0 de sorte que {p = 0} = Γ.
De plus Xd ∩ (Kn\Γ) comporte au moins n + 1 points (dont un est nécessairement Aik ). En
effet, sinon Xd serait inclus dans la réunion de Γ et d’un hyperplan passant par Aik ce qu’interdit
son unisolvance (le polynôme ℓik ×h où h est une équation de l’hyperplan serait un polynôme
non nul de degré d qui s’annulerait sur Xd ).
Considérons alors M1, . . . , Mn , n points distincts de Aik , dans Xd et en dehors de Γ et posons
X rk = X ′k ∪ {Mr }, r = 1, . . . ,n.
Nous affirmons que chacun de ces X rk est unisolvant de degré d −1. Pour le montrer, supposons
P ∈ Pd−1(Kn) s’annule sur X rk . Si P ̸= 0 alors P = 0 est une équation de Γ (en raison du degré et
de l’annulation sur X ′k de P ) mais P (Mr ) = 0 et ainsi Mr appartiendrait à Γ 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 ik l’existence de Nd−1 ×n autres sous-ensemble unisolvant de degré d −1 pour
obtenir un total au moins égal à nNd−1(n)+1. Nous avons établi le théorème suivant.
Théorème 5.
(1) Pour d ≥ 3, de tout système unisolvant de degré d dans Kn , on peut extraire au moins
nNd−1 +1 systèmes unisolvants de degré d −1.
(2) Pour tout ensemble unisolvant de degré d ≥ 3 dans Kn , on disposed’au moins
md = (n +1)
d∏
k=2
(nNk−1(n)+1) (2)
structures de Newton.
Remarque 6. En tenant compte du Théorème 3, dans le cas n = 2, on obtient au moins
48
∏d
k=3(k
2 +k +1) structures de Newton.
678 François Bertrand
Remarque 7. En négligeant l’unité dans (2), on a
md ≥
(n +1)nd−1
n!n−1
d−1∏
k=1
(
n +k
k
)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 Xd de degré d
sous l’hypothèse supplémentaire que les points de Xd 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), no 6, article no. 1950030 (45 pages).
[2] J.-P. Calvi, « Intertwining unisolvent arrays for multivariate Lagrange interpolation », Adv. Comput. Math. 23 (2005),
no 4, p. 393-414.
[3] K. C. Chung, T. Yao, « On lattices admitting unique Lagrange interpolations », SIAM J. Numer. Anal. 14 (1977), no 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), no 211, p. 1147-1170.


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

Yu Chen

Tingbin Cao

Meromorphic solutions of a first order differential equations with delays

Nicola Arcozzi

Nikolaos Chalmoukis

Riesz capacities of a set due to Dobiński

Temha Erkoç

Gamze Akar

Rational Groups whose character degree graphs are disconnected

Nguyen Dang Ho Hai

Stanley–Reisner rings and the occurrence of the Steinberg representation in the hit problem

Amine Amimour

Karima Belaide

Ouagnina Hili

Minimum Hellinger distance estimates for a periodically time-varying long memory parameter

Yann Brenier

Une interprétation variationnelle de la relativité générale dans le vide en termes de transport optimal

Philippe G. LeFloch

Allen M. Tesdall

The positive entropy production property for augmented nonlinear hyperbolic models

Moritz Lang

Mikhail Shkolnikov

Sandpile monomorphisms and limits

Christophe Cuny

Jérôme Dedecker

Florence Merlevède

Magda Peligrad

Berry–Esseen type bounds for the matrix coefficients and the spectral radius of the left random walk on $GL_d({\protect \mathbb{R}})$

Not a member yet