Univariate Shepard operators combined with least squares fitting polynomials

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.

Authors

Andra Malina
Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj-Napoca, Romania
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, Cluj-Napoca, Romania

Keywords

Univariate Shepard operator; Weighted least squares approximation; Interpolation formula; Degree of exactness; Remainder term

Paper coordinates

A. Malina, Univariate Shepard operators combined with least squares fitting polynomials, Filomat, 38 (2024) no. 15, pp. 5507-5516. https://doi.org/10.2298/FIL2415507M

PDF

About this paper

Journal

Filomat

Publisher Name

Faculty of Sciences and Mathematics, University of Nis, Serbia

Print ISSN

0354-5180

Online ISSN

2406-0933

google scholar link

Paper (preprint) in HTML form

Univariate Shepard operators combined with least squares fitting polynomials

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 , for a given set of K interpolation nodes, xiX,i=1,,K, the Shepard operator is defined as

Sμf(x)=i=1KAi,μ(x)f(xi), (1)

with the basis functions Ai,μ given by

Ai,μ(x)=|xxi|μj=1K|xxj|μ,i=1,,K,xixj,for ij,j=1,,K, (2)

xX and μ>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, constructed following the weighted least squares approximation technique.

Consider X, f:X and K given real nodes, denoted by xj, j=1,,K. The values of the function f on the given nodes are known and denoted by fj=f(xj),j=1,,K.

Under these assumptions, for a point xX, let us define the nth degree polynomial function Cjn[f], j=1,,K, n, as

Cjn[f](x)=fj+k=1naj,k(xxj)k, (3)

where the coefficients aj,k are found such that they minimize the sum of the weighted squared residuals

Ej=i=1ijKλi,j[Cjn[f](xi)fi]2, (4)

where

λi,j=|xixj|μk=1kiK|xixk|μ, (5)

for i,j=1,,K and μ>0.

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

Ejaj,k=0, for each k=1,,n and j=1,,K.

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

Ejaj,k=2i=1ijKλi,j[p=1naj,p(xixj)p+(fjfi)](xixj)k=0, for each k=1,,n.

Let us make the notation

xi,jp=i=1ijKλi,j(xixj)p.

Then, the system of normal equations that has to be solved in order to find the coefficients aj,k,k=1,,n, has the form

{aj,1xi,j2+aj,2xi,j3++aj,nxi,jn+1=i=1ijKλi,j(xixj)(fifj)aj,1xi,jk+1+aj,2xi,jk+2++aj,nxi,jk+n=i=1ijKλi,j(xixj)k(fifj)aj,1xi,jn+1+aj,2xi,jn+2++aj,nxi,j2n=i=1ijKλi,j(xixj)n(fifj), (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

Mjaj=bj, (7)

where Mj is a n×n matrix having on the entry (r,s) the element i=1ijKλi,j(xixj)r+s, bj is a vector of n elements with i=1ijKλi,j(xixj)k(fifj) on the kth entry and aj=(aj,1,aj,2,,aj,n)T is the vector of unknowns.

Theorem 2.1

The operator Cjn[f] defined in (3) satisfies the following interpolation property

Cjn[f](xj)=fj,j=1,,K.
Proof 2.2.

For any j=1,,K, one has

Cjn[f](xj)=fj+k=1naj,k(xjxj)k=fj.
Theorem 2.3.

The operator Cjn[f],j=1,,K, has the degree of exactness n, i.e.,

dex(Cjn[f])=n,j=1,,K,

where ”dex” denotes the degree of exactness.

Proof 2.4.

For xX we have the following cases for Cjn[f],j=1,,K:

  • Case 1.

    f(x)=e0(x)=x0. We get aj,k=0, k=1,,n, and obviously

    Cjn[e0](x)=e0(xj)+0k=1n(xxj)k=1=e0(x).
  • Case 2.

    f(x)=en(x)=xn. We obtain the following solution for the coefficients aj,k:

    aj,k=(nnk)xjnk,k=1,,n (8)

    and

    Cjn[en](x) =en(xj)+k=1n(nnk)xjnk(xxj)k
    =(nn)xjn0(xxj)0+k=1n(nnk)xjnk(xxj)k
    =k=0n(nk)xjnk(xxj)k=(xj+xxj)n=xn=en(x).
  • Case 3.

    f(x)=ep(x),p=1,,n1. In this situation we have

    aj,r=(ppr)xjpr for r=1,,p and aj,s=0 for s=p+1,,n

    and

    Cjn[ep](x)=ep(xj)+r=1p(ppr)xjpr(xxj)r=xp=ep(x).
  • Case 4.

    f(x)=en+1(x). It is obvious that Cjn[en+1](x)xn+1 since

    Cjn[en+1](x)=en+1(xj)+k=1naj,k(xxj)k

    and no term xn+1 appears.

In conclusion, dex(Cjn[f])=n,j=1,,K.

Theorem 2.5.

The operator Cjn[f] is linear.

Proof 2.6.

We have to show that for g1,g2:X, arbitrarily chosen, and α,β, one has for xX:

Cjn[αg1+βg2](x)=αCjn[g1](x)+βCjn[g2](x),j=1,,K. (9)

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

Cjn[g1](x) =g1(xj)+k=1naj,k(xxj)k,j=1,,K,
Cjn[g2](x) =g2(xj)+k=1naj,k′′(xxj)k,j=1,,K,
Cjn[αg1+βg2](x) =(αg1+βg2)(xj)+k=1naj,k(xxj)k
=αg1(xj)+βg2(xj)+k=1naj,k(xxj)k,j=1,,K.

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

aj,k=αaj,k+βaj,k′′, for every k=1,,n and j=1,,K.

Now, one has

Cjn[αg1+βg2](x) =αg1(xj)+βg2(xj)+k=1n(αaj,k+βaj,k′′)(xxj)k
=α[g1(xj)+k=1naj,k(xxj)k]+β[g2(xj)+k=1naj,k′′(xxj)k]
=αCjn[g1](x)+βCjn[g2](x),j=1,,K,

and so (9) is proved.

Definition 2.7.

For f:X and the set of K interpolation nodes, using the nth degree polynomial given in (3), we can define the univariate Shepard operator combined with a nth degree polynomial as

SPn[f](x)=j=1KAj,μ(x)Cjn[f](x), (10)

with Aj,μ defined in (2) using the given parameter μ>0.

Theorem 2.8.

The following interpolation property holds

SPn[f](xj)=f(xj),j=1,,K.
Proof 2.9.

It follows from Theorem 2.1 and the fact that for Aj,μ given in (2), we have Aj,μ(xi)=δij, where

δij={1,if i=j0,if ij. (11)
Theorem 2.10.

The operator SPn is linear.

Proof 2.11.

For g1,g2:X arbitrarily chosen and α,β, using the linearity of Cjn showed in Theorem 2.5, one has

SPn[αg1+βg2](x) =j=1KAj,μ(x)Cjn[αg1+βg2](x)
=j=1KAj,μ(x)[αCjn[g1](x)+βCjn[g2](x)]
=αj=1KAj,μ(x)Cjn[g1](x)+βj=1KAj,μ(x)Cjn[g2](x)
=αSPn[g1](x)+βSPn[g2](x),

the linearity of SPn being proved.

Theorem 2.12.

The Shepard operator SPn has degree of exactness n.

Proof 2.13.

We know that for some arbitrary operators Ri,i=1,,K, with dex(Ri)=ri,i=1,,K, we have dex(SR)=min{r1,,rK}, where

SRf(x)=i=1KAi,μ(x)Ri(x).

Taking into account this property and the fact that dex(Cjn)=n,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=SPn[f]+Rn[f],

with Rn[f] denoting the remainder.

Considering the space Hm[a,b], m{0} of functions fCm1[a,b] (continuously differentiable up to order m1, inclusively) with f(m1) absolutely continuous on [a,b], we obtain the following result for the remainder of the formula:

Theorem 2.14.

If fHn+1[a,b], then

Rn[f](x)=abϕn(x,t)f(n+1)(t) dt,

where

ϕn(x,t)=(xt)+nn!j=1KAj,μ(x)[(xjt)+nn!+k=1naj,k(xxj)k], (12)

with aj,k given as solutions of Ejaj,k=0, for each k=1,,n, for

Ej=i=1ijKλi,j[(xjt)+nn!+k=1naj,k(xixj)k(xit)+nn!]2

and λi,j given in (5), j=1,,K.

Proof 2.15.

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

Rn[f](x)=abϕn(x,t)f(n+1)(t) dt,

with

ϕn(,t)=Rn[(t)+nn!]=(t)+nn!j=1KAj,μ()Cjn[(t)+nn!].

Finally, for all x[a,b], we obtain

ϕn(x,t)=(xt)+nn!j=1KAj,μ(x)[(xjt)+nn!+k=1naj,k(xxj)k],

where aj,k are solutions of Ejaj,k=0, for each k=1,,n, for

Ej=i=1ijKλi,j[(xjt)+nn!+k=1naj,k(xixj)k(xit)+nn!]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]):

Cliff:f1(x)=12tanh(9x+1)+0.5,Gentle:f2(x)=13exp[8116(x0.5)2],Saddle:f3(x)=1.256+6(3x1)2,Steep:f4(x)=13exp[814(x0.5)2]. (13)

For each function fi,i=1,,4, we compare the test results obtained by considering the linear, quadratic and cubic interpolants SPj[fi],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 SLk,STk and SBk, 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 xi that belong to X and the real-valued function f defined on X such that the data f(xi),i{1,,K} are known, the univariate Shepard-Lagrange operator is defined as

SLk[f](x)=j=1KAj,μ(x)Lkj[f](x), (14)

with

Lkj[f](x)=i=0kα=0,αik(xxj+α)α=0,αik(xj+ixj+α)f(xj+i), (15)

xK+i=xKi,i=1,,k, and Aj,μ defined in (2), μ>0.

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

For f:X and K distinct interpolation nodes xj,j{1,,K}, consider the sets

Δ={ηj,i|ηj,i(f)=f(i)(xj) with j=1,,K;i=0,,k;k}

and

Δj(f)={ηj,p|p=0,,k}

such that ΔjΔ is a subset of Δ associated to ηj, having ηjΔj, for all j=1,,K.

Then, the univariate Shepard-Taylor operator is defined as

STk[f](x)=j=1KAj,μ(x)Tkj[f](x), (16)

with

Tkj[f](x)=i=0k(xxj)ii!f(i)(xj) (17)

and Aj,μ defined in (2), μ>0.

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

Suppose there are K given points xj in X and xK+1=xK1. Then, we can define the univariate Shepard-Bernoulli operator as follows

SBk[f](x)=j=1KAj,μ(x)Bk[f;xj,xj+1](x), (18)

with Aj,μ defined in (2) and the Bernoulli operators Bk given by

Bk[f;a,b]=f(a)+j=1khj1j!(Bj(xah)Bj)(f(j1)(a)f(j1)(b))

for fCk[a,b],k1, h=ba.

Bn are the Bernoulli numbers, i.e. the values of the Bernoulli polynomials Bn(x) at x=0. The Bernoulli polynomials are defined recursively as

{B0(x)=1,Bn(x)=nBn1(x),n1,01Bn(x)𝑑x=0,n1.

We consider a set of K=50 equally spaced interpolation nodes from the interval X=[0,1] and set the μ parameter’s value to 2. Table 1 presents the maximum interpolation errors for the classical Shepard operator Sμf introduced in (1) and the linear SP1, quadratic SP2 and cubic SP3 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.

f1 f2 f3 f4
Sμf 0.0247 0.0043 0.0024 0.0084
SP1 0.0157 0.0025 0.0024 0.0041
SL1 0.0081 0.0020 0.0013 0.0030
ST1 0.0067 0.0020 0.0012 0.0027
SB1 0.0081 0.0020 0.0013 0.0030
SP2 0.0066 0.0012 8.7983e-04 0.0041
SL2 0.0048 9.4582e-04 0.0014 0.0027
ST2 0.0050 0.0010 7.7720e-04 0.0026
SB2 0.0048 0.0010 7.7771e-04 0.0027
SP3 0.0053 5.4032e-04 6.7304e-04 0.0023
SL3 0.0671 0.0050 0.0049 0.0024
ST3 0.0094 8.7148e-04 8.7393e-04 0.0024
SB3 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

xj=12+12cos(2j12Kπ),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 f4. 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.

f1 f2 f3 f4
Sμf 0.0246 0.0064 0.0046 0.0160
SP1 0.0119 0.0018 0.0019 0.0066
SL1 0.0078 0.0034 0.0016 0.0031
ST1 0.0094 0.0035 0.0017 0.0021
SB1 0.0083 0.0035 0.0016 0.0031
SP2 0.0054 9.3156e-04 0.0011 0.0065
SL2 0.0119 0.0027 0.0013 0.0040
ST2 0.0139 0.0029 0.0015 0.0037
SB2 0.0133 0.0029 0.0015 0.0038
SP3 0.0046 2.6850e-04 7.0098e-04 0.0027
SL3 0.0070 7.3503e-04 7.9055e-04 0.0051
ST3 0.0089 9.3807e-04 9.8040e-04 0.0054
SB3 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 12 illustrates the functions f2 and f3 and their corresponding polynomial Shepard interpolants SP1,SP2 and SP3.

Refer to caption
(a) Function f2.
Refer to caption
(b) Interpolant SP1[f2].
Refer to caption
(c) Interpolant SP2[f2].
Refer to caption
(d) Interpolant SP3[f2].
Figure 1: Graphs for the Gentle function f2.
Refer to caption
(a) Function f3.
Refer to caption
(b) Interpolant SP1[f3].
Refer to caption
(c) Interpolant SP2[f3].
Refer to caption
(d) Interpolant SP3[f3].
Figure 2: Graphs for the Saddle function f3.

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 C1 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.

[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 C1 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.

Related Posts

No results found.