On a class of splines free of Gibbs phenomenon

Amat, Sergio; Ruiz, Juan; Shu, Chi-Wang; Trillo, Juan Carlos

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 55 (2021), pp. S29-S64

When interpolating data with certain regularity, spline functions are useful. They are defined as piecewise polynomials that satisfy certain regularity conditions at the joints. In the literature about splines it is possible to find several references that study the apparition of Gibbs phenomenon close to jump discontinuities in the results obtained by spline interpolation. This work is devoted to the construction and analysis of a new nonlinear technique that allows to improve the accuracy of splines near jump discontinuities eliminating the Gibbs phenomenon. The adaption is easily attained through a nonlinear modification of the right hand side of the system of equations of the spline, that contains divided differences. The modification is based on the use of a new limiter specifically designed to attain adaption close to jumps in the function. The new limiter can be seen as a nonlinear weighted mean that has better adaption properties than the linear weighted mean. We will prove that the nonlinear modification introduced in the spline keeps the maximum theoretical accuracy in all the domain except at the intervals that contain a jump discontinuity, where Gibbs oscillations are eliminated. Diffusion is introduced, but this is fine if the discontinuity appears due to a discretization of a high gradient with not enough accuracy. The new technique is introduced for cubic splines, but the theory presented allows to generalize the results very easily to splines of any order. The experiments presented satisfy the theoretical aspects analyzed in the paper.

Classification : 65D05, 65D17, 65M06, 65N06
Keywords: Splines, adaption to discontinuities, interpolation, computer aided design (modeling of curves)

A. A. Abushama and B. Bialecki, Modified nodal cubic spline collocation for Poisson’s equation. SIAM J. Numer. Anal. 46 (2008) 397–418. | MR | Zbl | DOI

S. Amat and J. Liandrat, On the stability of the PPH nonlinear multiresolution. Appl. Comput. Harmon. Anal. 18 (2005) 198–206. | MR | Zbl | DOI

S. Amat and J. Ruiz, New WENO smoothness indicators computationally efficient in the presence of corner discontinuities. J. Sci. Comput. 71 (2017) 1265–1302. | MR | Zbl | DOI

S. Amat, F. Aràndiga, A. Cohen, R. Donat, G. Garcia and M. Von Oehsen, Data compression with ENO schemes: a case study. Appl. Comput. Harmon. Anal. 11 (2001) 273–288. | MR | Zbl | DOI

S. Amat, S. Busquier and J. C. Trillo, On multiresolution schemes using a stencil selection procedure: applications to ENO schemes. Numer. Algorithms 44 (2007) 45–68. | MR | Zbl | DOI

S. Amat, K. Dadourian, J. Liandrat, J. Ruiz and J. C. Trillo, On a class of $L^1$-stable nonlinear cell-average multiresolution schemes. J. Comput. Appl. Math. 234 (2010) 1129–1139. | MR | Zbl | DOI

S. Amat, S. Busquier, M. Legaz, F. Manzano and J. Ruiz, Reciprocal polynomial extrapolation vs Richardson extrapolation for singular perturbed boundary problems. Numer. Algorithms 61 (2012) 631–647. | MR | Zbl | DOI

S. Amat, J. Liandrat, J. Ruiz and J. Trillo, On a compact non-extrapolating scheme for adaptive image interpolation. J. Franklin Inst. 349 (2012) 1637–1647. | MR | Zbl | DOI

S. Amat, J. Ruiz and J. C. Trillo, Adaptive interpolation of images using a new nonlinear cell-average scheme. Math. Comput. Simul. 82 (2012) 1586–1596. | MR | DOI

S. Amat, K. Dadourian, J. Liandrat and J. Trillo, High order nonlinear interpolatory reconstruction operators and associated multiresolution schemes. J. Comput. Appl. Math. 253 (2013) 163–180. | MR | Zbl

S. Amat, J. Ruiz and J. C. Trillo, Improving the compression rate versus $L^1$ error ratio in cell-average error control algorithms. Numer. Algorithms 67 (2014) 145–162. | MR | Zbl

S. Amat, J. Liandrat, J. Ruiz and J. Trillo, On a family of nonlinear cell-average multiresolution schemes for image processing. Math. Comput. Simul. 118 (2015) 30–48. | MR

S. Amat, J. Liandrat, J. Ruiz and J. C. Trillo, On a power WENO scheme with improved accuracy near discontinuities. SIAM J. Sci. Comput. 39 (2017) A2472–A2507. | MR | Zbl

S. Amat, J. Ruiz and J. C. Trillo, On an algorithm to adapt spline approximations to the presence of discontinuities. Numer. Algorithms 80 (2019) 903–936. | MR | Zbl

F. Aràndiga and R. Donat, Nonlinear multiscale decompositions: the approach of A. Harten. Numer. Algorithms 23 (2000) 175–216. | MR | Zbl

F. Arandiga, A. Cohen, R. Donat, N. Dyn and B. Matei, Approximation of piecewise smooth functions and images by edge-adapted (ENO-EA) nonlinear multiresolution techniques. Special Issue on Mathematical Imaging – Part II. Appl. Comput. Harmon. Anal. 24 (2008) 225–250. | MR | Zbl

F. Aràndiga, A. Belda and P. Mulet, Point-value WENO multiresolution applications to stable image compression. J. Sci. Comput. 43 (2010) 158–182. | MR | Zbl

A. K. B. Chand and G. P. Kapoor, Generalized cubic spline fractal interpolation functions. SIAM J. Numer. Anal. 44 (2006) 655–676. | MR | Zbl

A. Cohen, N. Dyn and B. Matei, Quasi linear subdivision schemes with applications to ENO interpolation. Appl. Comput. Harmon. Anal. 15 (2003) 89–116. | MR | Zbl

O. Davydov and L. L. Schumaker, Stable approximation and interpolation with $C^1$ quartic bivariate splines. SIAM J. Numer. Anal 39 (2002) 1732–1748. | MR | Zbl

C. De Boor, A Practical Guide to Splines. SIAM, Springer-Verlag New York 27 (1980). | MR | Zbl

R. Devore, Nonlinear approximation. Acta Numer. 7 (1998) 51–150. | MR | Zbl

M. S. Floater and M.-J. Lai, Polygonal spline spaces and the numerical solution of the Poisson equation. SIAM J. Numer. Anal. 54 (2016) 797–824. | MR | Zbl

J. Foster and F. B. Richards, Gibbs-Wilbraham splines. Constr. Approx. 11 (1995) 37–52. | MR | Zbl

D. Gottlieb and C.-W. Shu, On the Gibbs phenomenon and its resolution. SIAM Rev. 39 (1997) 644–668. | MR | Zbl

A. Harten, Multiresolution representation of data: a general framework. SIAM J. Numer. Anal. 33 (1996) 1205–1256. | MR | Zbl

A. Harten, Multiresolution representation of data II. SIAM J. Numer. Anal. 33 (1996) 1205–1256. | MR | Zbl

A. Harten and S. Osher, Uniformly high-order accurate nonoscillatory schemes. I. SIAM J. Numer. Anal. 24 (1987) 279–309. | MR | Zbl

A. Harten, B. Engquist, S. Osher and S. R. Chakravarthy, Uniformly high order accurate essentially non-oscillatory schemes. III. J. Comput. Phys. 71 (1987) 231–303. | MR | Zbl

F. Richards, A Gibbs phenomenon for spline functions. J. Approx. Theory 66 (1991) 334–351. | MR | Zbl

L. L. Schumaker, Spline Functions: Computational Methods, SIAM. Springer-Verlag, New York (2015). | MR | Zbl

D. Schweikert, An interpolation curve using splines in tension. J. Math. Phys. 45 (1966) 312–317. | MR | Zbl

S. Serna and A. Marquina, Power ENO methods: a fifth-order accurate weighted power ENO method. J. Comput. Phys. 194 (2004) 632–658. | MR | Zbl

C.-W. Shu, Order ENO and WENO Schemes for Computational Fluid Dynamics. Springer, Berlin, Heidelberg (1999) 439–582. | MR | Zbl

C.-W. Shu and S. Osher, Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77 (1988) 439–471. | MR | Zbl

C.-W. Shu and S. Osher, Efficient implementation of essentially non-oscillatory shock-capturing schemes II. J. Comput. Phys. 83 (1989) 32–78. | MR | Zbl

H. Späth, Exponential spline interpolation. Computing 4 (1969) 225–233. | MR | Zbl

R. A. Usmani, Inversion of Jacobi’s tridiagonal matrix. Comput. Math. App. 27 (1994) 59–66. | MR | Zbl

Z. Zhang and C. F. Martin, Convergence and Gibbs’ phenomenon in cubic spline interpolation of discontinuous functions. J. Comput. Appl. Math. 87 (1997) 359–371. | MR | Zbl