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² n) .^[1] Their name is due to the University of Padua, where they were originally discovered.^[2]

The points are defined in the domain $\scriptstyle [-1,1]\times [-1,1]\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

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

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=\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 $[-1,1]^2$. The cardinality of the set $\scriptstyle \text{Pad}_n^s$ is $\scriptstyle |\text{Pad}_n^s|=N=\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.^[3][4]

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)],\quad t\in [0,\pi].$

If we sample it as written above, we have:

$\text{Pad}_n^1=\lbrace\mathbf{\xi}=(\mu_j,\eta_k), 0\le j\le n; 1\le k\le\lfloor\frac{n}{2}\rfloor+1+\delta_j\rbrace,$

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{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 $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)],\quad 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)],\quad 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)],\quad 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 $\scriptstyle K_n(\mathbf{x},\mathbf{y})$, $\scriptstyle \mathbf{x}=(x_1,x_2)$ and $\scriptstyle \mathbf{y}=(y_1,y_2)$, of the space $\scriptstyle\Pi_n^2([-1,1]^2)$ equipped with the inner product

$\langle f,g\rangle =\frac{1}{\pi^2} \int_{[-1,1]^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

$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 $\scriptstyle \hat T_j$ representing the normalized Chebyshev polynomial of degree $j$ (that is, $\scriptstyle \hat T_0=T_0$, $\scriptstyle \hat T_p=\sqrt{2}T_p$ where $\scriptstyle T_p(\cdot)=\cos(p\arccos(\cdot))$ is the classical Chebyshev polynomial of first kind of degree $p$).^[3] For the four families of Padua points, which we may denote by $\scriptstyle \text{Pad}_n^s=\lbrace\mathbf{\xi}=(\xi_1,\xi_2)\rbrace$, $s=\lbrace 1,2,3,4\rbrace$, the interpolation formula of order $n$ of the function $\scriptstyle f\colon [-1,1]^2\to\mathbb{R}^2$ on the generic target point $\scriptstyle \mathbf{x}\in [-1,1]^2$ is then

$\mathcal{L}_n^s f(\mathbf{x})=\sum_{\mathbf{\xi}\in\text{Pad}_n^s}f(\mathbf{\xi})L^s_{\mathbf\xi}(\mathbf{x})$

where $\scriptstyle L^s_{\mathbf\xi}(\mathbf{x})$ is the fundamental Lagrange polynomial

$L^s_{\mathbf\xi}(\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 $\scriptstyle w_{\mathbf\xi}$ are defined as

$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. L. Bos, M. Caliari; M. Vianello, S. De Marchi,; Xu, Y.; Vianello, M; Xu, Y (2006), "Bivariate Lagrange interpolation at the Padua points: the generating curve approach", J. Approx. Theory 143 (1): 15–25, doi:10.1016/j.jat.2006.03.008
2. M. Caliari, S. De Marchi; Vianello, M.; Vianello, M (2005), "Bivariate polynomial interpolation at new nodal sets", Appl. Math. Comput. 165 (2): 261–274, doi:10.1016/j.amc.2004.07.001
3. M. Caliari, S. De Marchi; Vianello, M. (2008), "Algorithm 886: Padua2D: Lagrange interpolation at Padua points on bivariate domains", ACM T. Math. Software 35 (3)
4. S. De Marchi, L. Bos; Y. Xu, M. Vianello; Vianello, Marco; Xu, Yuan (2007), "Bivariate Lagrange interpolation at the Padua points: the ideal theory approach", Numerische Mathematik 108 (1): 43–57, doi:10.1007/s00211-007-0112-z

External links

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