Padua points

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 $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 $[-1,1]\times [-1,1]\subset {\mathbb{ℝ}}^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

File:Padua points fam 1 degree 5.png

Padua points of the first family and of degree 5, plotted with their generating curve.

File:Padua points fam 1 degree 6.png

Padua points of the first family and of degree 6, plotted with their generating curve.

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 $n$ and family $s$ can be defined as

${\text{Pad}}_n^s=\{\mathit{\xi }=({\xi }_1,{\xi }_2)\}=\{{\gamma }_s\left(\frac{k\pi }{n(n+1)}\right),k=0,\dots ,n(n+1)\}.$

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 $[-1,1{]}^2$. The cardinality of the set ${\mathrm{Pad}}_n^s$ is $|{\mathrm{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 $[-1,1{]}^2$, $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 $[0,2\pi ]$, and are a special case of Lissajous curves.

The first family

The generating curve of Padua points of the first family is

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

If we sample it as written above, we have:

${\mathrm{Pad}}_n^1=\{\mathit{\xi }=({\mu }_j,{\eta }_k),0\le j\le n;1\le k\le \lfloor \frac{n}{2}\rfloor +1+{\delta }_j\},$

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

${\mu }_j=\cos \left(\frac{j\pi }{n}\right),{\eta }_k=\{\begin{array}{ll}\cos \left(\frac{(2k-2)\pi }{n+1}\right)& j\text{ odd}\\ \cos \left(\frac{(2k-1)\pi }{n+1}\right)& j\text{ even.}\end{array}$

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

The second family

The generating curve of Padua points of the second family is

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

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

The third family

The generating curve of Padua points of the third family is

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

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

The fourth family

The generating curve of Padua points of the fourth family is

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

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

The interpolation formula

The explicit representation of their fundamental Lagrange polynomial is based on the reproducing kernel $K_n(\mathbf{x},\mathbf{y})$, $\mathbf{x}=(x_1,x_2)$ and $\mathbf{y}=(y_1,y_2)$, of the space ${\mathrm{\Pi }}_n^2([-1,1{]}^2)$ equipped with the inner product

$⟨f,g⟩=\frac{1}{{\pi }^2}\underset{[-1,1{]}^2}{\int }f(x_1,x_2)g(x_1,x_2)\frac{d{x}_1}{\sqrt{1-x_1^2}}\frac{d{x}_2}{\sqrt{1-x_2^2}}$

defined by

$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 ${\hat{T}}_j$ representing the normalized Chebyshev polynomial of degree $j$ (that is, ${\hat{T}}_0=T_0$ and ${\hat{T}}_p=\sqrt{2}{T}_p$, where $T_p(\cdot )=\cos (p\arccos (\cdot ))$ is the classical Chebyshev polynomial of first kind of degree $p$). For the four families of Padua points, which we may denote by ${\mathrm{Pad}}_n^s=\{\mathit{\xi }=({\xi }_1,{\xi }_2)\}$, $s=\{1,2,3,4\}$, the interpolation formula of order $n$ of the function $f:[-1,1{]}^2\to {\mathbb{ℝ}}^2$ on the generic target point $\mathbf{x}\in [-1,1{]}^2$ is then

${{ℒ}}_n^{s}f(\mathbf{x})=\sum _{\mathit{\xi }\in {\mathrm{Pad}}_n^s}f(\mathit{\xi })L_{\mathit{\xi }}^s(\mathbf{x})$

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

$L_{\mathit{\xi }}^s(\mathbf{x})=w_{\mathit{\xi }}(K_n(\mathit{\xi },\mathbf{x})-T_n({\xi }_i)T_n(x_i)),s=1,2,3,4,i=2-(smod2).$

The weights $w_{\mathit{\xi }}$ are defined as

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

External links

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