Abstract
We obtain some new Shepard type operators based on the classical, the modified Shepard methods and the least squares thin plate spline function. Given some sets of points, we compute some representative subsets of knot points following an algorithm described by J. R. McMahon in 1986.
Authors
BabesBolyai University, Faculty of Mathematics and Computer Sciences
Keywords
Scattered data; Shepard operator; least squares approximation; thinplate spline; knot points.
Paper coordinates
Malina Andra, Catinas Teodora, Shepard operator of least squares thinplate spline type, Stud. Univ. BabesBolyai Math. 66(2021), No. 2, 257–265
http://doi.org/10.24193/subbmath.2021.2.02
About this paper
Print ISSN
02521938
Online ISSN
2065961X
MR
?
ZBL
?
Google Scholar
Paper (preprint) in HTML form
Shepard operator of least squares thinplate spline type
Abstract.
We obtain some new Shepard type operators based on the classical, the modified Shepard methods and the least squares thin plate spline function. Given some sets of points, we compute some representative subsets of knot points following an algorithm described by J. R. McMahon in 1986.
Key words and phrases:
Scattered data, Shepard operator, least squares approximation, thin plate spline, knot points.1991 Mathematics Subject Classification:
41A05, 41A25, 41A80.1. Preliminaries
One of the best suited methods for approximating large sets of data is the Shepard method, introduced in 1968 in [16]. It has the advantages of a small storage requirement and an easy generalization to additional independent variables, but it suffers from no good reproduction quality, low accuracy and a high computational cost relative to some alternative methods [15], these being the reasons for finding new methods that improve it (see, e.g.,[1][8], [17], [18]). In this paper we obtain some new operators based on the classical, the modified Shepard methods and the least squares thin plate spline.
Let $f$ be a realvalued function defined on $X\subset {\mathbb{R}}^{2},$ and $({x}_{i},{y}_{i})\in X,i=1,\mathrm{\dots},N$ some distinct points. Denote by ${r}_{i}(x,y)$ the distances between a given point $(x,y)\in X$ and the points $({x}_{i},{y}_{i}),i=1,\mathrm{\dots},N$. The bivariate Shepard operator is defined by
$$\left({S}_{\mu}f\right)(x,y)=\sum _{i=1}^{N}{A}_{i,\mu}(x,y)f({x}_{i},{y}_{i}),$$  (1.1) 
where
$${A}_{i,\mu}(x,y)=\frac{\prod _{\begin{array}{c}j=1\\ j\ne i\end{array}}^{N}{r}_{j}^{\mu}(x,y)}{\sum _{k=1}^{N}\prod _{\begin{array}{c}j=1\\ j\ne k\end{array}}^{N}{r}_{j}^{\mu}(x,y)},$$  (1.2) 
with the parameter $\mu >0.$
It is known that the bivariate Shepard operator ${S}_{\mu}$ reproduces only the constants and that the function ${S}_{\mu}f$ has flat spots in the neighborhood of all data points.
Franke and Nielson introduced in [10] a method for improving the accuracy in reproducing a surface with the bivariate Shepard approximation. This method has been further improved in [9], [14], [15], and it is given by:
$$\left(Sf\right)(x,y)=\frac{\sum _{i=1}^{N}{W}_{i}(x,y)f({x}_{i},{y}_{i})}{\sum _{i=1}^{N}{W}_{i}(x,y)},$$  (1.3) 
with
$${W}_{i}(x,y)={\left[\frac{{({R}_{w}{r}_{i})}_{+}}{{R}_{w}{r}_{i}}\right]}^{2},$$  (1.4) 
where ${R}_{w}$ is a radius of influence about the node $({x}_{i},{y}_{i})$ and it is varying with $i.$ ${R}_{w}$ is taken as the distance from node $i$ to the $j$th closest node to $({x}_{i},{y}_{i})$ for $j>{N}_{w}$ (${N}_{w}$ is a fixed value) and $j$ as small as possible within the constraint that the $j$th closest node is significantly more distant than the $(j1)$st closest node (see, e.g. [15]). As it is mentioned in [11], this modified Shepard method is one of the most powerful software tools for the multivariate approximation of large scattered data sets.
2. The Shepard operators of least squares thinplate spline type
Consider $f$ a realvalued function defined on $X\subset {\mathbb{R}}^{2},$ and $({x}_{i},{y}_{i})\in X,i=1,\mathrm{\dots},N$ some distinct points. We introduce the Shepard operator based on the least squares thinplate spline in four ways.
Method 1.
We consider
$$({S}_{1}f)(x,y)=\sum _{i=1}^{N}{A}_{i,\mu}(x,y){F}_{i}(x,y),$$  (2.1) 
where ${A}_{i,\mu},$ $i=1,\mathrm{\dots},N,$ are defined by (1.2), for a given parameter $\mu >0$ and the least squares thinplate splines are given by
$${F}_{i}(x,y)=\sum _{j=1}^{i}{C}_{j}{d}_{j}^{2}\mathrm{log}({d}_{j})+ax+by+c,i=1,\mathrm{\dots},N,$$  (2.2) 
with ${d}_{j}=\sqrt{{(x{x}_{j})}^{2}+{(y{y}_{j})}^{2}}.$
For the second way, we consider a smaller set of $k\in {\mathbb{N}}^{\ast}$ knot points $({\widehat{x}}_{j},{\widehat{y}}_{j}),$ $j=1,\mathrm{\dots},k$ that will be representative for the original set. This set is obtained following the next steps (see, e.g., [12] and [13]):
Algorithm 2.1.

1.
Generate $k$ random knot points, with $$;

2.
Assign to each point the closest knot point;

3.
If there exist knot points for which there is no point assigned, move the knot to the closest point;

4.
Compute the next set of knot points as the arithmetic mean of all corresponding points;

5.
Repeat steps 24 until the knot points do not change for two successive iterations.
Method 2.
For a given $k\in {\mathbb{N}}^{\ast}$, we consider the representative set of knot points $({\widehat{x}}_{j},{\widehat{y}}_{j}),$ $j=1,\mathrm{\dots},k$. The Shepard operator of least squares thinplate spline is given by
$$({S}_{2}f)(x,y)=\sum _{i=1}^{k}{A}_{i,\mu}(x,y){F}_{i}(x,y),$$  (2.3) 
where ${A}_{i,\mu},$ $i=1,\mathrm{\dots},k,$ are defined by
$${A}_{i,\mu}(x,y)=\frac{\prod _{\begin{array}{c}j=1\\ j\ne i\end{array}}^{k}{r}_{j}^{\mu}(x,y)}{\sum _{p=1}^{k}\prod _{\begin{array}{c}j=1\\ j\ne p\end{array}}^{k}{r}_{j}^{\mu}(x,y)},$$ 
for a given parameter $\mu >0$.
The least squares thinplate spline are given by
$${F}_{i}(x,y)=\sum _{j=1}^{i}{C}_{j}{d}_{j}^{2}\mathrm{log}({d}_{j})+ax+by+c,i=1,\mathrm{\dots},k,$$  (2.4) 
with ${d}_{j}=\sqrt{{(x{\widehat{x}}_{j})}^{2}+{(y{\widehat{y}}_{j})}^{2}}.$
For Methods 1 and 2, the coefficients ${C}_{j},$ $a,$ $b,$ $c$ of ${F}_{i}$ are found such that to minimize the expressions
$$E=\sum _{i=1}^{{N}^{\prime}}{[{F}_{i}({x}_{i},{y}_{i})f({x}_{i},{y}_{i})]}^{2},$$ 
considering ${N}^{\prime}=N$ for the first case and ${N}^{\prime}=k$ for the second one. There are obtained systems of the following form (see, e.g., [12]):
$$\left(\begin{array}{ccccccc}0& {d}_{12}^{2}\mathrm{log}{d}_{12}& \mathrm{\cdots}& {d}_{1{N}^{\prime}}^{2}\mathrm{log}{d}_{1{N}^{\prime}}& {x}_{1}& {y}_{1}& 1\\ {d}_{21}^{2}\mathrm{log}{d}_{21}& 0& \mathrm{\cdots}& {d}_{2{N}^{\prime}}^{2}\mathrm{log}{d}_{2{N}^{\prime}}& {x}_{2}& {y}_{2}& 1\\ \mathrm{\vdots}& \mathrm{\vdots}& \mathrm{\vdots}& \mathrm{\vdots}& \mathrm{\vdots}& \mathrm{\vdots}& \mathrm{\vdots}\\ {d}_{{N}^{\prime}1}^{2}\mathrm{log}{d}_{{N}^{\prime}1}& {d}_{{N}^{\prime}2}^{2}\mathrm{log}{d}_{{N}^{\prime}2}& \mathrm{\cdots}& 0& {x}_{{N}^{\prime}}& {y}_{{N}^{\prime}}& 1\\ {x}_{1}& {x}_{2}& \mathrm{\cdots}& {x}_{{N}^{\prime}}& 0& 0& 0\\ {y}_{1}& {y}_{2}& \mathrm{\cdots}& {y}_{{N}^{\prime}}& 0& 0& 0\\ 1& 1& \mathrm{\cdots}& 1& 0& 0& 0\end{array}\right)\cdot \left(\begin{array}{c}{C}_{1}\\ {C}_{2}\\ \mathrm{\vdots}\\ {C}_{{N}^{\prime}}\\ a\\ b\\ c\end{array}\right)=\left(\begin{array}{c}{f}_{1}\\ {f}_{2}\\ \mathrm{\vdots}\\ {f}_{{N}^{\prime}}\\ 0\\ 0\\ 0\end{array}\right)$$ 
with ${d}_{ij}^{2}={({x}_{i}{x}_{j})}^{2}+{({y}_{i}{y}_{j})}^{2}$, ${f}_{i}=f({x}_{i},{y}_{i}),i,j=1,\mathrm{\dots},{N}^{\prime}$.
Next we consider the improved form of the Shepard operator given in (1.3).
Method 3.
The coefficients ${C}_{j},$ $a,$ $b,$ $c$ of ${F}_{i},$ $i=1,\mathrm{\dots},N$ are determined in order to minimize the expression
$$E=\sum _{i=1}^{N}{[{F}_{i}({x}_{i},{y}_{i})f({x}_{i},{y}_{i})]}^{2}.$$ 
Method 4.
For a given $k\in {\mathbb{N}}^{\ast}$, we consider the representative set of knot points $({\widehat{x}}_{j},{\widehat{y}}_{j}),$ $j=1,\mathrm{\dots},k$, obtained applying the Algorithm 2.1. In this case, we introduce the Shepard operator of least squares thinplate spline type by the following formula:
$$({S}_{4}f)(x,y)=\frac{\sum _{i=1}^{k}{W}_{i}(x,y){F}_{i}(x,y)}{\sum _{i=1}^{k}{W}_{i}(x,y)},$$  (2.6) 
with ${W}_{i}$ given by (1.4) and ${F}_{i}$ given by (2.4), for $i=1,\mathrm{\dots},k$.
The coefficients ${C}_{j},$ $a,$ $b,$ $c$ of ${F}_{i}$, $i=1,\mathrm{\dots},k$ are determined in order to minimize the expression
$$E=\sum _{i=1}^{k}{[{F}_{i}({x}_{i},{y}_{i})f({x}_{i},{y}_{i})]}^{2}.$$ 
3. Numerical examples
We consider the following test functions (see, e.g., [9], [14], [15]):
$$\begin{array}{cc}\text{Gentle:}\hfill & {f}_{1}(x,y)=\mathrm{exp}[\frac{81}{16}({(x0.5)}^{2}+{(y0.5)}^{2})]/3,\hfill \\ \text{Saddle:}\hfill & {f}_{2}(x,y)=\frac{(1.25+\mathrm{cos}5.4y)}{6+6{(3x1)}^{2}},\hfill \\ \text{Sphere:}\hfill & {f}_{3}(x,y)=\sqrt{6481({(x0.5)}^{2}+{(y0.5)}^{2})}/90.5.\hfill \end{array}$$  (3.1) 
Table 1 contains the maximum errors for approximating the functions (3.1) by the classical and the modified Shepard operators given, respectively, by (1.1) and (1.3), and the errors of approximating by the operators introduced in (2.1), (2.3), (2.5) and (2.6). We consider three sets of $N=100$ random points for each function in $[0,1]\times [0,1]$, $k=25$ knots, $\mu =3$ and ${N}_{w}=19$.
Remark 3.1.
The approximants ${S}_{2}{f}_{i}$, ${S}_{4}{f}_{i}$, $i=1,2,3$ have better approximation properties although the number of knot points is smaller than the number of knot points considered for the approximants ${S}_{1}{f}_{i}$, ${S}_{3}{f}_{i}$ $i=1,2,3$, so this illustrates the benefits of the algorithm of choosing the representative set of points.
In Figures 2, 4, 6 we plot the graphs of ${f}_{1},{f}_{2},{f}_{3}$ and of the corresponding Shepard operators ${S}_{1}{f}_{i},{S}_{2}{f}_{i}$, ${S}_{3}{f}_{i}$ and ${S}_{4}{f}_{i}$, $i=1,2,3$, respectively.
In Figures 1, 3, 5 we plot the sets of the given points and the corresponding sets of the representative knot points.
${f}_{1}$  ${f}_{2}$  ${f}_{3}$  

${S}_{\mu}f$  0.0864  0.1095  0.1936 
$Sf$  0.0724  0.0970  0.1770 
${S}_{1}f$  0.1644  0.4001  0.6595 
${S}_{2}f$  0.1246  0.2858  0.3410 
${S}_{3}f$  0.1578  0.3783  0.6217 
${S}_{4}f$  0.1212  0.2834  0.3399 
References
 [1] Cătinaş, T., The combined ShepardAbelGoncharov univariate operator, Rev. Anal. Numér. Théor. Approx., 32(2003), pp. 11–20.
 [2] Cătinaş, T., The combined ShepardLidstone bivariate operator, In: de Bruin, M.G. et al. (eds.): Trends and Applications in Constructive Approximation. International Series of Numerical Mathematics, Springer GroupBirkhäuser Verlag, 151(2005), pp. 77–89.
 [3] Cătinaş, T., Bivariate interpolation by combined Shepard operators, Proceedings of ${17}^{th}$ IMACS World Congress, Scientific Computation, Applied Mathematics and Simulation, ISBN 2915913021, 2005, 7 pp.
 [4] Cătinaş, T., The bivariate Shepard operator of Bernoulli type, Calcolo, 44 (2007), no. 4, pp. 189202.
 [5] Coman, Gh., The remainder of certain Shepard type interpolation formulas, Studia UBB Math, 32 (1987), no. 4, pp. 2432.
 [6] Coman, Gh., Hermitetype Shepard operators, Rev. Anal. Numér. Théor. Approx., 26(1997), 33–38.
 [7] Coman, Gh., Shepard operators of Birkhoff type, Calcolo, 35(1998), pp. 197–203.
 [8] Farwig, R., Rate of convergence of Shepard’s global interpolation formula, Math. Comp., 46(1986), pp. 577–590.
 [9] Franke, R., Scattered data interpolation: tests of some methods, Math. Comp., 38(1982), pp. 181–200.
 [10] Franke, R., Nielson, G., Smooth interpolation of large sets of scattered data. Int. J. Numer. Meths. Engrg., 15(1980), pp. 1691–1704.
 [11] Lazzaro, D., Montefusco, L.B.: Radial basis functions for multivariate interpolation of large scattered data sets, J. Comput. Appl. Math., 140(2002), pp. 521–536.
 [12] McMahon, J. R., Knot selection for least squares approximation using thin plate splines, M.S. Thesis, Naval Postgraduate School, 1986.
 [13] McMahon, J. R., Franke, R., Knot selection for least squares thin plate splines, Technical Report, Naval Postgraduate School, Monterey, 1987.
 [14] Renka, R.J., Cline, A.K., A trianglebased ${C}^{1}$ interpolation method. Rocky Mountain J. Math., 14(1984), pp. 223–237.
 [15] Renka, R.J., Multivariate interpolation of large sets of scattered data ACM Trans. Math. Software, 14(1988), pp. 139–148.
 [16] Shepard, D., A two dimensional interpolation function for irregularly spaced data, Proc. 23rd Nat. Conf. ACM, 1968, pp. 517–523.
 [17] Trîmbiţaş, G., Combined Shepardleast squares operators  computing them using spatial data structures, Studia UBB Math, 47(2002), pp. 119–128.
 [18] Zuppa, C., Error estimates for moving least square approximations, Bull. Braz. Math. Soc., New Series 34(2), 2003, pp. 231249.
[2] Catinas, T., The combined ShepardLidstone bivariate operator, In: de Bruin, M.G. et al. (eds.): Trends and Applications in Constructive Approximation. International Series of Numerical Mathematics, Springer GroupBirkhauser Verlag, 151(2005), 7789.
[3] Catinas, T., Bivariate interpolation by combined Shepard operators, Proceedings of 17th IMACS World Congress, Scientific Computation, Applied Mathematics and Simulation, ISBN 2915913021, 2005, 7 pp.
[4] Catinas, T., The bivariate Shepard operator of Bernoulli type, Calcolo, 44 (2007), no. 4, 189202.
[5] Coman, Gh., The remainder of certain Shepard type interpolation formulas, Stud. Univ. BabesBolyai Math., 32(1987), no. 4, 2432.
[6] Coman, Gh., Hermitetype Shepard operators, Rev. Anal. Num´er. Th´eor. Approx.,
26(1997), 3338.
[7] Coman, Gh., Shepard operators of Birkhoff type, Calcolo, 35(1998), 197203.
[8] Farwig, R., Rate of convergence of Shepard’s global interpolation formula, Math. Comp., 46(1986), 577590.
[9] Franke, R., Scattered data interpolation: tests of some methods, Math. Comp., 38(1982), 181200.
[10] Franke, R., Nielson, G., Smooth interpolation of large sets of scattered data, Int. J. Numer. Meths. Engrg., 15(1980), 16911704.
[11] Lazzaro, D., Montefusco, L.B., Radial basis functions for multivariate interpolation of large scattered data sets, J. Comput. Appl. Math., 140(2002), 521536.
[12] McMahon, J.R., Knot selection for least squares approximation using thin plate splines, M.S. Thesis, Naval Postgraduate School, 1986.
[13] McMahon, J.R., Franke, R., Knot selection for least squares thin plate splines, Technical Report, Naval Postgraduate School, Monterey, 1987.
[14] Renka, R.J., Multivariate interpolation of large sets of scattered data, ACM Trans. Math. Software, 14(1988), 139148.
[15] Renka, R.J., Cline, A.K., A trianglebased C1 interpolation method, Rocky Mountain J. Math., 14(1984), 223237.
[16] Shepard, D., A two dimensional interpolation function for irregularly spaced data, Proc. 23rd Nat. Conf. ACM, 1968, 517523.
[17] Trımbitas, G., Combined Shepardleast squares operators – computing them using spatial data structures, Stud. Univ. BabesBolyai Math., 47(2002), 119128.
[18] Zuppa, C., Error estimates for moving least square approximations, Bull. Braz. Math. Soc., New Series, 34(2003), no. 2, 231249.