Padua points explained

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.[ -1 , 1 ] x [ -1 , 1 ] \subset 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

n and family s can be defined asPad ^{s = \lbrace \xi = (\xi} _{1 ,\xi} _{2)\rbrace=\left\lbrace\gamma} ^{s\left( (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 \operatorname{Pad} ^{s} _{n} is $|\backslash operatorname\_n^s|\; =\; \backslash frac$. Moreover, for each family of Padua points, two points lie on consecutive vertices of the square [ -1 , 1 ] ^{2} , 2 n -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:

\operatorname{Pad} ^{1= \lbrace \xi = (\mu} _{j, η} _{k),} 0 \le j\le n; 1 \le k\le\lfloor (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( (j\pi)/(n)} \right), η _{k = \begin{cases} \cos\left( (( 2 k -2 )\pi)/(n +1)} \right) & j odd \\ \cos\left( (( 2 k -1 )\pi)/(n +1) \right) & j 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)],} 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

K _{n(x,y)} , x = (x _{1,x} _{2)} and y = (y _{1,y} _{2)} , of the space \Pi ^{2 ([ -1 , 1 ]} _{n} ^{2)} equipped with the inner product\langle f,g\rangle = (1)/(\pi ^{2}) \int _{[ -1 , 1 ] ^{2}} f(x _{1,x} _{2)g(x} _{1,x} ^{2 ) (dx _{1})/(\sqrt{ 1- x ^{2} _{1})} }\frac

defined by

K _{n(x,y)=\sum} ^{k} ^{j =0} \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( ⋅ )=\cos(p\arccos( ⋅ ))} is the classical Chebyshev polynomial of first kind of degree p ). For the four families of Padua points, which we may denote by \operatorname{Pad} ^{s = \lbrace \xi = (\xi} _{1 ,\xi} _{2)\rbrace} , s = \lbrace 1 , 2 , 3 , 4 \rbrace , the interpolation formula of order n of the function f\colon [ -1 , 1 ] ^{2\toR} ^{2} on the generic target point x \in [ -1 , 1 ] ^{2} is thenl{L} ^{s} _{n} f( x ) = \sum _{\xi\in\operatorname{Pad} ^{s}f( \xi )L} ^{n} ^{s} ^{\xi} ( x )

where

L ^{s} _{\xi} ( x ) is the fundamental Lagrange polynomialL ^{s} _{\xi} ( x ) = w _{\xi} (K _{n(\xi,x)-T} _{n(\xi} _{i)T} _{n(x} _{i)),} s =1 , 2 , 3 , 4 , i =2- (s\mod 2 ).

The weights

w _{\xi} are defined asw _{\xi} = (1)/(⋅ \begin{cases} n(n +1 )) (1)/(2) if \xi isavertexpoint \\ 1 if \xi isanedgepoint \\ 2 if \xi isaninteriorpoint. \end{cases}

External links

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