Numerical differentiation on scattered data through multivariate polynomial interpolation

Let \(\varPi _{d}\left( {\mathbb {R}}^{s}\right) \) be the space of polynomials of total degree at most d in the variable \({\mathbf {x}}=\left( \xi _{1},\dots ,\xi _{s}\right) \). A basis for this space, in the multi-index notation, is given by the monomials \({\mathbf {x}}^{\alpha }\mathbf { =}\xi _{1}^{\alpha _{1}}\dots \xi _{s}^{\alpha _{s}}\), where \(\alpha =\left( \alpha _{1},\dots ,\alpha _{s}\right) \in {\mathbb {N}} _{0}^{s}\), \(\left| \alpha \right| =\alpha _{1}+\dots +\alpha _{s}\le d\) and therefore \(\dim \varPi _{d}\left( {\mathbb {R}}^{s}\right) =\left( {\begin{array}{c} d+s\\ s\end{array}}\right) \). We introduce a total order in the set of all multi-indices \(\alpha \). More precisely, we assume \(\alpha <\beta \) if \(\left| \alpha \right| <\left| \beta \right| \), otherwise, if \(\left| \alpha \right| =\left| \beta \right| \) we follow the lexicographic order of the dictionary of words of \(\left| \alpha \right| \) letters from the ordered alphabet \(\left\{ \xi _{1},\dots ,\xi _{s}\right\} \) with the possibility to repeat each letter \(\xi _{i}\) only consecutively many times. For instance, if \(\left| \alpha \right| =3\) , we have \(\left( 3,0,0\right)<\left( 2,1,0\right)<\left( 2,0,1\right)<\left( 1,2,0\right)<\left( 1,1,1\right)<\left( 1,0,2\right)<\left( 0,3,0\right)<\left( 0,2,1\right)<\left( 0,1,2\right) <\left( 0,0,3\right) \) . Further details on multivariate polynomials and related multi-index notations can be found in [6, Ch. 4].

Let us consider a setof \(m=\left( {\begin{array}{c}d+s\\ s\end{array}}\right) \) pairwise distinct points in \( {\mathbb {R}} ^{s}\) and let us assume that they are unisolvent for Lagrange interpolation in \(\varPi _{d}\left( {\mathbb {R}}^{s}\right) \), that is for any choice of \( y_{1},\dots ,y_{m}\in {\mathbb {R}}\), there exists and it is unique \(p\in \varPi _{d}\left( {\mathbb {R}}^{s}\right) \) satisfyingAn equivalent result [6, Ch. 1] is the non singularity of the Vandermonde matrixwhere the index i, related to the points, varies along the rows while the index \(\alpha \), related to the powers, increases with the column index by following the above introduced order. By denoting with \(\overline{{\mathbf {x}}} \) any point in \({\mathbb {R}}^{s}\) and by fixing the basisthe Vandermonde matrix centered at \(\overline{{\mathbf {x}}}\)is non singular as well [6, Theorem 3, Ch. 5]. Therefore, for any choice of the vectorthe solution \(p\left[ {\mathbf {y}},\sigma \right] \left( {\mathbf {x}}\right) \) of the interpolation problem (2) in the basis (3), can be obtained by solving the linear systemand by setting, using matrix notation,where \({\mathbf {c}}=\left[ c_{\alpha }\right] _{\left| \alpha \right| \le d}^{T}\in {\mathbb {R}}^{m}\) is the solution of the system (6). This approach, for \(s=2\) and \(\overline{{\mathbf {x}}}\) the barycenter of the node set \(\sigma \), has been recently proposed in [12] in connection with the use of the \(PA=LU\) factorization of the matrix \(V_{\overline{{\mathbf {x}}}}\left( \sigma \right) \).

The main goal of the paper is to provide a pointwise numerical differentiation method of a target function f sampled at scattered points, by locally using the interpolation formula (7). The key tools are the connection to Taylor’s formula via the shifted monomial basis (3), suitably preconditioned by local scaling to reduce the conditioning of the Vandermonde matrix, together with the extraction of Leja-like local interpolation subsets from the scattered sampling set via basic numerical linear algebra. Our approach is complementary to other existing techniques, based on least-square approximation or on different function spaces, see for example [2, 7, 8, 16] and the references cited therein. In Sect. 2 we provide error bounds in approximating function and derivative values at a given point \(\overline{{\mathbf {x}}}\), as well as sensitivity estimates to perturbations of the function values, and in Sect. 3 we conduct some numerical experiments to show the accuracy of the proposed method.

In the following we assume that \(\varOmega \subset {\mathbb {R}} ^{s}\) is a convex body containing \(\sigma \) and that the sampled function \( f:\varOmega \) \(\rightarrow {\mathbb {R}} \) is of class \(C^{d,1}\left( \varOmega \right) \), that is \(f\in C^{d}\left( \varOmega \right) \) and all its partial derivatives of order dare Lipschitz continuous in \(\varOmega \). Let \(K\subseteq \varOmega \) compact convex: we equip the space \(C^{d,1}\left( K \right) \) with the semi-norm [13]and we denote by \(T_{d}\left[ f,\overline{{\mathbf {x}}}\right] \left( \mathbf {x }\right) \) the truncated Taylor expansion of f of order d centered at \( \overline{{\mathbf {x}}}\in \varOmega \)and by \(R_{T}\left[ f,\overline{{\mathbf {x}}}\right] \left( {\mathbf {x}}\right) \) the corresponding remainder term in integral form [19]where [6, Ch. 4]with the multi-indices \(\beta \) following the order specified in Sect. 1.Let us denote by \(\ell _{i}\left( {\mathbf {x}}\right) \) the \(i^{th}\) bivariate fundamental Lagrange polynomial. Sinceby setting for each \(i=1,\dots ,m,\)and by solving the linear system \(V_{\overline{{\mathbf {x}}}}\left( \sigma \right) {\mathbf {a}}^{i}=\delta ^{i}\), we get the expression of \(\ell _{i}\left( {\mathbf {x}}\right) \) in the translated canonical basis (3), that iswhere \({\mathbf {a}}^{i}=\left[ a_{\alpha }^{i}\right] _{\left| \alpha \right| \le d}^{T}\).

In the following we denote by \(V_{\overline{{\mathbf {x}}},h}(\sigma )\) the Vandermonde matrix in the scaled basis (15)and by \(B_{h}\left( \mathbf {\overline{{\mathbf {x}}}}\right) \) the ball of radius h centered at \(\mathbf {\overline{{\mathbf {x}}}}\).

The estimates in Proposition 1 can be written in terms of the Lebesgue constant of interpolation at the node set \(\sigma \), defined by

It is worth noting that the analysis developed in [14] in connection with the estimation of the error of Hermite interpolation in \({\mathbb {R}}^{s}\) can be used to obtain analogous bounds with respect to those obtained in (31) and (32). To do this, in line with [14], given an integer \(l\in {\mathbb {N}}\), we denote with \(D^{l}f\left( {\mathbf {x}}\right) \) the l-th derivative of f in a point \( {\mathbf {x}}\in \varOmega \), that is the l linear operatorwhich acts on the canonical basis element \(\underset{\nu {_{1}\text { times}}}{(\underbrace{{\mathbf {e}}_{1},\dots ,{\mathbf {e}}_{1}}},\underset{\nu _{2}\text { times}}{\underbrace{{\mathbf {e}}_{2},\dots ,{\mathbf {e}}_{2}}},\dots ,\underset{ \nu {_{s}\text { times}}}{\underbrace{{\mathbf {e}}_{s},\dots ,{\mathbf {e}}_{s}}})\) , \(\nu =\left( \nu _{1},\nu _{2},\dots ,\nu _{s}\right) \in {\mathbb {N}} _{0}^{s}\), \(\left| \nu \right| =l\), as followswhere we use the previously introduced notations for partial derivatives (8). As an l linear operator, the norm of \( D^{l}f\left( {\mathbf {x}}\right) \) is defined in a standard way as followsand therefore, for each \(\nu \in {\mathbb {N}}_{0}^{s}\), \(\left| \nu \right| =l\), we haveBy introducing the Sobolev semi-normwhich is meaningful for functions \(f\in W^{d+1,p}\left( \varOmega \right) \) for each \(d+1\ge l\), from [14, Theorem 2.1] by taking \( p=+\infty \), we get using (38)for any \(\overline{{\mathbf {x}}}\in \varOmega ,\) \(\mathbf {x\in }K\mathbf {=} B_{h}\left( \overline{{\mathbf {x}}}\right) \cap \varOmega \) and for any multi-index \(\nu \) of length \(\left| \nu \right| =l\le d\). In order to point out links between proof of Proposition 3 and that one given in [14, Theorem 2.1], we start with the inequalitywhich is already stated in the paper [14, Page 414, line 9] for the general case of Hermite interpolation. By the linearity of the operator \(D^{l}\) with respect to the function argument, we get by using the expression (16) of Lagrange polynomialsWe can explicitly compute the expression of \(D^{l}\left( {\mathbf {x}}- \overline{{\mathbf {x}}}\right) ^{\alpha }\) when applied to a vector \(\left( {\mathbf {u}}_{1},\dots ,{\mathbf {u}}_{l}\right) \in \left( {\mathbb {R}} ^{s}\right) ^{l}\). In order to simplify the notations, in line with [14, Section 2], we assume thatand, denoting with \(\left\{ \varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{s}\right\} \) the canonical basis of \( {\mathbb {R}} ^{s}\), we setandThereforeUsing (40) and (41), we get From the bound (39), the equality (42) and by recalling that [13, Lemma 2.1]we obtainwhich is a slight different version of the bound (31) given in Proposition 3. In order to have an analogous version of the bound (32), we evaluate at \( \overline{{\mathbf {x}}}\) the estimation (43), and consequently we get We notice that the s-tuple \(\varepsilon _{\lambda ,l}\) in the internal sum depends on \(\alpha \), but its length is equal to \(l\le d\) and therefore we getIt is easy to see that, despite the bounds (32) and (45) are similar, their comparison depends on the sign of the coefficients \(a_{\alpha ,h}^{i}\), \(\left| \alpha \right| =l\), since the sum \(\sum \limits _{\left| \alpha \right| =l}\alpha !a_{\alpha ,h}^{i}\) contains the term \(\nu !a_{\nu ,h}^{i}\).

In line with [12] we can write the bounds (31) and (32) in Proposition 3 in terms of the 1-norm condition number, say \( {{\,\mathrm{cond}\,}}_h\left( \sigma \right) \), of the Vandermonde matrix \(V_{\overline{\mathbf { x}},h}\left( \sigma \right) \).

The results of Table 1 in Sect. 3 show that the bounds (27) and (47) are much larger than (32), which is only based on the “active coefficients” in the differentiation process. Therefore, in the analysis of the sensitivity to the perturbation of the function values, we use only the “active coefficients”.

In this section we provide some numerical tests to support the above theoretical results in approximating function, gradient and second order derivative values. We fix \(s=2\), \(\varOmega =[0,1]^2\) and we take different positions for the point \(\overline{{\mathbf {x}}}\) in \(\varOmega \): at the center, and near/on a side and a corner of the square. We use different distributions of scattered points in \(\varOmega \), namely Halton points [15] and uniform random points. We focus on the scattered points in the ball \(B_r(\overline{{\mathbf {x}}})\) centered at \( \overline{{\mathbf {x}}}\) for different radii, from which we extract an interpolation subset \(\sigma \) of \(m=\left( {\begin{array}{c}d+2\\ 2\end{array}}\right) \) Discrete Leja Points computed through the algorithm proposed in [3] (see Fig. 1).

The reason for adopting Discrete Leja Points is twofold. We recall that they are extracted from a finite set of points (in this case the scattered points in the ball) by LU factorization with row pivoting of the corresponding rectangular Vandermonde matrix. Indeed, Gaussian elimination with row pivoting performs a sort of greedy optimization of the Vandermonde determinant, by searching iteratively the new row (that is selecting the new interpolation point) in such a way that the modulus of the augmented determinant is maximized. In addition, if the polynomial basis is lexicographically ordered, the Discrete Leja Points form a sequence, that is the first \({\left( {\begin{array}{c}k+s\\ s\end{array}}\right) }\) are the Discrete Leja Points for interpolation of degree k in s variables, \(1\le k\le d\); see [3] for a comprehensive discussion.

Then, on one hand Discrete Leja Points provide, with a low computational cost, a unisolvent interpolation set, since a nonzero Vandermonde determinant is automatically seeked. On the other hand, since they are computed by a greedy maximization, one can expect, as a qualitative guideline, that the elements of the corresponding inverse Vandermonde matrix (that are cofactors divided by the Vandermonde determinant), and thus also the relevant sum in the error bound (32) as well as the condition number, are not allowed to increase rapidly. These results are in line with those shown in [12, Table 1]. In addition, using Discrete Leja Points has also the effect of trying to minimize the sup-norm of the fundamental Lagrange polynomials \(\ell _i\) (which, as it is well-known, can be written as ratio of determinants, cf. [3]) and thus the Lebesgue constant, which is relevant to estimate (27). Nevertheless, it is clear from Table 1 that the bounds involving the Lebesgue constant and the condition number are much larger than (32) which rests only on the “active coefficients” in the differentiation process. Further numerical experiments show that, while decreasing r, for each value of \( \left| \nu \right| \), the first and third rows in Table 1 remain of the same order of magnitude thanks to the scaling of the basis, for the feasible degrees (since unisolvence of interpolation of degree d is possible until there are enough scattered points in the ball).

For simplicity, from now on we setand, to measure the error of approximation, we compute the relative errorsandusing the following bivariate test functions where \(f_{1}\) is the well known Franke’s function and \(f_{3}\) is an oscillating function (see Fig. 6) both in Renka’s test set [17], whereas \(f_{2}\) is obtained by a superposition of the univariate exponential with an inner product and then is constant on the parallel hyperplanes \(x+y=q\), \(q\in {\mathbb {R}}\) (ridge function). For each test function we approximate \(D^{\nu }f\left( \overline{ {\mathbf {x}}}\right) \) bywhere \(c_{\nu ,h}\), with \(h\le r\) defined in (14), are the coefficients of the interpolating polynomial (17 ) at the point \(\overline{{\mathbf {x}}}\). Interpolation is made at Discrete Leja Points in \(B_r(\overline{{\mathbf {x}}})\) for \(r=\frac{1}{2},\frac{3}{8}, \frac{1}{4},\frac{1}{8}\) at a sequence of degrees d. We stress that for a fixed radius r, unisolvence of interpolation is possible only for a finite number of degrees, that is until there are enough scattered points in the ball.

In the first experiment we start from 1000, 2000 and 4000 Halton and uniform random points and we set \(\overline{{\mathbf {x}}}=\left( 0.5,0.5\right) \) (see Fig. 1). For the test function \(f_{1}\), the numerical results are displayed in Figs. 2, 3.

In the second experiment, we start from 2000 Halton points for the test function \(f_2\), again with \(\overline{{\mathbf {x}}}=\left( 0.5,0.5\right) \). The numerical results are displayed in Fig. 4.

In the third experiment, for the test function \(f_3\), we start from 4000 Halton points choosing \(\overline{{\mathbf {x}}}\) at the center, then close to the right side and finally close to the north-east corner (see Figures 5, 6). The numerical results are displayed in Figs. 7, 8 and 10. We repeat the same experiments choosing \(\overline{{\mathbf {x}}}\) on the right side and at the north-east corner and we report the results in Figs. 9 and 11.

In the last experiment, for each test function \(f_{k}\), \(k=1,2,3\), we include a random noise in the m function values, namelywhere \(U(-\varepsilon ,\varepsilon )\) denotes the multivariate uniform distribution in \([-\varepsilon ,\varepsilon ]^{m}\). In Figure 12 we display the relative errorfor the gradient at \(\overline{{\mathbf {x}}}=\left( 0.5,0.5\right) \), computed using 1000 Halton points with exact function values (55) and perturbed function values (59) for \( \varepsilon =10^{-6}\). In Figure 13 we display the relative sensitivity in computing the gradient of the interpolating polynomial p under the perturbation of the function values (\( \varepsilon =10^{-6}\))together with its estimate involving the stability constant of the gradient (51)Notice that the relative errors gep in Fig. 12 and sensitivity gs in Fig. 13 are of the same order of magnitude when the errors ge become negligible with respect to gs. Moreover, gse turns out to be a slight overestimate of the relative sensitivity gs. This fact, as we can see in Table 2 where \(\overline{{\mathbf {x}}}=(0.5,0.5)\), is due to the relative small values of the stability constant that varies slowly while decreasing the radius r or increasing the degree of the interpolating polynomial.

Finally, it is worth stressing that the stability constant (51) is a function of \(\overline{{\mathbf {x}}}\) and then it depends on the position of \(\overline{{\mathbf {x}}}\) in the square. More precisely, for a fixed interpolation degree d, it slowly varies except for a neighborhood of the boundary where it increases rapidly, expecially near the vertices, as can be observed in Fig. 14, where for clarity we restrict the stability constant to lines. On the other hand, it can be noticed that by increasing the degree, the stability constant tends to increase, much more rapidly at the boundary. Such a behavior, that explains the worsening of the accuracy at the boundary (see Figs. 8–9) and at the vertex (see Figs. 10–11) of the square, can be ascribed to the fact that the stability functions (52) increase rapidly near the boundary of the local interpolation domains \(B_h(\overline{ {\mathbf {x}}}) \cap \varOmega \). This phenomenon, that resembles the behavior at the boundary of Lebesgue functions of univariate interpolation at equispaced points (cf. e.g. [18]), is worth of further investigation.

We stress that our method is not restricted to dimension 2. Indeed, in Figs. 15–16 we show the accuracy of derivative approximation for the 3D version of the function \(f_2\) by using 10000 Halton and uniform random points, respectively. The error behaviour is quite similar to the 2D case with Halton points (see Fig. 4). Notice that for the smallest radius the maximum interpolation degree is smaller than the 2D case since there are not enough interpolation points in the ball (to reach the same maximum degree we would need around 56000 points).