TL;DR
This paper introduces "filtered schemes," a novel and flexible approach to constructing accurate and convergent numerical methods for solving Hamilton-Jacobi (HJ) equations. By blending stable, monotone schemes with potentially unstable, accurate schemes, these methods achieve higher-order accuracy while guaranteeing convergence to the correct solution, even in the presence of singularities.
What Problem Does This Paper Address?
Hamilton-Jacobi (HJ) equations are fundamental in many scientific and engineering fields, including optimal control, image processing, and geometric optics. Finding accurate and reliable numerical solutions to these equations is challenging, especially when the solutions are not smooth (i.e., they have singularities). Traditional methods that are stable and convergent (like monotone schemes) are often only first-order accurate, while higher-order accurate methods can be unstable or difficult to implement. This paper aims to bridge this gap by developing a general framework for constructing finite difference schemes that are both provably convergent and achieve higher-order accuracy, even for solutions with singularities.
Methods
The core innovation is the "filtered scheme," which combines a stable, monotone scheme ($F_M$) with an accurate scheme ($F_A$). The filtered scheme ($F_h$) is defined as follows:
$F_h[u] = \begin{cases} F_A[u] & \text{if } |F_A[u] - F_M[u]| \le \sqrt{h} \\ F_M[u] & \text{otherwise} \end{cases}$
Here, $h$ is the grid spacing. This approach ensures that the stable, monotone scheme is used when the accurate scheme might be unstable or inaccurate (e.g., near singularities), while the accurate scheme is employed in smooth regions to achieve higher-order accuracy. The authors demonstrate this by implementing various accurate schemes, including standard centered differences, higher-order upwinding, and ENO (Essentially Non-Oscillatory) interpolation, combined with monotone schemes. For solving the resulting discrete equations, they leverage efficient methods like the fast sweeping method, which is applicable due to the explicit nature of many of their filtered schemes.
Datasets
Not discussed in the paper. The paper focuses on numerical methods and their theoretical properties, validated through computational examples with known exact solutions.
Key Insights and Ideas
- The "Filtering" Principle: The core idea of blending a stable scheme with an accurate one is surprisingly simple yet powerful. It allows for the benefits of both worlds: stability from the monotone scheme and accuracy from the accurate scheme.
- Guaranteed Convergence: By ensuring the monotone scheme is active in critical regions, the filtered schemes inherit the convergence guarantees of monotone schemes, even though the filtered scheme itself might not be monotone.
- Flexibility in Scheme Choice: The framework is highly general, allowing researchers to plug in various existing accurate discretizations (even those that are unstable on their own) and combine them with a suitable monotone scheme.
- Accuracy Near Singularities: The method is designed to maintain higher-order accuracy in smooth regions while gracefully falling back to a stable, lower-order scheme near singularities, leading to improved overall accuracy compared to purely monotone methods.
- Explicit Schemes and Fast Solvers: The construction of explicit filtered schemes, particularly with upwind discretizations, enables the use of efficient solvers like the fast sweeping method, making the approach computationally practical.
Key Results
- Provable Convergence: The filtered schemes are proven to converge to the unique viscosity solution of the HJ equation.
- Higher-Order Accuracy: The paper demonstrates second, third, and fourth-order accurate schemes in one dimension and second-order accurate schemes in two dimensions for the eikonal equation and other HJ equations.
- Improved Accuracy in Practice: Computational results show that filtered schemes consistently achieve higher accuracy than the monotone scheme alone, especially in regions where the solution is smooth.
- Upwind Schemes Excel: For the eikonal equation, higher-order upwind filtered schemes consistently achieve their theoretical order of accuracy, even for piecewise smooth solutions.
- Efficiency: The explicit nature of many filtered schemes allows for efficient computation using the fast sweeping method.
Limitations and Future Work
- Global vs. Local Accuracy: While higher-order accuracy is achieved in smooth regions, the overall global accuracy can be limited by the presence of singularities, especially in higher dimensions. The paper notes that for some two-dimensional cases, the global convergence rate in the $l_\infty$ norm can be less than the formal order of accuracy.
- ENO Scheme Behavior: The paper observes that ENO schemes, while designed to adapt stencils, sometimes do not achieve their theoretical order of accuracy and can be outperformed by upwind schemes, particularly in cases with complex solution behavior.
- Future Work: The authors suggest that the filtered scheme framework can be extended to other types of partial differential equations. They also note that the explicit nature of the upwind filtered schemes makes them particularly well-suited for fast sweeping methods, which could be further explored. The potential for using these schemes in more complex scenarios, like time-dependent problems, is also hinted at.
Summary updated