Univariate Shepard operators combined with least squares fitting polynomials

Andra Malina andra.malina@ubbcluj.ro Babeş-Bolyai University, Faculty of Mathematics and Computer Science & Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, Cluj-Napoca, Romania

Abstract

We obtain new univariate Shepard operators using polynomials that are constructed such that they fit the interpolation data in a weighted least squares approximation way. We study the degree of exactness, the linearity and the remainder for the corresponding interpolation formula.

1 Introduction

D. Shepard introduced in 1968 in [13] a very powerful method for approximating a given function $f$ on a set of scattered data, method that nowadays is named after him. The procedure has an easy implementation and it is expressed as a combination between some basis functions and the values of the function $f$ on a given set of interpolation nodes. However, two of its major drawbacks are the high computational cost and the low degree of exactness. Several authors have studied them and proposed different solutions to overcome them, such as modifying the basis functions or combining the Shepard operator with other interpolation operators for an increased degree of exactness (see, e.g., [1]; [2]; [3]; [4]; [5]; [6]; [7]; [8]; [9]; [10]).

In the univariate case, when $f$ is a real-valued function defined on a subset $X$ of $\mathbb{R}$ , for a given set of $K$ interpolation nodes, $x_{i}\in X,\;i=1,...,K$ , the Shepard operator is defined as

S_{\mu}f(x)=\sum\limits_{i=1}^{K}A_{i,\mu}(x)\cdot f(x_{i}),

(1)

with the basis functions $A_{i,\mu}$ given by

A_{i,\mu}(x)=\frac{\left|x-x_{i}\right|^{-\mu}}{\sum\limits_{j=1}^{K}\left|x-x% _{j}\right|^{-\mu}},\;\;\;\;i=1,...,K,\;x_{i}\neq x_{j},\;\mbox{for }i\neq j,% \;j=1,...,K,

(2)

$x\in X$ and $\mu>0$ an arbitrary parameter.

This paper focuses on introducing a new univariate Shepard operator, combined with polynomials constructed based on the least squares approach. In Section 2, after we construct these polynomials, we study several properties of them and of the combined Shepard operators (interpolation property, degree of exactness, linearity). Finally, we study the errors, based on Peano’s Theorem. Section 3 is dedicated to numerical examples that show the benefits of these Shepard operators.

2 Shepard operators combined with polynomials constructed by the least squares method

R. J. Renka introduced in 1988 in [11] an algorithm for improving the bivariate Shepard operator, considering a quadratic polynomial that interpolates the function $f$ on a set of given nodes and also approximates the data in a weighted least squares way. Later on, in 1999 in [12] he improved this method by replacing the quadratic polynomial with a cubic one. In 2010 in [14], W. I. Thacker et al. emphasized the main disadvantages of these two methods and suggested the combination of the Shepard operator with a linear polynomial that still fits the data in a weighted least squares sense.

Using some ideas for the bivariate case presented in the above mentioned papers, we are going to consider an improvement for the classical Shepard operator in the univariate case, by combining it with polynomials of degree $n,\;n\in\mathbb{N}$ , constructed following the weighted least squares approximation technique.

Consider $X\subset\mathbb{R}$ , $f:X\to\mathbb{R}$ and $K$ given real nodes, denoted by $x_{j}$ , $j=1,...,K$ . The values of the function $f$ on the given nodes are known and denoted by $f_{j}=f(x_{j}),\;j=1,...,K$ .

Under these assumptions, for a point $x\in X$ , let us define the $n$ th degree polynomial function $C_{j}^{n}[f]$ , $j=1,...,K$ , $n\in\mathbb{N}$ , as

C_{j}^{n}[f](x)=f_{j}+\sum\limits_{k=1}^{n}a_{j,k}(x-x_{j})^{k},

(3)

where the coefficients $a_{j,k}$ are found such that they minimize the sum of the weighted squared residuals

E_{j}=\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\left[C_{j}^{n}[f](x_{i})-f_{i}\right]^% {2},

(4)

where

\lambda_{i,j}=\frac{\left|x_{i}-x_{j}\right|^{-\mu}}{\sum\limits_{\begin{% subarray}{c}k=1\\ k\neq i\end{subarray}}^{K}\left|x_{i}-x_{k}\right|^{-\mu}},

(5)

for $i,j=1,...,K$ and $\mu>0$ .

In order to find the coefficients $a_{j,k}$ (i.e, obtain the minimum of expression (4)), we follow the weighted least squares reasoning, take the partial derivatives of $E_{j}$ with respect to each unknown, set them to zero and solve the resulting system:

\frac{\partial E_{j}}{\partial a_{j,k}}=0,\mbox{ for each }k=1,...,n\mbox{ and% }j=1,...,K.

Further, for every $j=1,...,K$ one obtains

\frac{\partial E_{j}}{\partial a_{j,k}}=2\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\left[\sum\limits_{p=1}^{n}a_{j,p}(x_{i% }-x_{j})^{p}+(f_{j}-f_{i})\right]\cdot(x_{i}-x_{j})^{k}=0,\mbox{ for each }k=1% ,...,n.

Let us make the notation

x_{i,j}^{p}=\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\cdot(x_{i}-x_{j})^{p}.

Then, the system of normal equations that has to be solved in order to find the coefficients $a_{j,k},\;k=1,...,n,$ has the form

\left\{\begin{aligned} a_{j,1}x_{i,j}^{2}+a_{j,2}x_{i,j}^{3}+...+&a_{j,n}x_{i,% j}^{n+1}=\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\cdot(x_{i}-x_{j})\cdot(f_{i}-f_{j})\\ ...\\ a_{j,1}x_{i,j}^{k+1}+a_{j,2}x_{i,j}^{k+2}+...+&a_{j,n}x_{i,j}^{k+n}=\sum% \limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\cdot(x_{i}-x_{j})^{k}\cdot(f_{i}-f_{j}% )\\ ...\\ a_{j,1}x_{i,j}^{n+1}+a_{j,2}x_{i,j}^{n+2}+...+&a_{j,n}x_{i,j}^{2n}=\sum\limits% _{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\cdot(x_{i}-x_{j})^{n}\cdot(f_{i}-f_{j}% ),\\ \end{aligned}\right.

(6)

for each $j=1,...,K$ .

For every $j=1,...,K,$ we can write the normal equations that appear above in a matricial form as

M_{j}\cdot a_{j}=b_{j},

(7)

where $M_{j}$ is a $n\times n$ matrix having on the entry $(r,s)$ the element $\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\cdot(x_{i}-x_{j})^{r+s}$ , $b_{j}$ is a vector of $n$ elements with $\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\cdot(x_{i}-x_{j})^{k}\cdot(f_{i}-f_{j})$ on the $k$ th entry and $a_{j}=\left(a_{j,1},\;a_{j,2},\;...,a_{j,n}\right)^{T}$ is the vector of unknowns.

Theorem 2.1

The operator $C_{j}^{n}[f]$ defined in (3) satisfies the following interpolation property

C_{j}^{n}[f](x_{j})=f_{j},\;j=1,...,K.

Proof 2.2.

For any $j=1,...,K$ , one has

C_{j}^{n}[f](x_{j})=f_{j}+\sum\limits_{k=1}^{n}a_{j,k}(x_{j}-x_{j})^{k}=f_{j}.

Theorem 2.3.

The operator $C_{j}^{n}[f],\;j=1,...,K$ , has the degree of exactness n, i.e.,

{\rm dex}(C_{j}^{n}[f])=n,\;j=1,...,K,

where ” ${\rm dex}$ ” denotes the degree of exactness.

Proof 2.4.

For $x\in X$ we have the following cases for $C_{j}^{n}[f],\;j=1,...,K$ :

Case 1.

$f(x)=e_{0}(x)=x^{0}$ . We get $a_{j,k}=0$ , $k=1,...,n,$ and obviously

$C_{j}^{n}[e_{0}](x)=e_{0}(x_{j})+0\cdot\sum\limits_{k=1}^{n}(x-x_{j})^{k}=1=e_% {0}(x).$

Case 2.

$f(x)=e_{n}(x)=x^{n}$ . We obtain the following solution for the coefficients $a_{j,k}$ :

a_{j,k}={{n}\choose{n-k}}x_{j}^{n-k},\;k=1,...,n

(8)

and

	$\displaystyle C_{j}^{n}[e_{n}](x)$	$\displaystyle=e_{n}(x_{j})+\sum\limits_{k=1}^{n}{{n}\choose{n-k}}x_{j}^{n-k}(x% -x_{j})^{k}$
		$\displaystyle={{n}\choose{n}}x_{j}^{n-0}(x-x_{j})^{0}+\sum\limits_{k=1}^{n}{{n% }\choose{n-k}}x_{j}^{n-k}(x-x_{j})^{k}$
		$\displaystyle=\sum\limits_{k=0}^{n}{{n}\choose{k}}x_{j}^{n-k}(x-x_{j})^{k}=(x_% {j}+x-x_{j})^{n}=x^{n}=e_{n}(x).$

Case 3.

$f(x)=e_{p}(x),\;p=1,...,n-1$ . In this situation we have

$a_{j,r}={{p}\choose{p-r}}x_{j}^{p-r}\mbox{ for }r=1,...,p\mbox{ and }a_{j,s}=0% \mbox{ for }s=p+1,...,n$

and

$C_{j}^{n}[e_{p}](x)=e_{p}(x_{j})+\sum\limits_{r=1}^{p}{{p}\choose{p-r}}x_{j}^{% p-r}(x-x_{j})^{r}=x^{p}=e_{p}(x).$
Case 4.

$f(x)=e_{n+1}(x)$ . It is obvious that $C_{j}^{n}[e_{n+1}](x)\neq x^{n+1}$ since

$C_{j}^{n}[e_{n+1}](x)=e_{n+1}(x_{j})+\sum\limits_{k=1}^{n}a_{j,k}(x-x_{j})^{k}$

and no term $x^{n+1}$ appears.

In conclusion, ${\rm dex}(C_{j}^{n}[f])=n,\;j=1,...,K$ .

Theorem 2.5.

The operator $C_{j}^{n}[f]$ is linear.

Proof 2.6.

We have to show that for $g_{1},\;g_{2}:X\to\mathbb{R}$ , arbitrarily chosen, and $\alpha,\;\beta\in\mathbb{R}$ , one has for $x\in X$ :

C_{j}^{n}[\alpha g_{1}+\beta g_{2}](x)=\alpha C_{j}^{n}[g_{1}](x)+\beta C_{j}^% {n}[g_{2}](x),\;j=1,...,K.

(9)

Let us define the terms that appear in (9):

	$\displaystyle C_{j}^{n}[g_{1}](x)$	$\displaystyle=g_{1}(x_{j})+\sum\limits_{k=1}^{n}a_{j,k}^{\prime}(x-x_{j})^{k},% \;j=1,...,K,$
	$\displaystyle C_{j}^{n}[g_{2}](x)$	$\displaystyle=g_{2}(x_{j})+\sum\limits_{k=1}^{n}a_{j,k}^{\prime\prime}(x-x_{j}% )^{k},\;j=1,...,K,$
	$\displaystyle C_{j}^{n}[\alpha g_{1}+\beta g_{2}](x)$	$\displaystyle=(\alpha g_{1}+\beta g_{2})(x_{j})+\sum\limits_{k=1}^{n}a_{j,k}(x% -x_{j})^{k}$
		$\displaystyle=\alpha g_{1}(x_{j})+\beta g_{2}(x_{j})+\sum\limits_{k=1}^{n}a_{j% ,k}(x-x_{j})^{k},\;j=1,...,K.$

By solving similar systems as in (6), we obtain the following relation between the coefficients that appear above

a_{j,k}=\alpha a_{j,k}^{\prime}+\beta a_{j,k}^{\prime\prime},\mbox{ for every % }k=1,...,n\mbox{ and }j=1,...,K.

Now, one has

	$\displaystyle C_{j}^{n}[\alpha g_{1}+\beta g_{2}](x)$	$\displaystyle=\alpha g_{1}(x_{j})+\beta g_{2}(x_{j})+\sum\limits_{k=1}^{n}(% \alpha a_{j,k}^{\prime}+\beta a_{j,k}^{\prime\prime})(x-x_{j})^{k}$
		$\displaystyle=\alpha\left[g_{1}(x_{j})+\sum\limits_{k=1}^{n}a_{j,k}^{\prime}(x% -x_{j})^{k}\right]+\beta\left[g_{2}(x_{j})+\sum\limits_{k=1}^{n}a_{j,k}^{% \prime\prime}(x-x_{j})^{k}\right]$
		$\displaystyle=\alpha C_{j}^{n}[g_{1}](x)+\beta C_{j}^{n}[g_{2}](x),\;j=1,...,K,$

and so (9) is proved.

Definition 2.7.

For $f:X\to\mathbb{R}$ and the set of $K$ interpolation nodes, using the $n$ th degree polynomial given in (3), we can define the univariate Shepard operator combined with a $n$ th degree polynomial as

SP_{n}[f](x)=\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot C_{j}^{n}[f](x),

(10)

with $A_{j,\mu}$ defined in (2) using the given parameter $\mu>0$ .

Theorem 2.8.

The following interpolation property holds

SP_{n}[f](x_{j})=f(x_{j}),\;\;j=1,...,K.

Proof 2.9.

It follows from Theorem 2.1 and the fact that for $A_{j,\mu}$ given in (2), we have $A_{j,\mu}(x_{i})=\delta_{ij}$ , where

\delta_{ij}=\left\{\begin{aligned} 1,\;\mbox{if }i=j\\ 0,\;\mbox{if }i\neq j\end{aligned}\right..

(11)

Theorem 2.10.

The operator $SP_{n}$ is linear.

Proof 2.11.

For $g_{1},\;g_{2}:X\to\mathbb{R}$ arbitrarily chosen and $\alpha,\;\beta\in\mathbb{R}$ , using the linearity of $C_{j}^{n}$ showed in Theorem 2.5, one has

	$\displaystyle SP_{n}[\alpha g_{1}+\beta g_{2}](x)$	$\displaystyle=\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot C_{j}^{n}[\alpha g_{1}+% \beta g_{2}](x)$
		$\displaystyle=\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot\left[\alpha C_{j}^{n}[g_{% 1}](x)+\beta C_{j}^{n}[g_{2}](x)\right]$
		$\displaystyle=\alpha\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot C_{j}^{n}[g_{1}](x)% +\beta\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot C_{j}^{n}[g_{2}](x)$
		$\displaystyle=\alpha SP_{n}[g_{1}](x)+\beta SP_{n}[g_{2}](x),$

the linearity of $SP_{n}$ being proved.

Theorem 2.12.

The Shepard operator $SP_{n}$ has degree of exactness n.

Proof 2.13.

We know that for some arbitrary operators $R_{i},\;i=1,...,K$ , with ${\rm dex}(R_{i})=r_{i},\;i=1,...,K,$ we have ${\rm dex}(S_{R})=\min\{r_{1},...,r_{K}\}$ , where

S_{R}f(x)=\sum\limits_{i=1}^{K}A_{i,\mu}(x)\cdot R_{i}(x).

Taking into account this property and the fact that ${\rm dex}(C_{j}^{n})=n,\;\forall j=1,...,K$ , we obtain the desired conclusion.

We now introduce the interpolation formula for the univariate Shepard combined with a polynomial, that is given by

f=SP_{n}[f]+R_{n}[f],

with $R_{n}[f]$ denoting the remainder.

Considering the space $H^{m}[a,b]$ , $m\in\mathbb{N}\setminus\{0\}$ of functions $f\in C^{m-1}[a,b]$ (continuously differentiable up to order $m-1$ , inclusively) with $f^{(m-1)}$ absolutely continuous on $[a,b]$ , we obtain the following result for the remainder of the formula:

Theorem 2.14.

If $f\in H^{n+1}[a,b]$ , then

R_{n}[f](x)=\int_{a}^{b}\phi_{n}(x,t)\cdot f^{(n+1)}(t)\mbox{ dt},

where

\phi_{n}(x,t)=\frac{(x-t)_{+}^{n}}{n!}-\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot% \left[\frac{(x_{j}-t)_{+}^{n}}{n!}+\sum\limits_{k=1}^{n}a_{j,k}(x-x_{j})^{k}% \right],

(12)

with $a_{j,k}$ given as solutions of $\frac{\partial E_{j}}{\partial a_{j,k}}=0$ , for each $k=1,...,n$ , for

E_{j}=\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\left[\frac{(x_{j}-t)_{+}^{n}}{n!}+\sum% \limits_{k=1}^{n}a_{j,k}(x_{i}-x_{j})^{k}-\frac{(x_{i}-t)_{+}^{n}}{n!}\right]^% {2}

and $\lambda_{i,j}$ given in (5), $j=1,...,K.$

Proof 2.15.

The degree of exactness for the Shepard operator $SP_{n}$ is n. Using now the Peano’s theorem, one gets

R_{n}[f](x)=\int_{a}^{b}\phi_{n}(x,t)\cdot f^{(n+1)}(t)\mbox{ dt},

with

\phi_{n}(\cdot,t)=R_{n}\left[\frac{(\cdot-t)_{+}^{n}}{n!}\right]=\frac{(\cdot-% t)_{+}^{n}}{n!}-\sum\limits_{j=1}^{K}A_{j,\mu}(\cdot)\cdot C_{j}^{n}\left[% \frac{(\cdot-t)_{+}^{n}}{n!}\right].

Finally, for all $x\in[a,b]$ , we obtain

\phi_{n}(x,t)=\frac{(x-t)_{+}^{n}}{n!}-\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot% \left[\frac{(x_{j}-t)_{+}^{n}}{n!}+\sum\limits_{k=1}^{n}a_{j,k}(x-x_{j})^{k}% \right],

where $a_{j,k}$ are solutions of $\frac{\partial E_{j}}{\partial a_{j,k}}=0$ , for each $k=1,...,n$ , for

E_{j}=\sum\limits_{\begin{subarray}{c}i=1\\ i\neq j\end{subarray}}^{K}\lambda_{i,j}\left[\frac{(x_{j}-t)_{+}^{n}}{n!}+\sum% \limits_{k=1}^{n}a_{j,k}(x_{i}-x_{j})^{k}-\frac{(x_{i}-t)_{+}^{n}}{n!}\right]^% {2}

concluding in this way the proof.

3 Test results

For the numerical experiments we consider four well-known real-valued test functions (see, e.g., [9]):

\begin{array}[c]{ll}\text{Cliff:}&f_{1}(x)=\frac{1}{2}\tanh(-9x+1)+0.5,\\ \\ \text{Gentle:}&f_{2}(x)=\frac{1}{3}\exp[-\frac{81}{16}(x-0.5)^{2}],\\ \\ \text{Saddle:}&f_{3}(x)=\frac{1.25}{6+6(3x-1)^{2}},\\ \\ \text{Steep:}&f_{4}(x)=\frac{1}{3}\exp[-\frac{81}{4}(x-0.5)^{2}].\end{array}

(13)

For each function $f_{i},\;i=1,...,4$ , we compare the test results obtained by considering the linear, quadratic and cubic interpolants $SP_{j}[f_{i}],\;j=1,2,3,$ with the ones obtained for some other combined Shepard operators, well-known in the literature. We study the maximum approximation errors for the Shepard operators of Lagrange, Taylor and Bernoulli type, for all of them considering the first, second and third order. They are denoted by $SL_{k},ST_{k}$ and $SB_{k}$ , $k=1,2,3$ , respectively. We recall their definitions in the sequel.

3.1 Univariate Shepard-Lagrange operator (see, e.g., [5])

For $K$ distinct points $x_{i}$ that belong to $X\subset\mathbb{R}$ and the real-valued function $f$ defined on $X$ such that the data $f(x_{i}),\;i\in\{1,\dots,K\}$ are known, the univariate Shepard-Lagrange operator is defined as

SL_{k}[f](x)=\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot L_{k}^{j}[f](x),

(14)

with

L_{k}^{j}[f](x)=\sum\limits_{i=0}^{k}\frac{\prod\limits_{\alpha=0,\;\alpha\neq i% }^{k}(x-x_{j+\alpha})}{\prod\limits_{\alpha=0,\;\alpha\neq i}^{k}(x_{j+i}-x_{j% +\alpha})}\cdot f(x_{j+i}),

(15)

$x_{K+i}=x_{K-i},\;i=1,...,k,$ and $A_{j,\mu}$ defined in (2), $\mu>0$ .

3.2 Univariate Shepard-Taylor operator (see, e.g., [5])

For $f:X\to\mathbb{R}$ and $K$ distinct interpolation nodes $x_{j},\;j\in\{1,\dots,K\}$ , consider the sets

\Delta=\{\eta_{j,i}\;|\;\eta_{j,i}(f)=f^{(i)}(x_{j})\mbox{ with }j=1,\dots,K;% \;i=0,\dots,k;\;k\in\mathbb{N}^{*}\}

and

\Delta_{j}(f)=\{\eta_{j,p}\;|\;p=0,\dots,k\}

such that $\Delta_{j}\subset\Delta$ is a subset of $\Delta$ associated to $\eta_{j}$ , having $\eta_{j}\in\Delta_{j}$ , for all $j=1,...,K$ .

Then, the univariate Shepard-Taylor operator is defined as

ST_{k}[f](x)=\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot T_{k}^{j}[f](x),

(16)

with

T_{k}^{j}[f](x)=\sum\limits_{i=0}^{k}\frac{(x-x_{j})^{i}}{i!}\cdot f^{(i)}(x_{% j})

(17)

and $A_{j,\mu}$ defined in (2), $\mu>0$ .

3.3 Univariate Shepard-Bernoulli operator (see, e.g., [6])

Suppose there are $K$ given points $x_{j}$ in $X\subset\mathbb{R}$ and $x_{K+1}=x_{K-1}$ . Then, we can define the univariate Shepard-Bernoulli operator as follows

SB_{k}[f](x)=\sum\limits_{j=1}^{K}A_{j,\mu}(x)\cdot B_{k}[f;x_{j},x_{j+1}](x),

(18)

with $A_{j,\mu}$ defined in (2) and the Bernoulli operators $B_{k}$ given by

B_{k}[f;a,b]=f(a)+\sum\limits_{j=1}^{k}\frac{h^{j-1}}{j!}\cdot\left(B_{j}\left% (\frac{x-a}{h}\right)-B_{j}\right)\cdot\left(f^{(j-1)}(a)-f^{(j-1)}(b)\right)

for $f\in C^{k}[a,b],\;k\geq 1$ , $h=b-a$ .

$B_{n}$ are the Bernoulli numbers, i.e. the values of the Bernoulli polynomials $B_{n}(x)$ at $x=0$ . The Bernoulli polynomials are defined recursively as

\left\{\begin{array}[]{ll}B_{0}(x)=1,\\ B_{n}^{\prime}(x)=nB_{n-1}(x),\;n\geq 1,\\ \int_{0}^{1}B_{n}(x)\;dx=0,\;n\geq 1.\end{array}\right.

We consider a set of $K=50$ equally spaced interpolation nodes from the interval $X=[0,1]$ and set the $\mu$ parameter’s value to $2$ . Table 1 presents the maximum interpolation errors for the classical Shepard operator $S_{\mu}f$ introduced in (1) and the linear $SP_{1}$ , quadratic $SP_{2}$ and cubic $SP_{3}$ Shepard operators, introduced in (10) for $n=1,2,3$ , respectively. In addition, we present the maximum approximation errors for the Shepard operators of Lagrange, Taylor and Bernoulli type, of order 1, 2 and 3, respectively. We can observe that the three new operators produce better approximation results than the classical Shepard operator. Moreover, as it was expected, higher degrees polynomials produce smaller approximation errors. We can observe that in the linear and quadratic cases, the approximation results for the Shepard operators combined with least squares fitting polynomials are close to the best approximation results for most of the functions. In the cubic cases the new Shepard operators obtained produce the smallest interpolation errors.

	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$
$S_{\mu}f$	0.0247	0.0043	0.0024	0.0084
$SP_{1}$	0.0157	0.0025	0.0024	0.0041
$SL_{1}$	0.0081	0.0020	0.0013	0.0030
$ST_{1}$	0.0067	0.0020	0.0012	0.0027
$SB_{1}$	0.0081	0.0020	0.0013	0.0030
$SP_{2}$	0.0066	0.0012	8.7983e-04	0.0041
$SL_{2}$	0.0048	9.4582e-04	0.0014	0.0027
$ST_{2}$	0.0050	0.0010	7.7720e-04	0.0026
$SB_{2}$	0.0048	0.0010	7.7771e-04	0.0027
$SP_{3}$	0.0053	5.4032e-04	6.7304e-04	0.0023
$SL_{3}$	0.0671	0.0050	0.0049	0.0024
$ST_{3}$	0.0094	8.7148e-04	8.7393e-04	0.0024
$SB_{3}$	0.0104	8.8533e-04	8.7689e-04	0.0024

Table 1: Maximum approximation errors, 50 equidistant nodes.

We also test these operators on a second set of $K=50$ Chebyshev nodes, defined as

x_{j}=\frac{1}{2}+\frac{1}{2}\cos\left(\frac{2j-1}{2K}\pi\right),\;j=1,...,K.

We present the maximum approximation errors in Table 2. In this case we can see that the new operators produce the best results in the quadratic case for all the functions, except for $f_{4}$ . In the cubic case they produce the smallest interpolation errors for all test functions. Very good results are obtained in the linear case as well.

	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$
$S_{\mu}f$	0.0246	0.0064	0.0046	0.0160
$SP_{1}$	0.0119	0.0018	0.0019	0.0066
$SL_{1}$	0.0078	0.0034	0.0016	0.0031
$ST_{1}$	0.0094	0.0035	0.0017	0.0021
$SB_{1}$	0.0083	0.0035	0.0016	0.0031
$SP_{2}$	0.0054	9.3156e-04	0.0011	0.0065
$SL_{2}$	0.0119	0.0027	0.0013	0.0040
$ST_{2}$	0.0139	0.0029	0.0015	0.0037
$SB_{2}$	0.0133	0.0029	0.0015	0.0038
$SP_{3}$	0.0046	2.6850e-04	7.0098e-04	0.0027
$SL_{3}$	0.0070	7.3503e-04	7.9055e-04	0.0051
$ST_{3}$	0.0089	9.3807e-04	9.8040e-04	0.0054
$SB_{3}$	0.0082	9.3521e-04	9.8137e-04	0.0054

Table 2: Maximum approximation errors, 50 Chebyshev nodes.

Finally, we present the graphical results for the Gentle and the Saddle functions using the set of 50 equally spaced nodes. Figures 1–2 illustrates the functions $f_{2}$ and $f_{3}$ and their corresponding polynomial Shepard interpolants $SP_{1},\;SP_{2}$ and $SP_{3}$ .

Refer to caption — (a) Function $f_{2}$ .

References

(1) R. Caira, F. Dell’Accio, Shepard-Bernoulli operators, Math. Comp. 76 (2007), 299–321.
(2) T. Cătinaş, The combined Shepard-Abel-Goncharov univariate operator, J. Numer. Anal. Approx. Theory 32 (2003), 11–20.
(3) Gh. Coman, Combined Shepard univariate operators, East J. Approx. 7 (2001), 471–483.
(4) Gh. Coman, R. Trîmbiţaş, Univariate Shepard-Birkhoff interpolation, J. Numer. Anal. Approx. Theory 30 (2001), 15–24.
(5) Gh. Coman, R. Trîmbiţaş, Combined Shepard univariate operators, East J. Approx. 7 (2001), 471–483.
(6) F. Dell’Accio, F. Di Tommaso, Scattered data interpolation by Shepard’s like methods: classical results and recent advances, Dolomites Res. Notes Approx. 9 (2016), 32–44.
(7) R. Franke, Scattered data interpolation: tests of some methods, Math. Comp. 38 (1982), 181–200.
(8) R. Franke, G. Nielson, Smooth interpolation of large sets of scattered data, Internat. J. Numer. Methods Engrg. 15 (1980), 1691–1704.
(9) R.J. Renka, A.K. Cline, A triangle-based $C^{1}$ interpolation method, Rocky Mountain J. Math. 14 (1984), 223–237.
(10) R.J. Renka, Multivariate interpolation of large sets of scattered data, ACM Trans. Math. Software 14 (1988), 139–148.
(11) R.J. Renka, Algorithm 660: QSHEP2D: Quadratic method for bivariate interpolation of scattered data, ACM Trans. Math. Software 14 (1988), 149–150.
(12) R.J. Renka, Algorithm 790: CSHEP2D: Cubic method for bivariate interpolation of scattered data, ACM Trans. Math. Software 25 (1999), 70–73.
(13) D. Shepard, A two dimensional interpolation function for irregularly spaced data, In: Proceedings of 23rd National Conference ACM (1968), 517–523.
(14) W. Thacker, J. Zhang, L. Watson, J. Birch, M. Iyer, M. Berry, Algorithm 905: SHEPPACK: Modified Shepard algorithm for interpolation of scattered multivariate data, ACM Trans. Math. Software 37 (2010), 1–20.

Univariate Shepard operators combined with least squares fitting polynomials

Abstract

Authors

Keywords

Paper coordinates

PDF

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

Paper (preprint) in HTML form

Univariate Shepard operators combined with least squares fitting polynomials

Abstract

1 Introduction

2 Shepard operators combined with polynomials constructed by the least squares method

Theorem 2.1

Proof 2.2.

Theorem 2.3.

Proof 2.4.

Theorem 2.5.

Proof 2.6.

Definition 2.7.

Theorem 2.8.

Proof 2.9.

Theorem 2.10.

Proof 2.11.

Theorem 2.12.

Proof 2.13.

Theorem 2.14.

Proof 2.15.

3 Test results

3.1 Univariate Shepard-Lagrange operator (see, e.g., [5])

3.2 Univariate Shepard-Taylor operator (see, e.g., [5])

3.3 Univariate Shepard-Bernoulli operator (see, e.g., [6])

References

References

Related Posts