# A Smoothening Method for the Piecewise Linear Interpolation

Authors: Beong In Yun
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

We propose a method to smoothen a piecewise linear interpolation
at a small number of nodes on a bounded interval.
The method employs a sigmoidal type weight function having a property that clusters most points on the left side
of the interval toward 0 and those on the right side toward 1.
The proposed method results in a noninterpolatory approximation which is
smooth over the whole interval.
We provide an algorithm for implementing
the presented smoothening method. To demonstrate usefulness of the presented method
we introduce some numerical examples and investigate the results.


---

## Body

## 1. Introduction

It is well known that, by Weierstrass approximation theorem, every continuous function on a bounded interval can be approximated arbitrarily accurately by polynomials. Nevertheless, it is also true that there is no fixed array of interpolation points that achieves convergence for all continuous functions as mentioned in the literature [1]. To overcome this problem, the piecewise polynomial interpolation or rational function approximation may be considered. In particular, piecewise polynomial functions such as spline functions have been used in various approximation fields including computer graphics, data fitting, numerical integration, and differential equations [2, 3]. However, it is not difficult to find troublesome examples for which the existing approximation methods will not suitably work when the number of interpolation nodes is not large enough.In this paper, we propose a new noninterpolatory approximation method that is based on a smoothening process for the piecewise linear interpolation at a small number of nodes on a given interval. The main purpose of this work is summarized as follows:(i)
Rendering the piecewise linear interpolant smooth, that is, infinitely differentiable over the whole interval.(ii)
Improving the accuracy of the approximation over the interval except the interpolation nodes.To fulfill this purpose, we construct a rational function denoted by qn(x) which smoothens all the vertices of the initial piecewise linear interpolant for 2n nodes with a small integer n. From numerical results for some examples one can see that the presented method is available and comparable with existing outstanding methods.Contents of this paper are as follows. In Section2, we employ a weight function wm(x) in (1) of order m≥1 whose prototype is a sigmoidal transformation introduced by Prössdorf and Rathsfeld [4]. In Section 3, for a set of equally spaced nodes {xk}k=02n on a bounded interval [a,b], we define a modified weight function vj,k(x) of an integer order mj≥1. Then, for each integer 1≤j≤n, we construct piecewise smooth functions Lj,k(x), k=1,2,…,2n-j, in the jth smoothening step so that each Lj,k(x) reflects the behavior of its precedents Lj-1,2k-1(x) and Lj-1,2k(x), depending on order mj of the associated weight function vj,k(x). It is found that the resultant approximation qn(x)≔Ln,1(x) is in C∞[a,b] and noninterpolatory with the approximation property at the given nodes as shown in Theorem 1. Section 4 includes numerical examples of some test functions whose results show the availability of the presented method.


## 2. A Sigmoidal Type Weight Function

For an interval[α,β] and a real number m≥1 we set a real valued function(1)wmα,β;x=x-αmx-αm+β-xm,α≤x≤βwhich we call a weight function of order m. The derivative of wm(α,β;x) with respect to x is(2)wm′α,β;x=mβ-αx-αm-1β-xm-1x-αm+β-xm2satisfying wm′(α,β;x)>0 for all α<x<β. In addition,(3)wm′α,β;α+β2=mβ-α.We summarize basic properties ofwm(x)∶=wm(α,β;x) below.(P1)
Values ofwm(x) at the points x=α,(α+β)/2,β are(4)wmα=0,wmα+β2=12,wmβ=1independently of the orderm. In addition, wm(x) is strictly increasing from 0 to 1 on the interval [α,β] since wm′(x)>0 in (2).(P2)
For sufficiently largem asymptotic behavior of wm(x) is(5)wmx=Ox-αβ-xm,α<x<α+β21-Oβ-xx-αm,α+β2<x<β.(P3)
wm(x) satisfies(6)wmc-t+wmc+t=1,0≤t≤β-α2for a central pointc=(α+β)/2.(P4)
wm(x)∈C1[α,β]∩C∞(α,β) for any real m≥1.By the change of variablesx=(β-α)ξ+α the weight function wm(x) becomes the so-called elementary sigmoidal transformation γm(ξ)=ξm/(ξm+(1-ξ)m),0≤ξ≤1, defined in [4]. In general, traditional sigmoidal transformations have been used for numerical evaluation of the singular integrals [5–7].


## 3. Smoothening the Piecewise Linear Interpolation

For a given interval[a,b], in this paper, we consider a set of equally spaced nodes(7)xk=a+b-aNk,k=0,1,2,…,N,where N≥2 is an integer not too large. We generalize the weight function wm, defined in (1), on [a,b] as follows. For an integer j≥1 and for an integer mj≥1, define(8)vj,kx≔wmjak,bk;x=x-akmjx-akmj+bk-xmj,a≤x≤b,where ak and bk are some nodes such as a≤ak<bk≤b defined by (7).The functionvj,k(x) with an integer order mj has inherited the properties (P1)–(P4) of wmj(x) on the restricted interval [α,β]=[ak,bk], including additional properties (P3)′ and (P4)′ on the whole interval [a,b] below.(P3)′
vj,k(x) satisfies(9)vj,kck-t+vj,kck+t=1,t≥0for a central pointck=(ak+bk)/2.(P4)′
vj,k(x)∈C∞[a,b].General behavior ofvj,k(x),mj=1,2,3,6, with [ak,bk]=[0,2]⊂[a,b]=[-2,4], for example, is shown in Figure 1. One can see that vj,k(x) becomes flatter outside the interval [ak,bk] as the order mj goes higher. This can be surmised from property (P2).Figure 1
Graphs of the functionsvj,k(x) with ak=0 and bk=2 for each mj=1,2,3,6 on a subinterval [ak,bk]=[0,2] in (a) and those on the whole interval [a,b]=[-2,4] in (b).
(a)
(b)From now on we setN=2n for an integer n≥1. Then, for a continuous function f(x),a≤x≤b, we define linear functions(10)lkx=fxk-fxk-1xk-xk-1x-xk+fxk,k=1,2,…,N,each of which interpolates two points xk-1,f(xk-1) and xk,f(xk). Then we consider a piecewise linear interpolation,(11)q0x≔l1x,x0≤x≤x1l2x,x1≤x≤x2⋮lNx,xN-1≤x≤xN.To smoothen the piecewise linear interpolation q0(x) over the whole interval [a,b]=[x0,xN] we propose an n-step strategy using the weight function vj,k(x) as follows.Step  0. Setting initial lines:(12)L0,kx=lkxfor each k=1,2,…,2n=N.Step  1. Smoothening vertices of q0(x) at the nodes x2k-1,k=1,2,…,2n-1: set(13)L1,kx=1-v1,kxL0,2k-1x+v1,kxL0,2kx,x2k-1≤x≤x2kfor each k=1,2,…,2n-1, and define a function(14)q1x≔L1,1x,x0≤x≤x2L1,2x,x2<x≤x4⋮L1,2n-1x,xN-2<x≤xN.Step  2. Smoothening vertices of q0(x) at the nodes x4k-2,k=1,2,…,2n-2: set(15)L2,kx=1-v2,kxL1,2k-1x+v2,kxL1,2kx,x4k-1≤x≤x4kfor each k=1,2,…,2n-2, and define a function(16)q2x≔L2,1x,x0≤x≤x4L2,2x,x4<x≤x8⋮L2,2n-2x,xN-4<x≤xN.⋮Step
n
-
1. Smoothening vertices of q0(x) at the nodes x2n-1k-2n-2, k=1,2: set(17)Ln-1,kx=1-vn-1,kxLn-2,2k-1x+vn-1,kxLn-2,2kx,x2n-1(k-1)≤x≤x2n-1k, for each k=1,2, and define a function(18)qn-1x≔Ln-1,1x,x0≤x≤x2n-1Ln-1,2x,x2n-1<x≤xN.Step
n. Smoothening a vertex of q0(x) at the node x2n-1: define a final function(19)qnx≔Ln,1x=1-vn,1xLn-1,1x+vn,1xLn-1,2x,a=x0≤x≤xN=b.In eachjth smoothening step (j=1,2,…,n) above, function vj,k(x) is defined by (8) with an appropriate integer order mj≥1 and nodes set by(20)ak=x2jk-1,bk=x2jkfor each k=1,2,…,2n-j(=N/2j).As a result, every vertex of the initial piecewise linear interpolationq0(x) has been smoothened by qn(x), whereas the interpolation property may be weakened as qn(xi)≈f(xi) for all xi’s except x0, x2n-1, and xN=x2n as shown in Theorem 1. In fact, property P4′ implies that qn(x)∈C∞[a,b].For intuitional comprehension on the presented method, Figure2 is included.  It shows the effect of L1,k(x) in the first smoothening step (j=1) by comparing results for the orders m1=1,2,4,8 of the associated weight function v1,k(x). One can see that L1,k(x) reflects the behavior of its precedents L0,2k-1(x) and L0,2k(x) over the larger region as order m1 goes higher, preserving the interpolation and the smoothness on the doubled local interval [x2(k-1),x2k]. In general, each jth piecewise smooth function Lj,k(x),k=1,2,…,2n-j, has the same property on the local interval [x2j(k-1),x2jk].Figure 2
Effect of the first step (j=1) smoothening L1,k(x) for each of the orders m1=1,2,4,8 of the weight function v1,k(x).
(a)
(b)
(c)
(d)Referring to the aforementioned comments, we may consider that, for smallj  (i.e., for the small subintervals x2j(k-1)≤x≤x2jk), order mj of the weight function vj,k(x) might be low in order to sustain the natural behavior in the range between interpolation nodes. For large j  (i.e., for the large subintervals), higher orders are required to prevent loss of the accuracy at the nodes except the endpoints and the midpoint of the subinterval. Thus, for practical performance of the presented method, we suggest integer orders mj,j=1,2,…,n, as(21)1≤m1<m2<⋯<mn.Theorem 1.
For integer ordersmj, satisfying (21), of the weight functions vj,k(x), j=1,2,…,n, with N=2n in (8), we have(22)qnxi=fxi,i=0,2n-1,2n,qnxi-fxi=Ohim2,i=1,3,5,…,N-1Ohim3,i=2,4,6,…,N-2,where 0<hi<1.Proof.
For eachx=x0=a and x=x2n=b, we have(23)qna=Ln-1,1a=Ln-2,1a=⋯=L0,1a=l1a=faqnb=Ln-1,2b=Ln-2,4b=⋯=L0,2nb=l2nb=fbfrom the definition of Lj,k(x) and property (P1) of the weight function vj,k(x). Similarly, for the midpoint x=x2n-1,(24)qnx2n-1=Ln-1,1x2n-1=Ln-2,2x2n-1=⋯=L0,2n-1x2n-1=l2n-1x2n-1=fx2n-1.
To prove the approximation property ofqn(x) at interior points xi,1≤i≤2n-1=N-1, we first consider the case of i=1. Definition of Lj,k(x) with the related nodes ak and bk in (20) and the assumption (21) for the order of vj,k(x) imply that (25)qnx1=1-vn,1x1Ln-1,1x1+vn,1x1Ln-1,2x1=Ln-1,1x1+Ovn,1x1=1-vn-1,1x1Ln-2,1x1+vn-1,1x1Ln-2,2x1+Ovn,1x1=Ln-2,1x1+Ovn-1,1x1=⋯=L1,1x1+Ov2,1x1=1-v1,1x1L0,1x1+v1,1x1L0,2x1+Ov2,1x1=fx1+Ov2,1x1,as m2 goes to the infinity, where the last equality results from L0,1(x1)=L0,2(x1)=f(x1). Thus, it follows that(26)qnx1-fx1=Ov2,1x1.In fact, since a1=x0 and b1=x4 in (20) for definition of v2,1(x),(27)x1<a1+b12=x2.Then from property (P2) of the weight function v2,1(x) of order m2 with α=a1 and β=b1 we have(28)v2,1x1=Oh1m2,where 0<h1<1. This results in(29)qnx1-fx1=Oh1m2.By a similar way, we have, for any odd integer i=2k-1(k=1,2,3,…,2n-1),(30)qnxi-fxi=Ohim2,0<hi<1.
For the case ofi=2, an even number, (31)qnx2=1-vn,1x2Ln-1,1x2+vn,1x2Ln-1,2x2=Ln-1,1x2+Ovn,1x2=1-vn-1,1x2Ln-2,1x2+vn-1,1x2Ln-2,2x2+Ovn,1x2=Ln-2,1x2+Ovn-1,1x2=⋯=L2,1x2+Ov3,1x2=1-v2,1x2L1,1x2+v2,1x2L1,2x2+Ov3,1x2=fx2+Ov3,1x2,where the last equality results from L1,1(x2)=L1,2(x2)=f(x2). Thus(32)qnx2-fx2=Ov3,1x2.Since a1=x0 and b1=x8 in (20) for definition of v3,1(x),(33)x2<a1+b12=x4.Then from property (P2) of the weight function v3,1(x) of order m3 with α=a1 and β=b1 we have(34)v3,1x2=Oh2m3,0<h2<1.Thus(35)qnx2-fx2=Oh2m3.By a similar way, we have, for any even integer i=2k(k=1,2,3,…,2n-1-1),(36)qnxi-fxi=Ohim3,0<hi<1.The proof is completed.The concept of the presented method for a case ofN=8(n=3) is illustrated in Figure 3. Therein one can see that nonsmooth vertices at the nodes x1,x2,…,x7 appear in the initial piecewise linear interpolation. Figure 3 explains that the vertices at the nodes x1,x3,x5, and x7 are blunted in the first smoothening step (j=1) and those at the nodes x2 and x6 are blunted in the second step (j=2). Finally, the remaining vertex at x4 is blunted in the last step (j=n=3).Figure 3
Illustration of the presented method for the case ofn=3. The symbol (t)j denotes an interpolation point at the tth node xt which is smoothened by Lj,k(x) in the jth smoothening step.For implementation of the presented method, we write the following algorithm with a given data{xi,f(xi)∣i=0,1,2,…,2n} and properly chosen orders mj, j=1,2,3,…,n, based on condition (21):(37)i≔0.Whilei=i+1≤2n.
SetL0,ix≔fxi-fxi-1/xi-xi-1x-xi+fxi(38)j≔0.Whilej=j+1≤n(39)k≔0.
While(k=k+1≤2n-j)(40)ak≔x2jk-1;bk≔x2jkvj,kx≔x-akmjx-akmj+bk-xmjLj,kx≔1-vj,kxLj-1,2k-1x+vj,kxLj-1,2kx.Set thejth smoothening interpolation,(41)qjx≔Lj,1x,ifa1≤x≤b1Lj,2x,ifa2≤x≤b2⋮Lj,2n-jx,ifa2n-j≤x≤b2n-j.


## 4. Examples

To perform the presented algorithm we used aMathematica (V.10) programming code, given in Appendix, where we have taken linearly increasing orders mj=3j-2 for the weight functions vj,k(x).We choose a test function below. Consider(42)fx=cos⁡2x+x2,0≤x≤3with 2n+1 nodes (n=3)(43)xk=38k,k=0,1,2,…,8.Results of the presented method are given in Figure 4, which shows consistency with the illustration given in Figure 3 and Theorem 1. The dotted curve indicates the original graph of f(x), and it is observed that qj(x), j=1,2,3, have highly improved the accuracy of the initial piecewise linear approximation q0(x). In Figure 5, the resultant approximation q3(x) is compared with two existing approximations, the Hermite interpolation H(x) and the cubic spline interpolation S(x). One can see that q3(x) is better than H(x) and S(x) in approximation over the whole interval, while the interpolation property at the given nodes is weakened as shown in Theorem 1. In fact, computation of the l2-norm error of the presented approximation q3(x) at the nodes {xk}k=08 results in ∑k=08‍f(xk)-q3(xk)2≈0.068.Figure 4
Smoothened piecewise linear interpolationqj(x), j=0,1,2,3, for the example f(x) with N=23. The dotted curve indicates the original graph of f(x).
(a)
(b)
(c)
(d)Figure 5
Comparison of the presented approximationq3(x), Hermite interpolation H(x), and spline interpolation S(x) for f(x) with N=23. Dotted curves indicate the original graph of f(x).
(a)
q
3
(
x
)
(b)
H
(
x
)
(c)
S
(
x
)For another example, we take a parametric function(44)rt=xt,yt=t2+cos⁡t,t2-sin⁡t,-π≤t≤4πwith the nodes(45)tk=-π+5π8k,k=0,1,2,…,8.In this case, the presented method is applied to both functions x(t) and y(t). Figures 6 and 7 include the results of the presented method, which shows the same availability and efficiency of the method as the case of the previous test function.Figure 6
Smoothened piecewise linear interpolationsqj(t), j=0,1,2,3, for the parametric function r(t) with N=23. The dotted curve indicates the original graph of r(t).
(a)
(b)
(c)
(d)Figure 7
Comparison of the presented approximationq3(t), Hermite interpolation H(t), and spline interpolation S(t) for the parametric function r(t) with N=23. Dotted curves indicate the original graph of r(t).
(a)
q
3
(
t
)
(b)
H
(
t
)
(c)
S
(
t
)


## 5. Conclusions

In this paper, we proposed a method which results in the noninterpolatory approximationsqj(x), j=1,2,…,n, and the last one qn(x) smoothens all the vertices of the initial piecewise linear interpolant q0(x). Although the interpolation property of q0(x) at most nodes is weakened by qn(x) as the approximation property in Theorem 1, we have obtained smoothness over the whole interval. Moreover, in the results of the numerical implementation for some examples, we have found that the accuracy of the presented approximation qn(x) is somewhat better than that of the Hermite interpolation and the spline interpolation over the whole interval.The performance of the presented method depends on the orders of the associated weight functions, and analysis for the problem of choosing optimal orders is left as a further work. In addition, the idea proposed in this work may be extended to the higher order piecewise polynomial interpolation.



---

*Source: 376362-2015-07-27.xml*