Padua points

Image:Padua points fam 1 degree 5.png

Image:Padua points fam 1 degree 6.png

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

:$\backslash text\{Pad\}\_n^s=\backslash lbrace\backslash mathbf\{\backslash xi\}=(\backslash xi\_1,\backslash xi\_2)\backslash rbrace=\backslash left\backslash lbrace\backslash gamma\_s\backslash left(\backslash frac\{k\backslash pi\}\{n(n+1)\}\backslash right),k=0,\backslash ldots,n(n+1)\backslash right\backslash 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 $\backslash operatorname\{Pad\}\_n^s$ is $|\backslash operatorname\{Pad\}\_n^s|\; =\; \backslash 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.

{{citation

|first1 = Marco

|last1 = Caliari

|first2 = Stefano

|last2 = de Marchi | author2-link = Stefano De Marchi

|first3 = Marco

|last3 = Vianello

|title = Algorithm 886: Padua2D—Lagrange Interpolation at Padua Points on Bivariate Domains

|journal = ACM Transactions on Mathematical Software

|year = 2008

|volume = 35

|issue = 3

|pages = 1–11

|doi=10.1145/1391989.1391994

}}

{{citation

|first1 = Len

|last1 = Bos

|first2 = Stefano

|last2 = de Marchi | author2-link = Stefano De Marchi

|first3 = Marco

|last3 = Vianello

|first4 = Yuan

|last4 = Xu

|title = Bivariate Lagrange interpolation at the Padua points: the ideal theory approach

|journal = Numerische Mathematik

|year = 2007

|volume = 108

|issue = 1

|pages = 43–57

|doi = 10.1007/s00211-007-0112-z

|arxiv = math/0604604

}}

The four generating curves are closed parametric curves in the interval $[0,2\backslash pi]$, and are a special case of Lissajous curves.

The generating curve of Padua points of the first family is

:$\backslash gamma\_1(t)=[-\backslash cos((n+1)t),-\backslash cos(nt)],\backslash quad\; t\backslash in\; [0,\backslash pi].$

If we sample it as written above, we have:

:$\backslash operatorname\{Pad\}\_n^1=\backslash lbrace\backslash mathbf\{\backslash xi\}=(\backslash mu\_j,\backslash eta\_k),\; 0\backslash le\; j\backslash le\; n;\; 1\backslash le\; k\backslash le\backslash lfloor\backslash frac\{n\}\{2\}\backslash rfloor+1+\backslash delta\_j\backslash rbrace,$

where $\backslash delta\_j=0$ when $n$ is even or odd but $j$ is even, $\backslash delta\_j=1$

if $n$ and $k$ are both odd

with

:$\backslash mu\_j=\backslash cos\backslash left(\backslash frac\{j\backslash pi\}\{n\}\backslash right),\; \backslash 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 generating curve of Padua points of the second family is

:$\backslash gamma\_2(t)=[-\backslash cos(nt),-\backslash cos((n+1)t)],\backslash quad\; t\backslash in\; [0,\backslash pi],$

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

The generating curve of Padua points of the third family is

:$\backslash gamma\_3(t)=[\backslash cos((n+1)t),\backslash cos(nt)],\backslash quad\; t\backslash in\; [0,\backslash pi],$

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

The generating curve of Padua points of the fourth family is

:$\backslash gamma\_4(t)=[\backslash cos(nt),\backslash cos((n+1)t)],\backslash quad\; t\backslash in\; [0,\backslash pi],$

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

The explicit representation of their fundamental Lagrange polynomial is based on the reproducing kernel $K\_n(\backslash mathbf\{x\},\backslash mathbf\{y\})$, $\backslash mathbf\{x\}=(x\_1,x\_2)$ and $\backslash mathbf\{y\}=(y\_1,y\_2)$, of the space $\backslash Pi\_n^2([-1,1]^2)$ equipped with the inner product

:$\backslash langle\; f,g\backslash rangle\; =\backslash frac\{1\}\{\backslash pi^2\}\; \backslash int\_\{[-1,1]^2\}\; f(x\_1,x\_2)g(x\_1,x\_2)\backslash frac\{dx\_1\}\{\backslash sqrt\{1-x\_1^2\}\}\backslash frac\{dx\_2\}\{\backslash sqrt\{1-x\_2^2\}\}$

defined by

:$K\_n(\backslash mathbf\{x\},\backslash mathbf\{y\})=\backslash sum\_\{k=0\}^n\backslash sum\_\{j=0\}^k\; \backslash hat\; T\_j(x\_1)\backslash hat\; T\_\{k-j\}(x\_2)\backslash hat\; T\_j(y\_1)\backslash hat\; T\_\{k-j\}(y\_2)$

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

:$$

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

where $L^s\_\{\backslash mathbf\backslash xi\}(\backslash mathbf\{x\})$ is the fundamental Lagrange polynomial

:$L^s\_\{\backslash mathbf\backslash xi\}(\backslash mathbf\{x\})=w\_\{\backslash mathbf\backslash xi\}(K\_n(\backslash mathbf\backslash xi,\backslash mathbf\{x\})-T\_n(\backslash xi\_i)T\_n(x\_i)),\backslash quad\; s=1,2,3,4,\backslash quad\; i=2-(s\backslash mod\; 2).$

The weights $w\_\{\backslash mathbf\backslash 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}

• [http://www.math.unipd.it/~marcov/CAApadua.html List of publications related to the Padua points and some interpolation software].

Category:Interpolation