Bivariate Lagrange interpolation at the node points of non-degenerate Lissajous curves

Abstract

Motivated by an application in Magnetic Particle Imaging, we study bivariate Lagrange interpolation at the node points of Lissajous curves. The resulting theory is a generalization of the polynomial interpolation theory developed for a node set known as Padua points. With appropriately defined polynomial spaces, we will show that the node points of non-degenerate Lissajous curves allow unique interpolation and can be used for quadrature rules in the bivariate setting. An explicit formula for the Lagrange polynomials allows to compute the interpolating polynomial with a simple algorithmic scheme. Compared to the already established schemes of the Padua and Xu points, the numerical results for the proposed scheme show similar approximation errors and a similar growth of the Lebesgue constant.

1 Introduction

A challenging task for multivariate polynomial interpolation is the construction of a suitable set of node points. Depending on the application, these node points should provide a series of favorable properties including a unique interpolation in given polynomial spaces, a slow growth of the Lebesgue constant and simple algorithmic schemes that compute the interpolating polynomial. The construction of suitable point sets for multivariate interpolation has a long-standing history. For an overview, we refer to the survey articles [14, 15] and the references therein. Examples of remarkable constructions in the bivariate setting are the point sets introduced by Morrow and Patterson [23], Xu [25], as well as some generalizations of them [18]. A modification of the Morrow-Patterson points, introduced as Padua points [7], is particularly interesting for the purposes of this article.

In some applications, the given data points are lying on subtrajectories of the euclidean space. In this case, aside from the above mentioned favorable properties, it is mandatory that the node points are part of these trajectories. Lissajous curves are particularly interesting examples for us, as they are used as a sampling path in a young medical imaging technology called Magnetic Particle Imaging (MPI) [16].

In MPI, the distribution of superparamagnetic iron oxide nanoparticles is reconstructed by measuring the magnetic response of the particles. The measurement process is based on the combination of various magnetic fields that generate and move a magnetic field free point through a region of interest. Although different trajectories are possible, this movement is typically performed in form of a Lissajous curve [20]. The reconstruction of the particle density from the data on the Lissajous trajectory is currently done in a very straight forward way, either by solving a system of linear equations based on a pre-measured system matrix or directly from the measurement data [17]. By using multivariate polynomial interpolation on the nodes of the sampling path, i.e. the Lissajous curve, it is assumed to obtain a further improvement in the reconstruction process.

Of the node points mentioned above, the Padua points, as described in [3], are the ones with the strongest relation to Lissajous curves. They can be characterized as the node points of a particular degenerate Lissajous figure. Moreover, they satisfy a series of remarkable properties: they can be described as an affine variety of a polynomial ideal [5], they form a particular Chebyshev lattice [11] and they allow a unique interpolation in the space $\Pi _n$ of bivariate polynomials of degree n [3]. Furthermore, a simple formula for the Lagrange polynomials is available and the Lebesgue constants are growing slowly as $\mathcal O\left( \log ^2 n \right)$ [3].

The aim of this article is to develop, similar to the Padua points, an interpolation theory for node points on Lissajous curves. To this end, we extend the generating curve approach as presented in [3] to particular families of Lissajous curves in $[-1,1]^2$. In this article, we will focus on the node points of non-degenerate Lissajous curves, which are important for the application in MPI [19]. Not all of the above mentioned properties of the Padua points will be carried over to the node points of Lissajous figures. However, the resulting theory will have some interesting resemblences, not only to the theory of the Padua points, but also to the Xu points.

We start our investigation by characterizing the node points $\mathrm {LS}_{n,p}$ of non-degenerate Lissajous curves. Based on the node points $\mathrm {LS}_{n,p}$, we will derive suitable quadrature formulas for integration with product Chebyshev weight functions. Next, we will provide the main theoretical results on bivariate interpolation based on the points $\mathrm {LS}_{n,p}$. We will show that the points $\mathrm {LS}_{n,p}$ allow unique interpolation in a properly defined space $\Pi _{n,p}^L$ of bivariate polynomials. Further, we will derive a formula for the fundamental polynomials of Lagrange interpolation. This explicit formula allows the computation of the interpolating polynomial with a simple algorithmic scheme, similar to the one of the Padua points [8]. We conclude this article with some numerical tests for the new bivariate interpolating schemes. Compared to the established interpolating schemes of the Padua and Xu points, the novel interpolation schemes show similar approximation errors and a similar growth of the Lebesgue constant.

2 The node points of non-degenerate Lissajous curves

In this article, we consider $2\pi$-periodic Lissajous curves of the form

$$\begin{aligned} \gamma _{n,p}: {\mathbb R}\rightarrow {\mathbb R}^2, \quad \gamma _{n,p}(t) = \Big ( \sin (nt), \, \sin ((n+p)t) \Big ), \end{aligned}$$

(1)

where n and p are positive integers such that n and $n+p$ are relatively prime. Based on the calculations in [1] (see also [21]), the Lissajous curve $\gamma _{n,p}$ is non-degenerate if and only if p is odd. In this case, $\gamma _{n,p}: [0,2\pi ) \rightarrow {\mathbb R}^2$ is an immersed plane curve with precisely $2 n (n+p) -2 n - p$ self-intersection points. In the following, we will always assume that p is odd and sample the Lissajous curve $\gamma _{n,p}$ along the $4n(n+p)$ equidistant points

$$\begin{aligned} t_k := \frac{2\pi k}{ 4 n (n+p)}, \quad k = 1, \ldots , 4n(n+p).\end{aligned}$$

In this way, we get the following set of Lissajous node points:

$$\begin{aligned} \mathrm {LS}_{n,p}:= \Big \{ \gamma _{n,p}(t_k): k = 1, \ldots , 4n(n+p) \Big \}. \end{aligned}$$

(2)

To characterize the set $\mathrm {LS}_{n,p}$, we divide $\gamma _{n,p}(t_k)$ for the even and odd integers k. For this decomposition, we use the fact that n and $n+p$ are relatively prime. Then, if n is odd, every odd integer k can be written as $k = (2i+1) n + 2j(n+p)$ with $i,j \in {\mathbb Z}$. If k is even, we can write $k = 2 i n + (2j+1)(n+p)$ with $i,j \in {\mathbb Z}$. If n is even, the same holds with the roles of n and $n+p$ switched. In this way, we get the decomposition $\mathrm {LS}_{n,p}= \mathrm {LS}_{n,p}^{\mathrm {b}}\cup \mathrm {LS}_{n,p}^{\mathrm {w}}$ with the sets

$$\begin{aligned} \mathrm {LS}_{n,p}^{\mathrm {b}}&:= \left\{ \gamma _{n,p}\left( \frac{(2i+1)n + 2j (n+p) }{ 4 n (n+p)} 2\pi \right) : i,j \in {\mathbb Z}\right\} ,\end{aligned}$$

(3)

$$\begin{aligned} \mathrm {LS}_{n,p}^{\mathrm {w}}&:= \left\{ \gamma _{n,p}\left( \frac{ 2i n + (2j+1)(n+p)}{ 4 n (n+p)} 2\pi \right) : i,j \in {\mathbb Z}\right\} . \end{aligned}$$

(4)

Two examples of Lissajous curves $\gamma _{n,p}$ with the corresponding node points $\mathrm {LS}_{n,p}^{\mathrm {b}}$ and $\mathrm {LS}_{n,p}^{\mathrm {w}}$ are illustrated in Fig. 1. To get a compact representation of $\mathrm {LS}_{n,p}^{\mathrm {b}}$ and $\mathrm {LS}_{n,p}^{\mathrm {w}}$, we use the following notation for the Chebyshev-Gauß-Lobatto points:

$$\begin{aligned} z_k^{n} := \cos \left( \frac{k\pi }{n}\right) , \quad n \in {\mathbb N}, \; k \in {\mathbb Z}. \end{aligned}$$

(5)

Then, evaluating the points (3) and (4) explicitly for the Lissajous curve (1), we get the following characterization:

$$\begin{aligned} \mathrm {LS}_{n,p}^{\mathrm {b}}&= \left\{ (-1)^{i+j} \Big ( z_{(2i+1)p}^{2(n+p)}, z_{2 j p}^{2n}\Big ): \quad \begin{array}{l} i = 0, \ldots , n+p-1 \\ j = 0, \ldots , n \end{array} \right\} ,\end{aligned}$$

(6)

$$\begin{aligned} \mathrm {LS}_{n,p}^{\mathrm {w}}&= \left\{ (-1)^{i+j} \Big ( z_{2i p}^{2(n+p)}, z_{(2 j + 1) p}^{2n}\Big ): \quad \begin{array}{l} i = 0, \ldots , n+p \\ j = 0, \ldots , n-1 \end{array} \right\} . \end{aligned}$$

(7)

Since p is assumed to be odd and relatively prime to n, p is relatively prime to 2n as well as to $2(n+p)$. Therefore, by rearranging the points, we can drop the number p in the lower indices of the Chebyshev-Gauß-Lobatto points in (6) and (7). Due to the point symmetry of the Lissajous curve $\gamma _{n,p}$, the term $(-1)^{i+j}$ which preceeds the points in (6) and (7) can also be dropped by further rearrangement. This leads to the following simple characterization of the point sets $\mathrm {LS}_{n,p}^{\mathrm {b}}$ and $\mathrm {LS}_{n,p}^{\mathrm {w}}$:

$$\begin{aligned} \mathrm {LS}_{n,p}^{\mathrm {b}}&= \left\{ \Big ( z_{2i'+1}^{2(n+p)}, z_{2 j'}^{2n}\Big ): \quad \begin{array}{l} i' = 0, \ldots , n+p-1 \\ j' = 0, \ldots , n \end{array} \right\} ,\end{aligned}$$

(8)

$$\begin{aligned} \mathrm {LS}_{n,p}^{\mathrm {w}}&= \left\{ \Big ( z_{2i' }^{2(n+p)}, z_{2 j' + 1}^{2n}\Big ): \quad \begin{array}{l} i' = 0, \ldots , n+p \\ j' = 0, \ldots , n-1 \end{array} \right\} . \end{aligned}$$

(9)

With this characterization, we can also divide the points $\mathrm {LS}_{n,p}$ into the sets $\mathrm {LS}_{n,p}^{\mathrm {int}}$ and $\mathrm {LS}_{n,p}^{\mathrm {out}}$ denoting the points lying in the interior and on the boundary of the square $[-1,1]^2$ respectively. We have

From the representation of the points $\mathrm {LS}_{n,p}$ in (8) and (9), it is possible to count the number of points in the different sets. They are listed in Table 1.

Table 1 Cardinality of the different $\mathrm {LS}$ point sets

Fig. 1

Illustration of non-degenerate Lissajous curves $\gamma _{n,p}$. The node points $\mathrm {LS}_{n,p}$ of $\gamma _{n,p}$ are arranged on two different grids (black, white) corresponing to the sets $\mathrm {LS}_{n,p}^{\mathrm {b}}$ and $\mathrm {LS}_{n,p}^{\mathrm {w}}$. Lissajous figure $\gamma _{2,1}$, $|\mathrm{LS}_{2,1}|=17$ (Left). Lissajous figure $\gamma _{2,3}$, $|\mathrm{LS}_{2,3}|=27$ (Right)

From the representation in (3) and (4) and its identification in (6) and (7), we can deduce that

$$\begin{aligned} \gamma _{n,p}\left( \frac{(2i+1)n + 2j (n+p) }{ 4 n (n+p)} 2\pi \right)&= \gamma _{n,p}\left( \frac{(2i+1)n - 2j (n+p) }{ 4 n (n+p)} 2\pi \right) ,\\ \gamma _{n,p}\left( \frac{ 2i n + (2j+1)(n+p)}{ 4 n (n+p)} 2\pi \right)&= \gamma _{n,p}\left( \frac{ - 2i n + (2j+1)(n+p)}{ 4 n (n+p)} 2\pi \right) \end{aligned}$$

holds for all $i,j \in {\mathbb Z}$. Moreover, in (3) and (4) the boundary points are represented by $j \in n {\mathbb Z}$ and $i \in (n+p) {\mathbb Z}$, respectively. Thus, for interior points in $\mathrm {LS}_{n,p}^{\mathrm {b}}\cap \mathrm {LS}_{n,p}^{\mathrm {int}}$, i.e. all points in (3) satisfying $j \ne n {\mathbb Z}$, there exist at least two different $1 \le k,k' \le 4n(n+p)$ in (2) that represent the same point. The same holds for all interior points in the second set $\mathrm {LS}_{n,p}^{\mathrm {w}}$.

Therefore, all points in $\mathrm {LS}_{n,p}^{\mathrm {int}}$ are self-intersection points of the Lissajous curve $\gamma _{n,p}$. Since $|\mathrm {LS}_{n,p}^{\mathrm {int}}| = 2n(n+p) - 2 n - p$ corresponds to the total number of self-intersection points of a non-degenerate Lissajous curve (see [1]), we can conclude that $\mathrm {LS}_{n,p}^{\mathrm {int}}$ is precisely the set of all self-intersection points of the Lissajous curve $\gamma _{n,p}$. Finally, since $2 | \mathrm {LS}_{n,p}^{\mathrm {int}}| + |\mathrm {LS}_{n,p}^{\mathrm {out}}| = 4n(n+p)$, we can also conclude that there are exactly two different $1 \le k,k' \le 4n(n+p)$ that represent the same point in $\mathrm {LS}_{n,p}^{\mathrm {int}}$ and that every point in $\mathrm {LS}_{n,p}^{\mathrm {out}}$ is described by exactly one $1 \le k\le 4n(n+p)$ in (2).

In order to identify the different integers k in (2) that describe the same point $\AA \in \mathrm {LS}_{n,p}$, we introduce for $k,k' \in {\mathbb Z}$ the equivalence relation

$$\begin{aligned} k \overset{\mathrm {LS}_{n,p}}{\sim }k' \quad \Leftrightarrow \quad \gamma _{n,p}(t_k) = \gamma _{n,p}(t_{k'}). \end{aligned}$$

We say that $k \in {\mathbb Z}$ belongs to the equivalence class $[\mathcal {A}]$, $\AA \in \mathrm {LS}_{n,p}$, if $\gamma _{n,p}(t_k) = \mathcal {A}$. Therefore, by the above argumentation, there is exactly one ${1 \le k \le 4n(n+p)}$ in the equivalence class $[\mathcal {A}]$ if $\AA \in \mathrm {LS}_{n,p}^{\mathrm {out}}$ and exactly two if $\mathcal {A}\in \mathrm {LS}_{n,p}^{\mathrm {int}}$.

Remark 1

There are some remarkable relations between the $\mathrm {LS}$, Padua and Xu points. In formal terms, if $p = 0$ in the characterization (8) and (9) of the $\mathrm {LS}_{n,p}$ points, the points $\mathrm {LS}_{n,0}$ correspond with the even Xu points $\mathrm {XU}_{2n}$ as defined in [25]. Moreover, if $p = \frac{1}{2}$ in (8) and (9), we obtain the even Padua points $\mathrm {PD}_{2n}$ of the second family (see [8] and (22), (23) in Sect. 6) with a slight adjustment in the range of the indices. A further comparison of these three point sets in terms of numerical simulations is given in the last section of this article. Finally we would like to add that the points $\mathrm {LS}_{n,p}$, similarly to the Padua points, can be considered as two-dimensional Chebyshev lattices of rank 1 (see [11]).

3 Quadrature formulas based on the Lissajous node points

In this section, we study quadrature rules for bivariate integration defined by point evaluations at the points $\mathrm {LS}_{n,p}$. As underlying polynomial spaces in ${\mathbb R}^2$, we consider

$$\begin{aligned} \Pi _n = {\text {span}}\{T_{i}(x) T_j(y):\; i+j \le n\}, \end{aligned}$$

where $T_i(x)$ denotes the Chebyshev polynomial $T_i(x) = \cos (i \arccos x)$ of the first kind. It is well-known (cf. [12, 25]) that $\{ T_i(x) T_j(y):\; i+j \le n\}$ is an orthogonal basis of $\Pi _n$ with respect to the inner product

$$\begin{aligned} \langle f,g \rangle := \frac{1}{\pi ^2} \int _{-1}^1 \int _{-1}^1 f(x,y) g(x,y) \frac{1}{\sqrt{1-x^2}} \frac{1}{\sqrt{1-y^2}} \mathrm {d}x \mathrm {d}y. \end{aligned}$$

(10)

The corresponding orthonormal basis is given by $\{\hat{T}_i(x) \hat{T}_j(y): i+j \le n \}$, where

$$\begin{aligned} \hat{T}_i(x) = \left\{ \begin{array}{ll} 1, &{} \quad \hbox {if }\, i = 0, \\ \sqrt{2} T_i(x), &{} \quad \hbox {if }\, i \ne 0. \end{array} \right. \end{aligned}$$

Using the trajectory $\gamma _{n,p}$, it is possible to reduce a double integral of the form used in (10) into a single integral for a large class of bivariate polynomials.

Lemma 1

For all polynomials $P \in \Pi _{8n+4p-1}$ with $\langle P, T_{2(n+p)}(x)T_{2n}(y) \rangle = 0$, the following formula holds:

$$\begin{aligned} \frac{1}{\pi ^2} \int _{-1}^1 \int _{-1}^1 P(x,y) \frac{1}{\sqrt{1-x^2}} \frac{1}{\sqrt{1-y^2}} \mathrm {d}x \mathrm {d}y = \frac{1}{2\pi } \int _0^{2\pi } P(\gamma _{n,p}(t)) \mathrm {d}t. \end{aligned}$$

(11)

Proof

We check (11) for all basis polynomials $T_i(x) T_j(y)$ in the space $\Pi _{8n+4p-1}$. For the left hand side of (11) we get the value 1 if $(i,j) = (0,0)$ and 0 otherwise. For the right hand side of (11) we get also 1 if $(i,j) = (0,0)$. For $(i,j) \ne (0,0)$ we get for $P(x,y) = T_i(x) T_j(y)$ the expression

$$\begin{aligned} \frac{1}{2\pi } \int _0^{2\pi } P(\gamma _{n,p}(t)) \mathrm {d}t&= \frac{1}{2\pi } \int _0^{2\pi } T_i(\sin (nt)) T_j( \sin ((n+p)t)) \mathrm {d}t \\&= \frac{1}{2\pi } \int _0^{2\pi } \cos \left( i n t - i \frac{\pi }{2} \right) \cos \left( j (n+p) t - j \frac{\pi }{2} \right) \mathrm {d}t. \end{aligned}$$

We now determine for which indices (i, j) this integral is different from 0. This is only the case if $in = j(n+p)$ and $i-j$ is even. Since the numbers n and $n+p$ are relatively prime, this can only be the case if $i = k(n+p)$, $j = nk$ and $k \in 2 {\mathbb N}$ is an even number. We see that the smallest possible value for k is $k = 2$ and the second smallest is $k = 4$. Furthermore, the sum of the respective indices is given by $i + j = (2n+p)k$. Therefore, we can conclude that for all indices (i, j) satisfying $i+j = 1, \ldots , 4n+2p-1$ and $i+j = 4n+2p+1, \ldots , 8n + 4p -1$ the right hand side of (11) vanishes. If $i+j = 4n+2p$, the above integral is nonzero only if $i = 2(n+p)$ and $j = 2n$. $\square$

To get a quadrature formula supported on the points $\mathrm {LS}_{n,p}$, we define a suitable polynomial subspace

$$\begin{aligned} \Pi _{n,p}^Q = {\text {span}}\{T_{i}(x) T_j(y):(i,j) \in \Gamma _{n,p}^Q\} \end{aligned}$$

with the index set $\Gamma _{n,p}^Q \subset {\mathbb N}_0^2$ given by

$$\begin{aligned} \Gamma _{n,p}^Q := \Big \{(i,j): \; i\!+\!j \le 4n \!-\! 1 \Big \}&\cup \! \bigcup _{m = 0}^{4p-1} \! \left\{ (i,j): \; i\!+\!j = 4n \! +\! m,\; j < \frac{n(4p \!-\! m)}{p} \right\} . \end{aligned}$$

Note that the particular index $(i,j) = (2(n+p),2n)$ is not included in $\Gamma _{n,p}^Q$ and that Lemma 1 is applicable for all polynomials $P \in \Pi _{n,p}^Q$. An example of the index set $\Gamma _{n,p}^Q$ is shown in Fig. 2. Clearly, the polynomial space $\Pi _{n,p}^Q$ satisfies $\Pi _{4n-1} \subset \Pi _{n,p}^Q \subset \Pi _{4n+4p-1}$ and the dimension of $\Pi _{n,p}^Q$ can be computed as

$$\begin{aligned} \dim \Pi _{n,p}^Q \,{=}\, |\Gamma _{n,p}^Q| \,{=}\, 8n(n+p) \,{+}\, 4 n \,{-}\, 2(p-1) \,{=}\, 4(|\mathrm {LS}_{n,p}|-n-p) - 2(p-1). \end{aligned}$$

Fig. 2

Illustration of the index set $\Gamma _{2,1}^Q$ with black and white bullets. We have $|\Gamma _{2,1}^Q| = 56$ black and white bullets. The black bullets correspond to indices describing the polynomial space $\Pi _{4n-1}$. The black cross is not contained in $\Gamma _{2,1}^Q$. It corresponds to the special index $(i,j) = (6,4)$ appearing in Lemma 1

For points $\AA \in \mathrm {LS}_{n,p}$, we define the quadrature weights

$$\begin{aligned} w_{\mathcal {A}} := \left\{ \begin{array}{ll} \displaystyle \frac{1}{4n(n+p)}, \quad &{} \text {if}\; \mathcal {A}\in \mathrm {LS}_{n,p}^\mathrm {out}, \\ \displaystyle \frac{2}{4n(n+p)}, \quad &{} \text {if}\; \mathcal {A}\in \mathrm {LS}_{n,p}^\mathrm {int}. \end{array}\right. \end{aligned}$$

Then, we get the following quadrature rule based on the node set $\mathrm {LS}_{n,p}$:

Theorem 1

For all $P \in \Pi _{n,p}^Q$ the quadrature formula

$$\begin{aligned} \frac{1}{\pi ^2} \int _{-1}^1 \int _{-1}^1 P(x,y) \frac{1}{\sqrt{1-x^2}} \frac{1}{\sqrt{1-y^2}} \mathrm {d}x \mathrm {d}y = \sum _{\mathcal {A}\in \mathrm {LS}_{n,p}} w_{\mathcal {A}} P(\mathcal {A}) \end{aligned}$$

(12)

is exact.

Proof

For all trigonometric $2\pi$-periodic polynomials q of degree less than $4n(n+p)$, the following composite trapezoidal quadrature rule is exact:

$$\begin{aligned} \frac{1}{2\pi } \int _0^{2\pi } q(t) dt = \frac{1}{4n(n+p)} \sum _{k=1}^{4n(n+p)} q\left( t_k \right) . \end{aligned}$$

Since $\Pi _{n,p}^Q \subset \Pi _{8n+4p-1}$ and $\Pi _{n,p}^Q \perp T_{2(n+p)}(x)T_{2n}(y)$, we have by Lemma 1 the identity

$$\begin{aligned} \frac{1}{\pi ^2} \int _{-1}^1 \int _{-1}^1 P(x,y) \frac{1}{\sqrt{1-x^2}} \frac{1}{\sqrt{1-y^2}} \mathrm {d}x \mathrm {d}y = \frac{1}{2\pi } \int _0^{2\pi } P(\gamma _{n,p}(t)) \mathrm {d}t. \end{aligned}$$

Thus, if we show that for $P \in \Pi _{n,p}^Q$ the trigonometric polynomial $P(\gamma _{n,p}(t))$ is of degree less than $4n(n+p)$, we immediately get the quadrature formula

$$\begin{aligned} \frac{1}{\pi ^2} \int _{-1}^1 \int _{-1}^1 P(x,y) \frac{1}{\sqrt{1-x^2}} \frac{1}{\sqrt{1-y^2}} \mathrm {d}x \mathrm {d}y&= \frac{1}{4n(n+p)} \sum _{k=1}^{4n(n+p)} P ( \gamma _{n,p}(t_k)) \\&= \sum _{\mathcal {A}\in \mathrm {LS}_{n,p}} w_\mathcal {A}P(\mathcal {A}). \end{aligned}$$

To finish the proof we consider the representation of the polynomial $P \in \Pi _{n,p}^Q$ in the orthogonal basis $\{T_{i}(x) T_j(y):\; (i,j) \in \Gamma _{n,p}^Q \}$ and get

$$\begin{aligned} P(\gamma _{n,p}(t))&= \sum _{(i,j) \in \Gamma _{n,p}^Q} a_{ij} T_i(\sin n t) T_j(\sin (n+p)t) \\&= \sum _{(i,j) \in \Gamma _{n,p}^Q} a_{ij} \cos \left( int - i \textstyle \frac{\pi }{2}\right) \cos \left( j (n+p) t - j \textstyle \frac{\pi }{2}\right) \end{aligned}$$

for some coefficients $a_{ij} \in {\mathbb R}$. In order for the trigonometric polynomials in this formula to have a degree less than $4n(n+p)$, the indices (i, j) have to satisfy the condition

$$\begin{aligned} (i+j) n + jp < 4n(n+p). \end{aligned}$$

In the case that $i+j < 4n$, we have $(i+j)n + jp \le (i+j)n + 4np < 4n(n+p)$ and the condition above is satisfied.

In the case that $i + j = 4n+m$ with $0 \le m \le 4p-1$, we have $(i+j)n + jp = 4n^2 + m n + j p < 4n(n+p)$ and the condition above is satisfied for all j with $j < \frac{n(4p-m)}{p}$. By definition, this condition is exactly satisfied for all indices $(i,j) \in \Gamma _{n,p}^Q$ and therefore for all polynomials $P \in \Pi _{n,p}^Q$. $\square$

Remark 2

Lemma 1 and Theorem 1 are generalizations of corresponding results proven in [3] for the Padua points. An analogous formula also exists for the Xu points (see [23, 25]). Furthermore, the cardinality of the Xu points $\mathrm {XU}_{2n}$ is known to be minimal for exact integration of bivariate polynomials in $\Pi _{4n-1}$ with respect to a product Chebyshev weight function (see [22, 25]). Since $|\mathrm {LS}_{n,p}| > |\mathrm {XU}_{2n}| = 2 n (n+1)$, this is not the case for the points $\mathrm {LS}_{n,p}$. On the other hand, as illustrated in Fig. 2, the space $\Pi _{n,p}^Q$, for which (12) is exact, shows a remarkable asymmetry. As for multivariate interpolation, the construction of suitable nodes for cubature rules has a long history. For an overview and further literature, we refer to the survey article [10] and the book [12].

4 Interpolation on the Lissajous node points

Given the quadrature formulas of the last section, we now investigate bivariate interpolation at the points $\mathrm {LS}_{n,p}$. The corresponding interpolation problem can be formulated as follows: for given function values $f_{\mathcal {A}} \in {\mathbb R}$, $\AA \in {\text {LS}}_{n,p}$, we want to find a unique bivariate interpolating polynomial $\mathcal {L}_{n,p} f$ such that

$$\begin{aligned} \mathcal {L}_{n,p} f(\mathcal {A}) = f_\mathcal {A}\quad \text {for all}\; \mathcal {A}\in \mathrm {LS}_{n,p}. \end{aligned}$$

(13)

To set this problem correctly, we have to fix an underlying interpolation space. This space is linked to $\Pi _{n,p}^Q$ and defined as

$$\begin{aligned} \Pi _{n,p}^L := {\text {span}}\{T_{i}(x) T_j(y): (i,j) \in \Gamma _{n,p}^L\} \end{aligned}$$

on the index set

$$\begin{aligned} \Gamma _{n,p}^L := \Big \{(i,j): \; i+j \le 2n \Big \} \cup \bigcup _{m = 1}^{2p-1} \left\{ (i,j): \; i+j = 2n+m,\; j < \frac{n(2p-m)}{p} \right\} . \end{aligned}$$

Examples of sets $\Gamma _{n,p}^L$ with different values of p are given in Fig. 3. The reproducing kernel $K_{n,p}^L: {\mathbb R}^2 \times {\mathbb R}^2 \rightarrow {\mathbb R}$ of the polynomial space $\Pi _{n,p}^L$ is given as

$$\begin{aligned} K_{n,p}^L(x_{\mathcal {A}},y_{\mathcal {A}}; x_{\mathcal {B}}, y_{\mathcal {B}}) = \sum _{(i,j) \in \Gamma _{n,p}^L} \hat{T}_i(x_{\mathcal {A}}) \hat{T}_i(x_{\mathcal {B}}) \hat{T}_j(y_{\mathcal {A}}) \hat{T}_j(y_{\mathcal {B}}). \end{aligned}$$

It is straightforward to check that the kernel $K_{n,p}^L$ has the reproducing property

$$\begin{aligned} \langle P, K_{n,p}^L(x,y; \cdot ) \rangle = P(x,y) \end{aligned}$$

for all polynomials $P \in \Pi _{n,p}^L$. We have $\Pi _{2n} \subset \Pi _{n,p}^L \subset \Pi _{2(n+p)-1}$. The dimension of the polynomial space $\Pi _{n,p}^L$ is given as

$$\begin{aligned} \dim (\Pi _{n,p}^L)&= |\Gamma _{n,p}^L| = \frac{(2n+1)(2n+2)}{2} + \sum _{m=1}^{2p-1} \left\lceil \frac{n(2p-m)}{p} \right\rceil \\&= 2n^2 + n (2p+2) + p = |\mathrm {LS}_{n,p}|. \end{aligned}$$

Therefore, the dimension $\dim (\Pi _{n,p}^L)$ of the polynomial space $\Pi _{n,p}^L$ corresponds precisely to the number of points in $\mathrm {LS}_{n,p}$.

Fig. 3

Illustration of the index sets $\Gamma _{n,p}^L$. The black bullets correspond to indices describing the polynomial space $\Pi _{2n}$. Index set $\varGamma _{2,1}^L$ with $|\varGamma _{2,1}^L|=17$ (Left). Index set $\varGamma _{2,3}^L$ with $|\varGamma _{2,3}^L|=27$ (Right)

Soon, we will deduce a formula for the fundamental polynomials of Lagrange interpolation with respect to the points in $\mathrm {LS}_{n,p}$ and show that the interpolation problem (13) has a unique solution. To this end, we investigate an isomorphism between the polynomial space $\Pi _{n,p}^L$ and the subspace

$$\begin{aligned} \Pi _{2n(n+p)}^{\mathrm {trig},L}\!:= \left\{ q \in \! \Pi _{2n(n+p)}^{\mathrm {trig}}\!\!: \; q(t_k) = q(t_{k'})\text { for all }k,k'\text { with }k \!\!\overset{\mathrm {LS}_{n,p}}{\sim }\!\! k' \right\} \end{aligned}$$

(14)

of $2\pi$-periodic trigonometric polynomials

$$\begin{aligned} \Pi _{2n(n+p)}^{\mathrm {trig}} := \left\{ q(t) = \sum _{m=0}^{2n(n+p)} a_m \cos (m t) + \sum _{m=1}^{2n(n+p) - 1} b_m \sin (mt):\quad a_m, b_m \in {\mathbb R}\right\} . \end{aligned}$$

Theorem 2

The operator

$$\begin{aligned} {\text {E}}_\gamma : \Pi _{n,p}^L\rightarrow \Pi _{2n(n+p)}^{\mathrm {trig},L}, \quad {\text {E}}_\gamma \! P(t) = P(\gamma _{n,p}(t)), \quad t \in [0,2\pi ], \end{aligned}$$

defines an isometric isomorphism from the space $\left( \Pi _{n,p}^L, \langle \cdot , \cdot \rangle \right)$ onto the space $\Pi _{2n(n+p)}^{\mathrm {trig},L}$ equipped with the inner product $\langle q_1, q_2 \rangle = \frac{1}{2\pi } \int _0^{2\pi } \!\!\! q_1(t) q_2(t) \mathrm {d}t$.

Proof

The system $\left\{ \hat{T}_i(x) \hat{T}_j(y): (i,j) \in \Gamma _{n,p}^L \right\}$ forms an orthonormal basis of the space $\Pi _{n,p}^L$. The image

$$\begin{aligned} e_{ij} (t) := {\text {E}}_\gamma \! \left( \! \hat{T}_{i}(x) \hat{T}_{j}(y)\! \right) \! (t), \quad (i,j) \in \Gamma _{n,p}^L, \end{aligned}$$

of this basis under the linear operator ${\text {E}}_\gamma$ is given by

$$\begin{aligned} e_{ij} (t) = \left\{ \begin{array}{ll} \, 1, &{} \text {if}\; (i,j) = (0,0), \\ \sqrt{2} \cos \left( i n t - i \frac{\pi }{2} \right) , &{} \text {if}\; j=0, i < 2(n+p), \\ \sqrt{2} \cos \left( j (n+p) t - j \frac{\pi }{2} \right) , &{} \text {if}\; i=0, j \le 2n, \\ \,2 \cos \! \left( i n t - i \frac{\pi }{2}\right) \cos \left( j (n+p) t - j \frac{\pi }{2} \right) ,\quad &{} \text {otherwise}. \end{array} \right. \end{aligned}$$

(15)

For $(i,j) \in \Gamma _{n,p}^L$, $j \ne 2n$, the functions $e_{ij} (t)$ are trigonometric polynomials of degree less than $2n(n+p)$. The only trigonometric polynomial of exact degree $2n(n+p)$ is precisely $e_{0,2n}$. By the definition of the operator ${\text {E}}_\gamma$, the values ${\text {E}}_\gamma \! P (t_k)$ and ${\text {E}}_\gamma \! P (t_{k'})$, $t_k \ne t_{k'}$ coincide if $\gamma _{n,p}(t_k) = \gamma _{n,p}(t_{k'})$ is a self-intersection point of $\gamma _{n,p}$. This is precisely encoded in the constraints given in (14). We can conclude that ${\text {E}}_\gamma$ maps $\Pi _{n,p}^L$ into the space $\Pi _{2n(n+p)}^{\mathrm {trig},L}$.

For polynomials $P_1,P_2 \in \Pi _{n,p}^L$, the product polynomial $P_1 P_2$ is an element of the space $\Pi _{8n+4p-1}$ and satisfies $\langle P_1 P_2, T_{2(n+p)}(x)T_{2n}(y) \rangle = 0$. Therefore, by Lemma 1, the set $\left\{ e_{ij} : \; (i,j) \in \Gamma _{n,p}^L \right\}$ is an orthonormal system in $\Pi _{2n(n+p)}^{\mathrm {trig},L}$, and thus, ${\text {E}}_\gamma$ is an isometric embedding from $\Pi _{n,p}^L$ into $\Pi _{2n(n+p)}^{\mathrm {trig},L}$.

Now, if we can show that the dimensions of $\Pi _{n,p}^L$ and $\Pi _{2n(n+p)}^{\mathrm {trig},L}$ coincide, the proof is finished. To this end, we consider in $\Pi _{2n(n+p)}^{\mathrm {trig}}$ the Dirichlet kernel

$$\begin{aligned} D_{2n(n+p)}(t):= & {} \frac{1 + \cos (2n(n+p)t) + 2 \sum _{k=1}^{2n(n+p)-1} \cos (kt)}{4n(n+p)} \\= & {} \frac{\sin (2n(n+p) t ) \cos \frac{t}{2} }{4n(n+p) \sin \frac{t}{2}} . \end{aligned}$$

It is well-known that the trigonometric polynomials

$$\begin{aligned} D_{2n(n+p)}^k(t) := D_{2n(n+p)}\left( t - t_k \right) , \quad k = 1, \ldots , 4n(n+p), \end{aligned}$$

are precisely the Lagrange polynomials in the space $\Pi _{2n(n+p)}^{\mathrm {trig}}$ with respect to the points $t_k$, $k = 1, \ldots , 4n(n+p)$ (see [26, Chapter X, 3]), i.e.

$$\begin{aligned} D_{2n(n+p)}^k \left( t_{k'} \right) = \delta _{k,k'}, \quad 1 \le k,k' \le 4n(n+p). \end{aligned}$$

In general, the polynomials $D_{2n(n+p)}^k$ do not lie in the subspace $\Pi _{2n(n+p)}^{\mathrm {trig},L}$. However, we can define a basis for $\Pi _{2n(n+p)}^{\mathrm {trig},L}$ by using the linear combinations

$$\begin{aligned} l_\mathcal {A}(t) := \sum _{\begin{array}{c} k = 1, \ldots , 4n(n+p): \\ k \in [\mathcal {A}] \end{array}} D_{2n(n+p)}^k(t), \quad \mathcal {A}\in \mathrm {LS}_{n,p}. \end{aligned}$$

(16)

Clearly, the polynomials $l_\mathcal {A}$ are elements of $\Pi _{2n(n+p)}^{\mathrm {trig},L}$, and $l_{\mathcal {A}}(t_k)$ is equal to one if $k \in [\mathcal {A}]$ and zero if $k \notin [\mathcal {A}]$. Thus, the system $\{l_\mathcal {A}: \; \AA \in \mathrm {LS}_{n,p}\}$ forms a basis of $\Pi _{2n(n+p)}^{\mathrm {trig},L}$ and $\dim (\Pi _{2n(n+p)}^{\mathrm {trig},L}) = |\mathrm {LS}_{n,p}|$. This corresponds exactly with the dimension of the space $\Pi _{n,p}^L$. $\square$

Theorem 3

For $\AA = (x_{\mathcal {A}}, y_{\mathcal {A}}) \in \mathrm {LS}_{n,p}$, the polynomials $L_{\mathcal {A}} := {\text {E}}_\gamma ^{-1} l_{\mathcal {A}}$ have the representation

$$\begin{aligned} L_{\mathcal {A}}(x,y) = w_{\mathcal {A}} \left( K_{n,p}^L(x,y; x_{\mathcal {A}},y_{\mathcal {A}}) - \frac{1}{2} \hat{T}_{2n}(y) \hat{T}_{2n}(y_\mathcal {A}) \right) \end{aligned}$$

(17)

and are the fundamental polynomials of Lagrange interpolation in the space $\Pi _{n,p}^L$ on the point set $\mathrm {LS}_{n,p}$, i.e.

$$\begin{aligned} L_{\mathcal {A}}(\mathcal {B}) = \delta _{\mathcal {A},\mathcal {B}}, \quad {\mathcal {A}}, \mathcal {B}\in \mathrm {LS}_{n,p}. \end{aligned}$$

The interpolation problem (13) has a unique solution in $\Pi _{n,p}^L$ and the interpolating polynomial $\mathcal {L}_{n,p} f$ is given by

$$\begin{aligned} \mathcal {L}_{n,p} f(x,y) = \sum _{\mathcal {A}\in \mathrm {LS}_{n,p}} f_\mathcal {A}L_\mathcal {A}(x,y). \end{aligned}$$

Proof

From the definition (16) of the trigonometric polynomials $l_{\mathcal {A}}$ and the mapping ${\text {E}}_\gamma$ it follows immediately that the polynomials $L_{\mathcal {A}} = {\text {E}}_\gamma ^{-1} l_{\mathcal {A}}$ satisfy $L_{\mathcal {A}}(\mathcal {B}) = \delta _{\mathcal {A},\mathcal {B}}$ for $\mathcal {B}\in \mathrm {LS}_{n,p}$. Moreover, since the trigonometric polynomials ${\{l_{\mathcal {A}}: \; \AA \in \mathrm {LS}_{n,p}\}}$ form a basis of the space $\Pi _{2n(n+p)}^{\mathrm {trig},L}$, Theorem 2 implies that the polynomials $\{L_{\mathcal {A}}: \; \mathcal {A}\in \mathrm {LS}_{n,p}\}$ form a basis of Lagrange polynomials for the space $\Pi _{n,p}^L$.

It remains to prove (17). To this end, we compute the decomposition of the polynomials $l_\mathcal {A}$ in the basis $e_{ij}$ given in (15) and use the inverse of the operator ${\text {E}}_\gamma$ to obtain (17). The proof will be given only for $\mathcal {A}\in \mathrm {LS}_{n,p}^{\mathrm {b}}$ having the representation

$$\begin{aligned} \mathcal {A}= (x_{\mathcal {A}}, y_{\mathcal {A}}) = \gamma _{n,p}\left( \frac{(2r+1)n + 2s (n+p) }{ 4 n (n+p)} 2\pi \right) = (-1)^{r+s} \left( z_{(2r+1)p}^{2(n+p)}, z_{2sp}^{2n} \right) . \end{aligned}$$

We first suppose that $\mathcal {A}\in \mathrm {LS}_{n,p}^{\mathrm {b}}$ is an interior point such that the two points $k,k' \in [\mathcal {A}] \cap [1,4n(n+p)]$, $k \ne k'$ that represent the same $\mathcal {A}$ are given as

$$\begin{aligned} k&= (2r+1) n + 2s (n+p) \; \mod \;4n(n+p),\\ k'&= (2r+1) n - 2s (n+p) \; \mod \;4n(n+p). \end{aligned}$$

Using simple trigonometric transformations, the basis function $l_\mathcal {A}$ can be written as

$$\begin{aligned} l_\mathcal {A}(t)= & {} D_{2n(n+p)}^k(t) + D_{2n(n+p)}^{k'}(t) \\= & {} \frac{2}{4n(n+p)} \left( 1 + \cos ((2r+1)n \pi ) \cos (2 n (n\!+\!p) t) \right. \\&+ \left. 2 \sum _{m=1}^{2n(n+p)-1} \textstyle \cos \left( \frac{2sm \pi }{2n}\right) \! \left( \cos \left( \frac{(2r+1)m\pi }{2(n+p)} \right) \cos (m t) + \sin \left( \frac{(2r+1)m\pi }{2(n+p)}\right) \sin (m t) \right) \!\! \right) \!. \end{aligned}$$

Now, using the explicit expression (15) of the basis polynomials $e_{ij}$ and comparing the coefficients in the decomposition of $l_\mathcal {A}$, we get the following formula for the inner product $\left\langle l_{\mathcal {A}}, e_{ij} \right\rangle = \frac{1}{2\pi } \int _0^{2\pi } l_{\mathcal {A}} (t) e_{ij} (t) \mathrm {d}t$, $(i,j) \in \Gamma _{n,p}^L$:

$$\begin{aligned} \left\langle l_{\mathcal {A}}, e_{ij} \right\rangle&= \left\{ \begin{array}{ll} \frac{2}{4n(n +p)}, &{} \text {if}\; (i,j) = (0,0), \\ \frac{\sqrt{2}}{4n(n +p)}, &{} \text {if}\;i = 0, j = 2n, \\ \frac{2 \sqrt{2}(-1)^{(r+s)j} }{4n(n +p)} \cos \left( j \frac{2s p \pi }{2n} \right) , &{} \text {if}\; i = 0, j < 2n, \\ \frac{2\sqrt{2}(- 1)^{(r+s)i} }{4n(n +p)} \cos \left( i \frac{(2r+1)p \pi }{2(n+p)} \right) , &{} \text {if}\; i \ne 0, j = 0,\\ \frac{4 (-1)^{(r+s)(i+j)}}{4n(n +p)} \cos \!\left( i \frac{(2r+1)p \pi }{2(n+p)} \! \right) \! \cos \! \left( j \frac{2s p \pi }{2n} \! \right) , \quad &{} \text {otherwise,} \end{array} \right. \\&=\frac{2}{4n(n\!+\!p)}\left\{ \begin{array}{ll} \frac{1}{2}\, \hat{T}_{2n}(y_\mathcal {A}), &{} \text {if}\; i = 0, j = 2n, \\ \hat{T}_{i}(x_{\mathcal {A}}) \hat{T}_j(y_\mathcal {A}),\quad &{} \text {if}\; (i,j) \in \Gamma _{n,p}^L {\setminus } (0,2n). \end{array} \right. \end{aligned}$$

Therefore, $l_\mathcal {A}(t)$ can be decomposed as

$$\begin{aligned} l_\mathcal {A}(t) = \frac{\hat{T}_{2n}(y_\mathcal {A})}{4n(n+p)} e_{0,2n}(t) + \!\!\!\!\!\! \sum _{\begin{array}{c} \;\;(i,j) \in \Gamma _{n,p}^L \\ j \ne 2n \end{array}} \!\!\!\!\!\! \frac{2 \hat{T}_{i}(x_\mathcal {A}) \hat{T}_j(y_\mathcal {A})}{4n(n+p)} e_{ij} (t). \end{aligned}$$

Now, using the inverse mapping ${\text {E}}_\gamma ^{-1}$ together with the definition of the reproducing kernel $K_{n,p}^L$, we can conclude:

$$\begin{aligned} L_\mathcal {A}(x,y) = {\text {E}}_\gamma ^{-1} l_\mathcal {A}(x,y) = w_\mathcal {A}\left( K_{n,p}^L(x,y; x_{\mathcal {A}}, y_\mathcal {A}) - \frac{1}{2} \hat{T}_{2n}(y) \hat{T}_{2n}(y_\mathcal {A}) \right) . \end{aligned}$$

If $\mathcal {A}\in \mathrm {LS}_{n,p}^{\mathrm {b}}$ is a point on the boundary of the square $[-1,1]^2$, the number k can be represented as $k = (2r+1)n$ and the basis function $l_\mathcal {A}$ is given as

$$\begin{aligned} l_\mathcal {A}(t)&= D_{2n(n+p)}^k(t) = \frac{1}{4n(n+p)} \left( 1 + \cos ((2r+1)n \pi ) \cos (2 n (n+p) t) \right. \\&\left. + \; 2 \!\! \!\!\!\! \sum _{m=1}^{2n(n+p)-1} \!\!\! \!\!\! \cos \left( \! \frac{2r+1}{2(n+p)} m \pi \! \right) \cos (m t) + \sin \left( \! \frac{2r+1}{2(n+p)} m \pi \!\right) \sin (m t) \! \right) . \end{aligned}$$

Now, similar calculations to the above yield (17) with the half sized weight function $w_{\mathcal {A}} = \frac{1}{4n(n+p)}$. Finally, for all points $\AA \in {\text {LS}}_{n,p}^{{\text {w}}}$, (17) can be obtained by analogous calculations using the representation (4) instead of (3). $\square$

Remark 3

(17) has a remarkable resemblence to the Lagrange polynomials of the Padua points. For the Padua points, the analog statement of Theorem 3 can be proved very elegantly by using ideal theory (cf. [5]). This approach was, however, not successful for the more general Lissajous nodes. Here, we had to use the isomorphism ${\text {E}}_\gamma$ and Theorem 2 instead.

5 A simple and efficient scheme for the computation of the interpolation polynomial

In view of Theorem 3, the solution to the interpolation problem (13) in $\Pi _{n,p}^L$ is given as

$$\begin{aligned} \mathcal {L}_{n,p} f(x,y) = \sum _{\mathcal {A}\in \mathrm {LS}_{n,p}} w_\mathcal {A}f_\mathcal {A}\left( K_{n,p}^L(x,y; x_{\mathcal {A}},y_\mathcal {A}) - \frac{1}{2} \hat{T}_{2n}(y) \hat{T}_{2n}(y_{\mathcal {A}}) \right) . \end{aligned}$$

The representation of the polynomial $\mathcal {L}_{n,p} f(x,y)$ in the orthonormal Chebyshev basis $\{ \hat{T}_i(x) \hat{T}_j(y):\; (i,j) \in \Gamma _{n,p}^L\}$ can now be written as

$$\begin{aligned} \mathcal {L}_{n,p} f(x,y) = \sum _{(i,j) \in \Gamma _{n,p}^L}\!\!\!\!\!\!\!c_{ij} \hat{T}_i(x) \hat{T}_j(y) \end{aligned}$$

with the coefficients $c_{ij} = \langle \mathcal {L}_{n,p} f, \hat{T}_i(x) \hat{T}_j(y) \rangle$ given by

$$\begin{aligned} c_{ij} = \left\{ \begin{array}{ll} \displaystyle \sum _{\mathcal {A}\in \mathrm {LS}_{n,p}}w_\mathcal {A}f_\mathcal {A}\, \hat{T}_i(x_\mathcal {A}) \hat{T}_j(y_\mathcal {A}),\; &{} \quad \text {if}\; (i,j) \in \Gamma _{n,p}^L \!{\setminus }\! (0,2n), \\ \displaystyle \frac{1}{2} \sum _{\mathcal {A}\in \mathrm {LS}_{n,p}} w_\mathcal {A}f_\mathcal {A}\, \hat{T}_{2n}(y_\mathcal {A}), &{} \quad \text {if} \; (i,j) = (0,2n). \\ \end{array} \right. \end{aligned}$$

(18)

Using the characterization of the points $\mathrm {LS}_{n,p}$ as the disjoint union of the sets (8) and (9), we can reformulate (18) in a more compact matrix notation. To this end, we introduce the coefficient matrix $\mathbf {C}_{n,p} = (c_{ij}) \in {\mathbb R}^{(2n+2p+1) \times (2n+1)}$ by

$$\begin{aligned} c_{ij} = \left\{ \begin{array}{ll} \langle \mathcal {L}_{n,p} f, \hat{T}_i(x) \hat{T}_j(y)\rangle ,\quad &{} \quad \text {if} \quad (i,j) \in \Gamma _{n,p}^L,\\ 0, &{}\quad \text {otherwise}, \end{array} \right. \end{aligned}$$

where $i = 0, \ldots , 2n+2p$ and $j = 0, \ldots , 2n$. The data values $f_\mathcal {A}$ and the weights $w_\mathcal {A}$ are collected in the extended data matrix $\mathbf {G}_{f} = (g_{ij}) \in {\mathbb R}^{(2n+2p+1) \times (2n+1)}$ given by

$$\begin{aligned} g_{ij} := \left\{ \begin{array}{ll} f_\mathcal {A}w_\mathcal {A}, \qquad &{} \text {if}\; \mathcal {A}= (z_i^{2n+2p}, z_j^{2n}) \in \mathrm {LS}_{n,p}, \\ 0 &{} \text {if}\; (z_i^{2n+2p}, z_j^{2n}) \notin \mathrm {LS}_{n,p}. \end{array} \right. \end{aligned}$$

Further, for a general finite set $\mathcal {X}= \{x_0, \ldots , x_m \} \subset [-1,1]$ of points, we define the matrices

$$\begin{aligned} \mathbf {T}_n(\mathcal {X})&:= \begin{pmatrix} \hat{T}_0(x_0) &{} \cdots &{} \hat{T}_0(x_m)\\ \vdots &{} \ddots &{} \vdots \\ \hat{T}_{n}(x_0 )&{} \cdots &{} \hat{T}_n(x_m) \end{pmatrix} \in {\mathbb R}^{(n+1) \times (m+1)}, \end{aligned}$$

and the sets $\mathcal {Z}_n = \{ z_0^n, z_1^n, \ldots , z_n^n \}$ of Chebyshev-Gauß-Lobatto points. Finally, we define the mask $\mathbf {M}_{n,p} = (m_{ij}) \in {\mathbb R}^{(2n+2p+1) \times (2n+1)}$ by

$$\begin{aligned} m_{ij} := \left\{ \begin{array}{ll} 1, &{} \text {if}\; (i,j) \in \Gamma _{n,p}^L {\setminus } (0,2n), \\ 1/2, \quad &{} \text {if}\; (i,j) = (0,2n),\\ 0, &{} \text {if}\; (i,j) \notin \Gamma _{n,p}^L. \end{array}\right. \end{aligned}$$

Then, the coefficient matrix $\mathbf {C}_{n,p}$ of the interpolating polynomial can be computed as

$$\begin{aligned} \mathbf {C}_{n,p} = \left( \mathbf {T}_{2n+2p}(\mathcal {Z}_{2n+2p}) \mathbf {G}_f \mathbf {T}_{2n}(\mathcal {Z}_{2n})^T \right) \odot \mathbf {M}_{n,p}, \end{aligned}$$

(19)

where $\odot$ denotes pointwise multiplication of the matrix entries. For an arbitrary point $\mathcal {A}=(x_{\mathcal {A}},y_\mathcal {A}) \subset {\mathbb R}^2$, the evaluation $\mathcal {L}_{n,p} f(\mathcal {A})$ of the interpolation polynomial is then given by

$$\begin{aligned} \mathcal {L}_{n,p} f(\mathcal {A}) = \mathbf {T}_{2n+2p}(x_\mathcal {A})^T \mathbf {C}_{n,p} \mathbf {T}_{2n}(y_\mathcal {A}). \end{aligned}$$

(20)

Due to the special structure of the matrices $\mathbf {T}_{2n+2p}(\mathcal {Z}_{2n+2p})$ and $\mathbf {T}_{2n}(\mathcal {Z}_{2n})$, the matrix-matrix evaluations in (19) can be computed efficiently using fast Fourier methods. For this purpose, we reformulate (19) for the single entries $c_{ij}$ of the matrix $\mathbf {C}_{n,p}$. Since the entries of the matrices $\mathbf {T}_{2n+2p}(\mathcal {Z}_{2n+2p})$ and $\mathbf {T}_{2n}(\mathcal {Z}_{2n})$ are Chebyshev polynomials evaluated at Chebyshev-Gauß-Lobatto points, we obtain the double cosine series

$$\begin{aligned} c_{ij} = m_{ij} \alpha _{ij} \sum _{l=0}^{2n} \left( \sum _{k=0}^{2n+2p} g_{kl} \cos \frac{i k \pi }{2n+2p} \right) \cos \frac{j l \pi }{2n} \end{aligned}$$

(21)

for the coefficients $c_{ij}$ with the normalization factors $\alpha _{ij} := \sqrt{2-\delta _{0,i}}\sqrt{2-\delta _{0,j}}$ of the Chebyshev polynomials. Therefore, the computation of the coefficients $c_{ij}$ can be performed by a composition of one-dimensional cosine transforms along the columns and the rows of the matrices $\mathbf {G}_f$ and $\mathbf {T}_{2n+2p}(\mathcal {Z}_{2n+2p}) \mathbf {G}_f$, respectively. Since

$$\begin{aligned} \sum _{k=0}^{2n+2p} g_{kl} \cos \frac{i k \pi }{2n+2p} = {\text {Re}}\left( \sum _{k=0}^{2n+2p} g_{kl}\, e^{-\imath \frac{2\pi i k}{4n+4p}} \right) ,\quad l = 0, \ldots , 2n, \end{aligned}$$

the single discrete cosine transforms can be executed efficiently by using a fast Fourier algorithm for the vectors $(g_{0,l}, \ldots , g_{2n+2p,l}, 0, \ldots , 0)^T \in {\mathbb R}^{4n+4p}$. The same scheme can be applied also for the discrete cosine transform of the rows of the matrix $\mathbf {T}_{2n+2p}(\mathcal {Z}_{2n+2p}) \mathbf {G}_f$. The corresponding implementation of formula (21) in Matlab/Octave code is given in Listing 1. The complexity of the algorithm is determined by the complexity of the fast Fourier transforms and is of order $\mathcal {O}\left( n (n+p) \ln (n (n+p))\right)$.

Remark 4

The matrix formulations in (19) and (20) are almost identical to the formulation of the interpolating scheme of the Padua points given in [6, 8]. Also, the fast algorithm for the computation of the coefficients $\mathbf {C}_{n,p}$ presented in Listing 1 is a modification of a respective algorithm developed for the Padua points in [6]. These structural similarities are due to the particular representation (17) of the Lagrange polynomials. The main difference between the two schemes lies in the form of the mask $\mathbf {M}_{n,p}$. The mask $\mathbf {M}_{n,p}$ for the points $\mathrm {LS}_{n,p}$ has an asymmetric structure determined by the index set $\Gamma _{n,p}^L$, whereas it is an upper left triangular matrix for the Padua points. Two examples of the structure of the index set $\Gamma _{n,p}^L$ are given in Fig. 3.

6 Numerical simulations

Based on the results derived in the last sections, we perform numerical simulations on the behaviour of the Lissajous points $\mathrm {LS}_{n,p}$ in comparison to some already established point sets. Unless explicitly mentioned, we assume $p=1$ for all numerical simulations of the Lissajous points. For the comparison point sets, our focus is on the Xu points (XU) [25] and the Padua points (PD) [7]. Based on the Chebyshev-Gauß-Lobatto points given by (5), and in correspondance to (8) and (9), the odd Xu points $\mathrm {XU}_{2n+1}$ are defined as the union of the sets

$$\begin{aligned} \text {XU}^{\mathrm {b}}_{2n+1}&= \left\{ (z^{2n+1}_{2i}, z^{2n+1}_{2j}):\; 0 \le i \le n,\; 0 \le j \le n\right\} , \\ \text {XU}^{\mathrm {w}}_{2n+1}&= \left\{ (z^{2n+1}_{2i+1}, z^{2n+1}_{2j+1}):\; 0 \le i \le n,\; 0 \le j \le n\right\} , \end{aligned}$$

with the cardinality $|\text {XU}_{2n+1}| = 2(n+1)^2$. In turn, the even Padua points $\mathrm {PD}_{2n}$ (2nd family) are defined as the union of the sets

$$\begin{aligned} \text {PD}^{\mathrm {b}}_{2n}&= \left\{ (z^{2n+1}_{2i+1}, z^{2n}_{2j}):\; 0 \le i \le n,\; 0 \le j \le n \right\} ,\end{aligned}$$

(22)

$$\begin{aligned} \text {PD}^{\mathrm {w}}_{2n}&= \left\{ (z^{2n+1}_{2i}, z^{2n}_{2j+1}):\; 0 \le i \le n,\; 0 \le j \le n-1 \right\} . \end{aligned}$$

(23)

The cardinality can be calculated as $|\text {PD}_{2n}| = (n+1)(2n+1)$. The distributions of the Lissajous, Xu and Padua points are shown for small degrees of n in Fig. 4. The point sets are introduced in such a way that an equally chosen n results in a similar cardinality.

Fig. 4

Visualizations of the Lissajous ($\mathrm {LS}$), Xu (XU) and Padua (PD) point sets. Point sets for $n=2$ (Left). Point sets for $n=5$ (Right)

The stability of the mapping $f \rightarrow \mathcal {L}_{n,p} f$ is evaluated by means of the growth of the Lebesgue constant. Here, we calculate the values of the Lebesgue constant

$$\begin{aligned} \Lambda ^{\text {LS}}_{n,p} = \max _{\mathcal {B}\in [-1,1]^2} \sum _{\mathcal {A}\in \mathrm {LS}_{n,p}} |L_\mathcal {A}(\mathcal {B})| \end{aligned}$$

of the Lissajous points up to a degree of $n=60$. We compare them with the least-squares fitting of the Lebesgue constant for the Padua and the Xu points. As shown in [7], it holds for the Padua points that ${\Lambda ^{\text {PD}}_{2n} = (\frac{2}{\pi } \log (2n + 1) + 1.1)^2}$ and as presented for the Xu points in [2] that ${\Lambda ^{\text {XU}}_{2n+1} = (\frac{2}{\pi } \log (2n + 2))^2}$. Figure 5a indicates that the asymptotic growth of $\Lambda ^{\mathrm {LS}}_{n,1}$ corresponds to the order $\mathcal O\left( \log ^2 n \right)$ of the Lebesgue constant $\Lambda ^{\mathrm {PD}}_{2n}$. In Fig. 5b it is shown, how a variation of the parameter p of the points $\mathrm {LS}_{n,p}$ changes the growth of the Lebesgue constant. Here, we consider $p=\{1,3,5,7\}$ and excluded each entry for n and p not being relatively prime. In total, these numerical evaluations foster the conjecture that the Lebesgue constant of the points $\mathrm {LS}_{n,p}$ is of the same order $\mathcal O\left( \log ^2 n \right)$ as the Lebesgue constant of the Padua and Xu points (see [4]).

Fig. 5

Lebesgue constants up to a degree of $n=60$ for the points $\mathrm {LS}_{n,p}$ in comparison to the least-squares fitting of the Lebesgue constant of the Xu and Padua points. $\mathrm{LS}_{n,1}$, $\mathrm{XU}_{2n+1}$ and $\mathrm{PD}_{2n}$ point sets (Left). Point sets $\mathrm{LS}_{n,p}$ for $p\in \{1,3,5,7\}$ (Right)

For a further evaluation of the points $\mathrm {LS}_{n,p}$, we perform numerical interpolations with the Xu, Padua and Lissajous points on the Franke-Renka-Brown test set [13, 24]. In order to simulate the Xu points as well as the Padua points, the numerical algorithms presented in [6, 9] are used. The maximum interpolation errors are computed on a uniform grid of $100\times 100$ points defined in a region $\Omega = \left[ 0,1\right] \times \left[ 0,1\right]$. As mentioned above, the degree n is defined to result in a similar total number of points, i.e. a similar cardinality. For our simulations we take $n \in \{5,10,20,30\}$. The results are shown in Tables 2, 3 and 4. It can be seen that the maximum interpolation error of all three point sets shows a similar behaviour in terms of degree n, with respect to the chosen test function. In terms of the point sets $\mathrm {LS}_{n,p}$, we evaluated the behaviour of p in addition to the aforementioned comparisons. We can state that the influence of varying p, with respect to the maximum interpolation error and the nodes used for the evaluation, is almost negligible.

Table 2 Interpolation errors for the points $\mathrm {LS}_{n,1}$

Table 3 Interpolation errors for the points $\mathrm {XU}_{2n+1}$

Table 4 Interpolation errors for the Padua points $\mathrm {PD}_{2n}$