Points de Padua

Dans l'interpolation polynomiale de deux variables, les points de Padua sont le premier exemple connu (et jusqu'à présent le seul) d'un ensemble de points unisolvant (c'est-à-dire que le polynôme d'interpolation est unique) avec une croissance minimale de leur constante de Lebesgue, avéré être de l'ordre $O(\log ^{2}n)$. Leur nom vient de l'Université de Padoue, où ils ont été découverts à l'origine.

Les points sont définis dans le domaine ${\textstyle [-1,1]\times [-1,1]\subset \mathbb {R} ^{2}}$ . Il est possible d'utiliser les points avec quatre orientations, obtenus avec des rotations successives de 90 degrés : on obtient ainsi quatre familles différentes de points de Padua.

Les quatre familles

Points de Padua de la première famille et de degré 5, tracés avec leur courbe génératrice.

Points de Padua de la première famille et de degré 6, tracés avec leur courbe génératrice.

On peut voir les points de Padua comme un « échantillonnage » d'une courbe paramétrique, dite courbe génératrice, qui est légèrement différente pour chacune des quatre familles, de sorte que les points d'interpolation de degré $n$ et la famille $s$ peut être défini comme

${\text{Pad}}_{n}^{s}=\lbrace \mathbf {\xi } =(\xi _{1},\xi _{2})\rbrace =\left\lbrace \gamma _{s}\left({\frac {k\pi }{n(n+1)}}\right),k=0,\ldots ,n(n+1)\right\rbrace .$

En fait, les points de Padua se situent exactement sur les auto-intersections de la courbe, et sur les intersections de la courbe avec les limites du carré ${\textstyle [-1;1]^{2}}$ . La cardinalité de l'ensemble ${\textstyle {\text{Pad}}_{n}^{s}}$ est ${\textstyle |{\text{Pad}}_{n}^{s}|=N={\frac {(n+1)(n+2)}{2}}}$ . De plus, pour chaque famille de points de Padoue, deux points se trouvent sur des sommets consécutifs du carré $[-1;1]^{2}$, il y a 2n-1 points se trouvent sur les bords du carré, et les points restants se trouvent sur les auto-intersections de la courbe génératrice à l'intérieur du carré.

Les quatre courbes génératrices sont des courbes paramétriques fermées dans l'intervalle $[0;2\pi ]$, et sont un cas particulier des courbes de Lissajous.

La première famille

La courbe génératrice des points de Padua de la première famille est

$\gamma _{1}(t)=[-\cos((n+1)t),-\cos(nt)],\quad t\in [0,\pi ].$

Si on l'échantillonne comme écrit ci-dessus, on a :

${\text{Pad}}_{n}^{1}=\left\lbrace \mathbf {\xi } =(\mu _{j},\eta _{k}),0\leq j\leq n;1\leq k\leq \left\lfloor {\frac {n}{2}}\right\rfloor +1+\delta _{j}\right\rbrace ,$

où $\delta _{j}=0$ lorsque $n$ est pair ou impair mais $j$ est pair, $\delta _{j}=1$ si $n$ et $k$ sont tous les deux impairs

avec

$\mu _{j}=\cos \left({\frac {j\pi }{n}}\right),\eta _{k}={\begin{cases}\cos \left({\frac {(2k-2)\pi }{n+1}}\right)&j{\mbox{ impair}}\\\cos \left({\frac {(2k-1)\pi }{n+1}}\right)&j{\mbox{ pair.}}\end{cases}}$

Il s'ensuit que les points de Padua de la première famille auront deux sommets en bas si $n$ est pair, ou à gauche si $n$ est impair.

La deuxième famille

La courbe génératrice des points de Padua de la deuxième famille est

$\gamma _{2}(t)=[-\cos(nt),-\cos((n+1)t)],\quad t\in [0,\pi ],$

ce qui conduit à avoir des sommets à gauche si $n$ est pair et en bas si $n$ est impair.

La troisième famille

La courbe génératrice des points de Padua de la troisième famille est

$\gamma _{3}(t)=[\cos((n+1)t),\cos(nt)],\quad t\in [0,\pi ],$

ce qui conduit à avoir des sommets sur le dessus si $n$ est pair et à droite si $n$ est impair.

La quatrième famille

La courbe génératrice des points de Padua de la quatrième famille est

$\gamma _{4}(t)=[\cos(nt),\cos((n+1)t)],\quad t\in [0,\pi ],$

ce qui conduit à avoir des sommets à droite si $n$ est pair et supérieur si $n$ est impair.

Formule d'interpolation

La représentation explicite de leur polynôme de Lagrange fondamental est basée sur le noyau reproducteur $K_{n}(\mathbf {x} ,\mathbf {y} )$, $\mathbf {x} =(x_{1},x_{2})$ et $\mathbf {y} =(y_{1},y_{2})$, de l'espace $\Pi _{n}^{2}([-1;1]^{2})$ équipé du produit scalaire

$\langle f,g\rangle ={\frac {1}{\pi ^{2}}}\int _{[-1,1]^{2}}{\frac {f(x_{1},x_{2})}{\sqrt {1-x_{1}^{2}}}}{\frac {g(x_{1},x_{2})}{\sqrt {1-x_{2}^{2}}}}\mathrm {d} x_{1}\mathrm {d} x_{2}$

défini par

$K_{n}(\mathbf {x} ,\mathbf {y} )=\sum _{k=0}^{n}\sum _{j=0}^{k}{\widehat {T}}_{j}(x_{1}){\widehat {T}}_{k-j}(x_{2}){\widehat {T}}_{j}(y_{1}){\widehat {T}}_{k-j}(y_{2})$

avec ${\widehat {T}}_{j}$ représentant le polynôme de Chebyshev normalisé de degré $j$ (soit, ${\widehat {T}}_{0}=T_{0}$, ${\widehat {T}}_{p}={\sqrt {2}}\,T_{p}$ où $T_{p}(\cdot )=\cos(p\arccos(\cdot ))$ est le polynôme classique de Chebyshev de première espèce de degré $p$ ). Pour les quatre familles de pointes de Padoue, que l'on peut désigner par ${\text{Pad}}_{n}^{s}=\lbrace \mathbf {\xi } =(\xi _{1},\xi _{2})\rbrace$, $s=\lbrace 1,2,3,4\rbrace$, la formule d'interpolation d'ordre $n$ de la fonction $f\colon [-1;1]^{2}\to \mathbb {R} ^{2}$ sur le point cible générique $\mathbf {x} \in [-1;1]^{2}$ est alors

${\mathcal {L}}_{n}^{s}f(\mathbf {x} )=\sum _{\mathbf {\xi } \in {\text{Pad}}_{n}^{s}}f(\mathbf {\xi } )L_{\mathbf {\xi } }^{s}(\mathbf {x} )$

où $L_{\mathbf {\xi } }^{s}(\mathbf {x} )$ est le polynôme de Lagrange fondamental

$L_{\mathbf {\xi } }^{s}(\mathbf {x} )=w_{\mathbf {\xi } }(K_{n}(\mathbf {\xi } ,\mathbf {x} )-T_{n}(\xi _{i})T_{n}(x_{i})),\quad s=1,2,3,4,\quad i=2-(s\mod 2).$

Les poids $w_{\mathbf {\xi } }$ sont définis comme

$w_{\mathbf {\xi } }={\frac {1}{n(n+1)}}\cdot {\begin{cases}{\frac {1}{2}}{\text{ si }}\mathbf {\xi } {\text{ est un sommet}}\\1{\text{ si }}\mathbf {\xi } {\text{ est sur un côté}}\\2{\text{ si }}\mathbf {\xi } {\text{ est intérieur.}}\end{cases}}$

Liens externes

• Liste des publications relatives aux points de Padoue et quelques logiciels d'interpolation.