Interpolation and approximation of piecewise smooth functions with corner discontinuities on sigma quasi-uniform grids

1. Problem Statement

The paper addresses the challenge of interpolating univariate data sampled from piecewise smooth functions that possess isolated corner singularities (discontinuities in the first derivative).

• The Issue: Classical linear interpolation methods suffer from the Gibbs phenomenon (spurious oscillations) and diffusion near discontinuities, leading to poor accuracy.
• The Context: While nonlinear methods like ENO (Essentially Non-Oscillatory) and Subcell Resolution (SR) have been successful on uniform grids, many practical applications (e.g., adaptive mesh refinement, specific physical simulations) require non-uniform grids.
• The Gap: Extending the theoretical guarantees of these nonlinear methods from uniform grids to general non-uniform grids is mathematically difficult. The authors focus specifically on $\sigma$ quasi-uniform grids, a class of non-uniform grids where the ratio of the maximum spacing ($h_{max}$) to the minimum spacing ($h_{min}$) is bounded by a constant $\sigma$.

2. Methodology

The authors generalize the work presented in a previous study [8] (which was limited to uniform grids) to the $\sigma$ quasi-uniform setting. The methodology consists of three main components:

A. The Interpolation Framework

The proposed method combines ENO strategies with Subcell Resolution (SR):

1. Stencils: For any interval $[x_i, x_{i+1}]$, a stencil of $m$ points is selected.
2. Smoothness Detection: The algorithm uses divided differences (specifically second-order) to identify the smoothest stencil. If a stencil crosses a singularity, the divided difference is large.
3. Classification: Intervals are labeled as:
   • Type G (Good): No singularity suspected. Standard ENO interpolation is applied.
   • Type B (Bad): A singularity is suspected.
4. Subcell Resolution (SR): If an interval is Type B, the algorithm attempts to locate the exact position of the corner ($\mu$) by finding the intersection point ($\psi$) of two polynomials:
   • $\tilde{p}^-_{j,m}$: Interpolating points to the left of the singularity.
   • $\tilde{p}^+_{j,m}$: Interpolating points to the right of the singularity.
     The final interpolation is defined piecewise using these two polynomials meeting at $\psi$.

B. The Detection Mechanism

A specific algorithm is defined to label intervals as Type B or G based on the magnitude of divided differences relative to their neighbors.

• Lemma 1: Proves that Type B intervals appear in groups of at most size 2, separated by groups of Type G intervals of size at least $m-1$. This ensures the singularity is isolated and surrounded by smooth regions.

C. Theoretical Analysis

The authors derive error bounds based on the grid spacing $h = h_{max}$ and a critical value $h_c$:
$$h_c = \frac{|[f']|}{4 \sup_{R\setminus\mu} |f''(x)|}$$
where $[f']$ is the jump in the first derivative at the singularity.

3. Key Contributions

1. Extension to Non-Uniform Grids: The paper successfully extends the theoretical framework of ENO-SR interpolation from uniform grids to $\sigma$ quasi-uniform grids.
2. Singularity Detection Proof: It proves that for grid spacings $h_{max} < h_c$, the detection mechanism always identifies the interval containing the singularity (or the pair of intervals if the singularity is near a node).
3. Optimal Approximation Orders:
   • Case 1 ($h < K h_c$): When the grid is sufficiently fine relative to the singularity strength, the method achieves optimal order $O(h^m)$ (where $m$ is the number of stencil points), matching the performance on uniform grids.
   • Case 2 ($h \geq K h_c$): When the grid is coarse relative to the singularity, the method guarantees second-order accuracy $O(h^2)$.
4. Sharpness of Results: The authors provide a counter-example (adapted from [8]) proving that for piecewise smooth functions with corner singularities, one cannot generally achieve higher than second-order accuracy ($O(h^2)$) if the grid spacing is not small enough to resolve the singularity, regardless of the method used.

4. Results

Theoretical Results

• Lemma 2 & 3: Establish that the singularity is detected and its position estimated with high precision ($O(h^m)$) provided $h_{max}$ is below the critical threshold.
• Theorem 1: Formalizes the global error bounds:
  $$||f - I_X f||_\infty \leq \begin{cases} C h^m \sup |f^{(m)}| & \text{if } h < K h_c \\ C h^2 \sup |f''| & \text{if } h \geq K h_c \end{cases}$$
  This confirms that the nonlinear method recovers the optimal convergence rate of the underlying smooth function when the grid resolves the discontinuity.

Numerical Experiments

The authors tested the method on a family of functions $f_d(x)$ with a corner at $x = \pi/8$, varying the discontinuity strength $d$.

• Setup: A $\sigma$ quasi-uniform grid with $\sigma=2$ was used (note: $\sigma=2$ exceeds the theoretical limit of $\sigma < 1.5$ in the proof, yet results were positive).
• Findings:
  • When $h_{max} < h_c$ (which depends on $d$), the numerical approximation order converged to 4th order (for $m=4$).
  • When $h_{max} > h_c$ (coarse grids or weak discontinuities), the order dropped to 2nd order, consistent with the theoretical lower bound.
  • The experiments demonstrated that the method is robust even when the theoretical condition $\sigma < 1.5$ is slightly violated, suggesting the conditions are sufficient but not strictly necessary in practice.

5. Significance

• Bridging Theory and Practice: This work validates the use of high-order nonlinear interpolation schemes in adaptive and non-uniform mesh environments, which are common in computational fluid dynamics (shock capturing) and image processing.
• Robustness: It provides a rigorous mathematical guarantee that the "Subcell Resolution" technique does not lose its high-order accuracy benefits simply because the grid is non-uniform, provided the grid is not too distorted ($\sigma$-quasi-uniform).
• Practical Guidelines: The definition of the critical spacing $h_c$ offers a practical criterion for mesh refinement: to achieve high-order accuracy near a corner, the grid spacing must be refined until it is smaller than the ratio of the jump in the derivative to the curvature of the function.

In conclusion, the paper successfully generalizes the ENO-SR interpolation theory to $\sigma$ quasi-uniform grids, proving that optimal convergence rates are recoverable for piecewise smooth functions with corner singularities, provided the grid resolution is sufficient to resolve the discontinuity.