Finite Difference Methods for Nonlinear Elliptic PDEs
Contents |
Monotone Schemes on a narrow stencil
The starting point for this work is
- Convergent Difference Schemes for Nonlinear Elliptic and Parabolic Equations: Hamilton-Jacobi Equations and Free Boundary Problems, SIAM Journal on Numerical Analysis, Vol 44 (2006) No. 2 pp. 879-895.
which builds schemes for a wide class of equations. The main requirement for convergence to viscosity solutions is that the schemes be monotone. This property is a discrete version of the comparison principle. The paper characterizes monotone schemes, and explains how to build them. A related paper is
- (with T. Zariphopoulou) Pricing early exercise contracts in incomplete markets, Computational Management Science, Vol 1 Issue 1 December (2003) pages 75-107.
While the application is to a particular problem in mathematical finance, the contribution from the point of view of numerics is an illustration of how to combine different terms (linear elliptic terms, Hamilton-Jacobi equations, obstacles) to build schemes for a complicated problem. The procedure is formalized in the first paper, but the equation here is more elaborate.
Schemes for Degenerate Equations: Infinity Laplace and Mean Curvature
A more difficult problem is building schemes which converge to viscosity solutions when the second order terms are either degenerate or fully nonlinear. Unlike the earlier works, to build monotone schemes for these types of equations required the introduction of a new idea, at least in this context.
As observed by Motzkin and Wasow, degenerate equations could reduce to diffusion in only one direction, and that direction may not line up with the grid. This makes building monotone schemes impossible for degenerate equations on a fixed grid, at least is second order accuracy is required. An abstract explanation for this obstruction is the fact that the collection of elliptic equations form a (non-polyhedral) convex cone, but the collection of monotone, second order accurate finite difference schemes form a polyhedral cone which is a subset of the first cone. This means there must always be some equations which can't approximated in this way.
A new approach was required to build schemes. The next group of papers introduced the idea of wide stencil schemes, with a directional resolution. This new parameter measured how well the round cone was approximated by the polyhedral cone. The new schemes are lower accuracy, but provably convergnet.
The next couple of papers deal with the degenerate case.
Building Efficient Methods Using Convergent Schemes for Validation
While the schemes are less accurate, the fact that they are provably convergent make them ideal for studying solutions near singularities. From a scientific computing point of view, it is natural to then build more efficient (faster, more accurate) methods which can be validated by the provably convergent schemes.
A more efficient scheme for the convex envelope was built by directly exploiting uniform and directional convexity. This idea was taken even further in the papers which follow.
Schemes for Fully Nonlinear Equations: Monge-Ampere, Pucci, Convex Envelope
Now we consider several fully nonlinear equations:
- The Monge-Ampere equation
- The maximal and minimal Pucci equations (which have a Stochastic Control interpretation)
- The Convex Envelope
In this case the degeneracy is no longer the only problem. Now the equations are fully nonlinear. The observation which make the numerical discretization possible