Misplaced Pages

In polynomial interpolation of two variables, the Padua points are the first known example (and up to now the only one) of a unisolvent point set (that is, the interpolating polynomial is unique) with minimal growth of their Lebesgue constant, proven to be ${\displaystyle O(\log ^{2}n)}$. Their name is due to the University of Padua, where they were originally discovered.

The points are defined in the domain ${\displaystyle \times \subset \mathbb {R} ^{2}}$. It is possible to use the points with four orientations, obtained with subsequent 90-degree rotations: this way we get four different families of Padua points.

The four families

We can see the Padua point as a "sampling" of a parametric curve, called generating curve, which is slightly different for each of the four families, so that the points for interpolation degree ${\displaystyle n}$ and family ${\displaystyle s}$ can be defined as

${\displaystyle {\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 .}$

Actually, the Padua points lie exactly on the self-intersections of the curve, and on the intersections of the curve with the boundaries of the square ${\displaystyle ^{2}}$. The cardinality of the set ${\displaystyle \operatorname {Pad} _{n}^{s}}$ is ${\textstyle |\operatorname {Pad} _{n}^{s}|={\frac {(n+1)(n+2)}{2}}}$. Moreover, for each family of Padua points, two points lie on consecutive vertices of the square ${\displaystyle ^{2}}$, ${\displaystyle 2n-1}$ points lie on the edges of the square, and the remaining points lie on the self-intersections of the generating curve inside the square.

The four generating curves are closed parametric curves in the interval ${\displaystyle }$, and are a special case of Lissajous curves.

The first family

The generating curve of Padua points of the first family is

${\displaystyle \gamma _{1}(t)=,\quad t\in .}$

If we sample it as written above, we have:

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

where ${\displaystyle \delta _{j}=0}$ when ${\displaystyle n}$ is even or odd but ${\displaystyle j}$ is even, ${\displaystyle \delta _{j}=1}$ if ${\displaystyle n}$ and ${\displaystyle k}$ are both odd

with

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

From this follows that the Padua points of first family will have two vertices on the bottom if ${\displaystyle n}$ is even, or on the left if ${\displaystyle n}$ is odd.

The second family

The generating curve of Padua points of the second family is

${\displaystyle \gamma _{2}(t)=,\quad t\in ,}$

which leads to have vertices on the left if ${\displaystyle n}$ is even and on the bottom if ${\displaystyle n}$ is odd.

The third family

The generating curve of Padua points of the third family is

${\displaystyle \gamma _{3}(t)=,\quad t\in ,}$

which leads to have vertices on the top if ${\displaystyle n}$ is even and on the right if ${\displaystyle n}$ is odd.

The fourth family

The generating curve of Padua points of the fourth family is

${\displaystyle \gamma _{4}(t)=,\quad t\in ,}$

which leads to have vertices on the right if ${\displaystyle n}$ is even and on the top if ${\displaystyle n}$ is odd.

The interpolation formula

The explicit representation of their fundamental Lagrange polynomial is based on the reproducing kernel ${\displaystyle K_{n}(\mathbf {x} ,\mathbf {y} )}$, ${\displaystyle \mathbf {x} =(x_{1},x_{2})}$ and ${\displaystyle \mathbf {y} =(y_{1},y_{2})}$, of the space ${\displaystyle \Pi _{n}^{2}(^{2})}$ equipped with the inner product

${\displaystyle \langle f,g\rangle ={\frac {1}{\pi ^{2}}}\int _{^{2}}f(x_{1},x_{2})g(x_{1},x_{2}){\frac {dx_{1}}{\sqrt {1-x_{1}^{2}}}}{\frac {dx_{2}}{\sqrt {1-x_{2}^{2}}}}}$

defined by

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

with ${\displaystyle {\hat {T}}_{j}}$ representing the normalized Chebyshev polynomial of degree ${\displaystyle j}$ (that is, ${\displaystyle {\hat {T}}_{0}=T_{0}}$ and ${\displaystyle {\hat {T}}_{p}={\sqrt {2}}T_{p}}$, where ${\displaystyle T_{p}(\cdot )=\cos(p\arccos(\cdot ))}$ is the classical Chebyshev polynomial of first kind of degree ${\displaystyle p}$). For the four families of Padua points, which we may denote by ${\displaystyle \operatorname {Pad} _{n}^{s}=\lbrace \mathbf {\xi } =(\xi _{1},\xi _{2})\rbrace }$, ${\displaystyle s=\lbrace 1,2,3,4\rbrace }$, the interpolation formula of order ${\displaystyle n}$ of the function ${\displaystyle f\colon ^{2}\to \mathbb {R} ^{2}}$ on the generic target point ${\displaystyle \mathbf {x} \in ^{2}}$ is then

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

where ${\displaystyle L_{\mathbf {\xi } }^{s}(\mathbf {x} )}$ is the fundamental Lagrange polynomial

${\displaystyle 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).}$

The weights ${\displaystyle w_{\mathbf {\xi } }}$ are defined as

${\displaystyle w_{\mathbf {\xi } }={\frac {1}{n(n+1)}}\cdot {\begin{cases}{\frac {1}{2}}{\text{ if }}\mathbf {\xi } {\text{ is a vertex point}}\\1{\text{ if }}\mathbf {\xi } {\text{ is an edge point}}\\2{\text{ if }}\mathbf {\xi } {\text{ is an interior point.}}\end{cases}}}$

References

1. Caliari, Marco; Bos, Len; de Marchi, Stefano; Vianello, Marco; Xu, Yuan (2006), "Bivariate Lagrange interpolation at the Padua points: the generating curve approach", J. Approx. Theory, 143 (1): 15–25, arXiv:math/0604604, doi:10.1016/j.jat.2006.03.008
2. de Marchi, Stefano; Caliari, Marco; Vianello, Marco (2005), "Bivariate polynomial interpolation at new nodal sets", Appl. Math. Comput., 165 (2): 261–274, doi:10.1016/j.amc.2004.07.001
3. ^ Caliari, Marco; de Marchi, Stefano; Vianello, Marco (2008), "Algorithm 886: Padua2D—Lagrange Interpolation at Padua Points on Bivariate Domains", ACM Transactions on Mathematical Software, 35 (3): 1–11, doi:10.1145/1391989.1391994
4. Bos, Len; de Marchi, Stefano; Vianello, Marco; Xu, Yuan (2007), "Bivariate Lagrange interpolation at the Padua points: the ideal theory approach", Numerische Mathematik, 108 (1): 43–57, arXiv:math/0604604, doi:10.1007/s00211-007-0112-z

External links

• List of publications related to the Padua points and some interpolation software.

• Interpolation