- Padua points
In
polynomial interpolation of two variables, the Padua points are the first known example (and up to now the only one) of "unisolvent" point set (that is, the interpolating polynomial is unique) with "minimal growth" of their Lebesgue constant, proved to be O(log2 "n")citation
first1 = M. Caliari
last1 = L. Bos
first2 = S. De Marchi,
last2 = M. Vianello
first3 = Y.
last3 = Xu
title = Bivariate Lagrange interpolation at the Padua points: the generating curve approach
journal = J. Approx. Theory
volume = 143
issue = 1
pages = 15-25
year = 2006] .Their name is due to theUniversity of Padua , where they were originally discoveredcitation
first1 = S. De Marchi
last1 = M. Caliari
first2 = M.
last2 = Vianello
title = Bivariate polynomial interpolation at new nodal sets
journal = Appl. Math. Comput.
volume = 165
issue = 2
pages = 261-274
year = 2005] .The points are defined in the domain scriptstyle [-1,1] imes [-1,1] subset mathbb{R}^2. It is possible to use the points with four orientations, obtained with subsequent 90-degree rotations: in this way, what we get are 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:ext{Pad}_n^s=lbracemathbf{xi}=(xi_1,xi_2) brace=leftlbracegamma_sleft(frac{kpi}{n(n+1)} ight),k=0,ldots,n(n+1) ight brace.
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 ext{Pad}_n^s, obtained by scriptstyle | ext{Pad}_n^s| is 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 squarecitation
first1 = S. De Marchi
last1 = M. Caliari
first2 = M.
last2 = Vianello
title = Algorithm 886: Padua2D: Lagrange interpolation at Padua points on bivariate domains
journal = ACM T. Math. Software
year = 2008
volume = 35
issue = 3] citation
first1 = M. Vianello
last1 = L. Bos
first2 = Y.
last2 = Xu
title = Bivariate Lagrange interpolation at the Padua points: the ideal theory approach
journal = Numer. Math.
year = 2007
volume = 108
issue = 1
pages = 43-57] .The four generating curves are "closed" parametric curves in the interval 0,2pi] , 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 tin [0,pi] .
If we sample it as written above, we have:
:ext{Pad}_n^1=lbracemathbf{xi}=(mu_j,eta_k), 0le jle n; 1le klelfloorfrac{n}{2} floor+1+delta_j brace,where delta_j=0 when n is even or odd but j is even, delta_j=1if n and k are both odd
with
:mu_j=cosleft(frac{jpi}{n} ight), eta_k=egin{cases}cosleft(frac{(2k-2)pi}{n+1} ight) & jmbox{ odd} \cosleft(frac{(2k-1)pi}{n+1} ight) & jmbox{ even.}end{cases}
From this we can understand 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 tin [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 tin [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 tin [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 thereproducing 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 scriptstylePi_n^2( [-1,1] ^2) equipped with theinner product :langle f,g angle =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^2frac{dx_2}{sqrt{1-x_2^2
defined by
:K_n(mathbf{x},mathbf{y})=sum_{k=0}^nsum_{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(parccos(cdot)) is the classical Chebyshev polynomial "of first kind" of degree p). For the four families of Padua points, that we may denote by scriptstyle ext{Pad}_n^s=lbracemathbf{xi}=(xi_1,xi_2) brace, s=lbrace 1,2,3,4 brace, the interpolation formula of order n of the function scriptstyle fcolon [-1,1] ^2 omathbb{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 ext{Pad}_n^s}f(mathbf{xi})L^s_{mathbfxi}(mathbf{x})
where scriptstyle L^s_{mathbfxi}(mathbf{x}) is the fundamental Lagrange polynomial
:L^s_{mathbfxi}(mathbf{x})=w_{mathbfxi}(K_n(mathbfxi,mathbf{x})-T_n(xi_i)T_n(x_i)),quad s=1,2,3,4,quad i=2-(smod 2).
The weights scriptstyle w_{mathbfxi} are defined as
:w_{mathbfxi}=frac{1}{n(n+1)}cdotegin{cases}frac{1}{2} ext{ if }mathbfxi ext{ is a vertex point}\1 ext{ if }mathbfxi ext{ is an edge point}\2 ext{ if }mathbfxi ext{ is an interior point.}end{cases}
References
Wikimedia Foundation. 2010.