0
$\begingroup$

I'm currently revisiting some FDM schemes for convection-diffusion equations in 1D, 2D and 3D and getting up to speed with the industry-standard methods again. The application is derivatives pricing, the equation is more or less the "Black-Scholes-PDE" in various forms and flavors.

In higher dimensions, I'm currently looking at ADI and AOS schemes and I was thinking whether one could not improve those a bit. While in "introductory" derivatives pricing for European call options the CN-Scheme is often presented, which is often a fair and good first choice, you'll get problems like oscillations around your at-the-money point, since there is a non-differentiability. You are also looking at problems when introducing barriers.

What you can of course do is make the grid finer - which in turn increases the dimensionality of your linear system. If you however only increase the grid around the areas where you "need it" (heuristics here are around the strike and/or around the "spot", so the area in the state space that is of most interest for you in these types of problems) you get almost the same effect.

I find however only little information on concrete work done on what happens to modern methods like ADI when you change the grid. I can imagine that the effect is not arbitrary - back from university I remember that in FEM, I'd consider whether or not my element is a conforming one or not, which I obviously have here. I found some papers about Shishkin meshes in which non-constant grid sizes and "optimal meshes" are constructed, but that did not really cover my concerns.

My three questions:

  1. Does the grid construction impact a FDM scheme significantly enough that it is worth the effort? Does it impact the convergence of the sparse solver potentially?
  2. How would I work in "areas of interest" and information about my boundaries (continuities etc.) into my grid generation?
  3. Is there some literature out there that covers this?
$\endgroup$

1 Answer 1

4
$\begingroup$

Your question mentions both space and time discretization and the problems that can arise due to different choices of one or the other. I think that you might be conflating problems that come from the timestepping scheme with problems that come from the spatial discretization and it's worth trying to disentangle the two.

You mention the Crank-Nicholson scheme, which is easy to implement and formally of 2nd order for linear evolution equations. But as you point out it can have oscillatory artifacts in the presence of sharp jumps, either in the initial condition or due to forcing. The reason for this is that the Crank-Nicholson scheme has predominantly dispersive errors, and as such it can create spurious maxima and minima where there were none before. The backward Euler scheme, while formally of only 1st order, does not create spurious maxima and minima; its errors are more diffusive than dispersive. For some problems, and I think yours is one of them, it may be worth paying the price of a lower-order timestepping scheme if it keeps the solution within the range that you expect. Most importantly for your question I think is the fact that the diffusive vs dispersive character of the errors from the timestepping scheme remains true whether you use finite difference or finite element methods. You can reduce the magnitude of the errors by refining the grid near where the spurious oscillations are most problematic. But nothing will change the fact that the Crank-Nicholson scheme is not positivity-preserving while the backward Euler scheme is.

This idea that "order isn't everything" is described in the book Finite Difference Methods by Randy Leveque. You can also read more about the diffusive vs dispersive character of the errors of different methods in Numerical Methods for Fluid Dynamics by Dale Durran. You can read more about maximum principles and positivity preservation in chapter 3 of A Guide to Numerical Methods for Transport Equations by Dmitri Kuzmin which is also free.

Leaving all that aside, it is definitely possible to improve on ADI; for example, you can use ADI as a smoother in a multigrid method, which should be substantially faster for big enough problem sizes. Grid construction definitely can significantly affect the overall speed and accuracy of the simulation; using only uniform grids would be fine if you just need a proof of concept but is definitely leaving some performance on the table. The book Grid Generation Methods covers all sorts of strategies for gridding, whether you're using finite difference methods on a logically-uniform grid that's been deformed to have more resolution in particular spots, or you're using a non-uniform mesh and finite element methods.

$\endgroup$
1
  • $\begingroup$ This is a great answer, thank you a lot. You could be right and I need to deepen my understanding of what makes a numerical method converge “better” and not just “faster”. I will read up the sources you mentioned and hopefully come back with more precise questions! $\endgroup$
    – freistil90
    Jan 8, 2023 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.