title: Points de Padua
text: # 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 [−1, 1]×[−1, $1]⊂R^2{\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
  
  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é $[−1;1]^2{\textstyle$ [-1;1]^{2}} . La cardinalité de l'ensemble $Pad_n^s{\textstyle$ {\text{Pad}}_{n}^{s}} est $|Pad_n^s|=N=((n+1)(n+2))/2$ {\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}}$
  