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

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_n^s=\lbrace\mathbf=(\xi_1,\xi_2)\rbrace=\left\lbrace\gamma_s\left(\frac\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,12. The cardinality of the set $\operatorname_n^s$ is $, \operatorname_n^s, = \frac$. Moreover, for each family of Padua points, two points lie on consecutive vertices of the square 1,12, $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 ,2\pi/math>, 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 ,\pi

If we sample it as written above, we have:

:$\operatorname_n^1=\lbrace\mathbf=(\mu_j,\eta_k), 0\le j\le n; 1\le k\le\lfloor\frac\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\right), \eta_k= \begin \cos\left(\frac\right) & j\mbox \\ \cos\left(\frac\right) & j\mbox \end$

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 ,\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 ,\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 ,\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,\mathbf)$, $\mathbf=(x_1,x_2)$ and $\mathbf=(y_1,y_2)$, of the space \Pi_n^2( 1,12) equipped with the inner product

:$\langle f,g\rangle =\frac \int_ f(x_1,x_2)g(x_1,x_2)\frac\frac$

defined by

:$K_n(\mathbf,\mathbf)=\sum_^n\sum_^k \hat T_j(x_1)\hat T_(x_2)\hat T_j(y_1)\hat T_(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=\sqrtT_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 $\operatorname_n^s=\lbrace\mathbf=(\xi_1,\xi_2)\rbrace$, $s=\lbrace 1,2,3,4\rbrace$, the interpolation formula of order $n$ of the function f\colon 1,12\to\mathbb^2 on the generic target point \mathbf\in 1,12 is then

:$\mathcal_n^s f(\mathbf)=\sum_f(\mathbf)L^s_(\mathbf)$

where $L^s_(\mathbf)$ is the fundamental Lagrange polynomial

:$L^s_(\mathbf)=w_(K_n(\mathbf\xi,\mathbf)-T_n(\xi_i)T_n(x_i)),\quad s=1,2,3,4,\quad i=2-(s\mod 2).$

The weights $w_$ are defined as

:$w_=\frac\cdot \begin \frac\text\mathbf\xi\text\\ 1\text\mathbf\xi\text\\ 2\text\mathbf\xi\text \end{cases}$

References

External links

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

Interpolation