Weighted Essentially Non-Oscillatory Shepard method
David Levin, José M. Ramón, Juan Ruiz-Álvarez, Dionisio F. Yáñez · 2024
Read Weighted Essentially Non-Oscillatory Shepard method by David Levin, José M. Ramón, Juan Ruiz-Álvarez, Dionisio F. Yáñez (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-02286.txt.
Introduction
David Levin and co-authors build in 2024 a nonlinear version of the Shepard interpolation method for scattered data. The classic method weights nearby points more than far ones. Near sharp jumps in a function, though, it and other linear methods oscillate and lose accuracy on sparse data.
Their version borrows adaptive weighting ideas from a shock-capturing scheme used in fluid problems. Rather than fixing one weight formula, they modify the weight function nonlinearly for any base choice. Tests show fewer oscillations near discontinuities and better overall interpolation quality. The method targets scientific computing and data analysis tasks.
Catalog record
| CREATOR | David Levin, José M. Ramón, Juan Ruiz-Álvarez, Dionisio F. Yáñez |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-02286
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Weighted Essentially Non-Oscillatory Shepard method David Levin, José M. Ramón, Juan Ruiz-Álvarez, Dionisio F. Yáñez Abstract Shepard method is a fast algorithm that has been classically used to interpolate scattered data in several dimensions. This is an important and well-known technique in numerical analysis founded in the main idea that data that is far away from the approximation point should contribute less to the resulting approximation. Approximating piecewise smooth functions in ℝ n \mathbb{R}^{n} near discontinuities along a hypersurface in ℝ n − 1 \mathbb{R}^{n-1} is challenging for the Shepard method or any other linear technique for sparse data due to the inherent difficulty in accurately capturing sharp transitions and avoiding oscillations. This letter is devoted to constructing a non-linear Shepard method using the basic ideas that arise from the weighted essentially non-oscillatory interpolation method (WENO). The proposed method aims to enhance the accuracy and stability of the traditional Shepard method by incorporating WENO’s adaptive and nonlinear weighting mechanism. To address this challenge, we will nonlinearly modify the weight function in a general Shepard method, considering any weight function, rather than relying solely on the inverse of the distance squared. This approach effectively reduces oscillations near discontinuities and improves the overall interpolation quality. Numerical experiments demonstrate the superior performance of the new method in handling complex datasets, making it a valuable tool for various applications in scientific computing and data analysis. 1 Introduction The Shepard method, introduced by Donald Shepard in 1968 [ 9 ] , is a widely used algorithm for interpolating scattered data in multiple dimensions. Traditionally, the weight function in the Shepard method is the inverse of the squared distance. However, this weight function can be generalized to any function, such as Gaussian [ 8 ] , inverse multiquadratic [ 5 ] , Matérn [ 7 ] , and Wendland functions [ 12 , 13 ] . These functions must have compact support and form a partition of unity to ensure the interpolation’s accuracy and stability [ 2 ] . The linear Shepard method performs well with smooth functions, such as the Franke’s function. However, it tends to produce non desirable diffusion effects near discontinuities, which can significantly degrade the approximation quality. In this letter, we propose a nonlinear Shepard’s method that aims to mitigate this diffusion. By modifying the weight function nonlinearly, we achieve results near discontinuities that are comparable to the Shepard’s method performance in smooth regions. The letter is organized as follows: The second section discusses the construction of the nonlinear method. We prove some properties in Section 3. Finally, Section 4 presents a series of numerical experiments comparing the performance of the linear and nonlinear methods and checking the theoretical results. 2 Construction of the non-linear method Given an open and bounded domain \Omega\subseteq\mathbb{R}^{n} , a set \chi_{N}=\{\mathbf{x}_{i}\in\Omega:i=1,\ldots,N\} of N distinct nodes and a corresponding set of function values \mathcal{F}_{N}=\{f_{i}=f(\mathbf{x}_{i}):i=1,\ldots,N\} , where f:\Omega\to\mathbb{R} . We assume the points \chi_{N} are quasi-uniformly distributed in \Omega , with a fill distance h=\sup_{x\in\Omega}\min_{\mathbf{x}_{i}\in\chi_{N}}\|\mathbf{x}-\mathbf{x}_{i}\| . Shepard’s method can be viewed as a special case of the moving least squares technique (see [ 6 ] ), where the degree of the polynomial is zero, i.e., a constant. Consequently, if we consider a non-negative, compactly supported, radial function \omega_{i}:\Omega\to\mathbb{R} , and define \omega_{i}(\mathbf{x})=\omega(\frac{\|\mathbf{x}_{i}-\mathbf{x}\|}{h}), the Shepard’s interpolant is defined as: \mathcal{I}_{\text{S}}(\mathbf{x})=\sum_{i=1}^{N}\frac{\omega_{i}(\mathbf{x})}{\sum_{j=1}^{N}\omega_{j}(\mathbf{x})}f_{i}=\sum_{i=1}^{N}W_{i}(\mathbf{x})f_{i}, where W_{i}:\Omega\to\mathbb{R} are defined as W_{i}(\mathbf{x})=\frac{\omega_{i}(\mathbf{x})}{\sum_{j=1}^{N}\omega_{j}(\mathbf{x})} . It follows that for i=1,\ldots,N , we have 0\leq W_{i}(\mathbf{x})\leq 1,\,\text{and}\,\sum_{j=1}^{N}W_{j}(\mathbf{x})=1,\forall\mathbf{x}\in\mathbb{R}^{n} . We call the W_{i} “ optimal Shepard weights ”. Remark 2.1 In Shepard’s method, the requirement that the function \omega(r) is compactly supported can be relaxed to a condition of rapid decay as r\to\infty . Interpolation is achieved if \omega(0)=\infty , (see [ 6 ] ). As described above, Shepard’s method is based on the distances between the evaluation point and the given nodes. However, if a discontinuity contaminates the data, or they present a strong gradient, It is then recommended to use only nodes that are free of singularities. To achieve this, the optimal Shepard weights are replaced with non-linear ones, defined as follows: \mathcal{W}_{i}(\mathbf{x})=\frac{\alpha_{i}(\mathbf{x})}{\sum_{j=1}^{N}\alpha_{j}(\mathbf{x})},\hskip 9.24994pt\alpha_{i}(\mathbf{x})=\frac{W_{i}(\mathbf{x})}{(\epsilon+I_{i})^{t}}. The values \{I_{i}\} are smoothness indicators, see [ 10 ] , which identify whether a node is near a discontinuity and thus should have a negligible contribution to the approximation. \epsilon and t are parameters chosen to achieve maximal approximation order. In our case, we take \epsilon=10^{-14} and t=4 . In the next subsection, we present a way to construct the smoothness indicators. With these ingredients the new WENO-Shepard’s method is: \mathcal{I}_{\text{WENO-S}}(\mathbf{x})=\sum_{i=1}^{N}\mathcal{W}_{i}(\mathbf{x})f_{i}. (1) 2.1 The smoothness indicators We start dividing our domain \Omega in some subdomains \mathcal{S}_{i} with \Omega\subset\cup_{i=1}^{N}\mathcal{S}_{i} , which satisfy that \mathbf{x}_{i}\in\mathcal{S}_{i},\,i=1,\ldots,N . In our case, we define the stencils as the balls centered in the data points, \mathbf{x}_{i} with a determined radius, \delta_{i} i.e., \mathcal{S}_{i}=\chi_{N}\cap B(\mathbf{x}_{i},\delta_{i})=\{\mathbf{x}_{j}\in\Omega:\|\mathbf{x}_{j}-\mathbf{x}_{i}\|<\delta_{i}\}=\{\mathbf{x}_{j_{i}}:j_{i}=1,\ldots,N_{i}\}. (2) To determine the radius, we rely on the general results presented in [ 2 , 6 , 13 ] , which assume that \delta_{i}=ch where c is a constant and h is the fill distance. To design the smoothness indicators, we aim for two properties indicated, for example, in [ 1 ] : P1 The order of a smoothness indicator that is free of discontinuities is h^{2} , i.e. I_{i}=O(h^{2})\,\,\text{if}\,\,f\,\,\text{is smooth in }\,\,\mathcal{S}_{i}. P2 When a discontinuity crosses the stencil \mathcal{S}_{i} then I_{i}\nrightarrow 0\,\,\text{as}\,\,h\to 0. Thus, we solve the linear least square problem for each i=1,\ldots,N, p_{i}=\argmin_{p\in\Pi_{1}(\mathbb{R}^{2})}\sum_{j_{i}=1}^{N_{i}}(f(\mathbf{x}_{j_{i}})-p(\mathbf{x}_{j_{i}}))^{2}, and define I_{i}=\frac{1}{N_{i}}\sum_{j_{i}=1}^{N_{i}}|f(\mathbf{x}_{j_{i}})-p_{i}(\mathbf{x}_{j_{i}})|. (3) It is clear that the I_{i} defined in ( 3 ) satisfy P1 and P2 . With these definitions we can prove some properties about the smoothness, the order of accuracy, and the behaviour close to the discontinuities presented by the approximant. 3 Properties of the new method In this section, we prove some characteristics about our new method. Principally, we want to conserve the properties of the linear one, Shepard’s method, and to improve the approximation in the zones close to the discontinuities. Let us start with the smoothness of the non-linear method. In this case, from the expression of the smoothness indicator, Eq. ( 3 ), we can see that it is a number independent of the variable x . Then, we only need the smoothness of the weight function \omega . This is similar to the linear Shepard’s operator. We can summarize this property with the following result (Th. 3.1 ). Theorem 3.1 Let \nu\in\mathbb{N} , \Omega\subset\mathbb{R}^{n} , \omega be a function with \omega\in\mathcal{C}^{\nu}(\Omega) , and let \mathcal{I}_{\text{\it WENO-S}} be the WENO Shepard’s approximation defined in Eq. ( 1 ), then \mathcal{I}_{\text{\it WENO-S}}\in\mathcal{C}^{\nu}(\Omega) . Regarding the order of accuracy in the smooth regions, it is evident that the new operator reproduces constants, as it satisfies the condition that: \sum_{i=1}^{N}\mathcal{W}_{i}(\mathbf{x})=1,\,\,\forall\,\mathbf{x}\in\mathbb{R}^{n}. As \omega is compactly supported, then we have the next theorem. Theorem 3.2 Let \Omega\subset\mathbb{R}^{n} . If f\in\mathcal{C}^{1}(\overline{\Omega}) , \chi_{N}=\{\mathbf{x}_{i}\in\Omega:i=1,\ldots,N\} are quasi-uniformly distributed with fill distance h , the weight function \omega is compactly supported with support size c , then \|f-\mathcal{I}_{\text{WENO-S}}\|_{\infty}\leq Ch\max_{\boldsymbol{\xi}\in\overline{\Omega}}|D^{\boldsymbol{\alpha}}f(\boldsymbol{\xi})|,\hskip 9.24994pt|\boldsymbol{\alpha}|=1, where C is a constant independent of h . Finally, we analyze the behaviour of the operator \mathcal{I}_{\text{WENO-S}} close to the discontinuities. For this purpose, we consider a (n-1) -hypersurface \Gamma defined by a function \gamma:\mathbb{R}^{n}\to\mathbb{R} being \Omega^{+}=\{\mathbf{x}\in\Omega:\gamma(\mathbf{x})\geq 0\},\hskip 9.24994pt\Omega^{-}=\Omega\setminus\Omega^{+}, and we suppose that \tilde{f}(\mathbf{x})=\left\{\begin{array}[]{ll}f_{1}(\mathbf{x}),&\mathbf{x}\in\Omega^{+},\\ f_{2}(\mathbf{x}),&\mathbf{x}\in\Omega^{-},\end{array}\right.