Smoothing techniques
The presence of discontinuities in the initial conditions creates problems for the solution of the discretized Black-Scholes PDE (and not only). There can be discontinuities either in the payoff function itself (e.g. digital option), or its derivatives (e.g. vanilla option). We can also be introducing discontinuities periodically at certain time points in our solution, like for example at exercise dates for Bermudan-style options (first derivative discontinuities). Or even worse, option value discontinuities at monitoring dates when we solve for discretely monitored barrier options.
There are two kinds of problems in such cases. One is that such discontinuities "pollute" the solution and will in general result in a reduction from the theoretical rate of convergence of the numerical scheme, i.e. a loss of expected accuracy. The other is that when central finite difference discretizations are used for the time derivative, as is effectively the case with the Crank-Nicolson (CN) scheme, spurious oscillations are introduced. Interestingly, those can affect the derivatives of the solution (otherwise referred to as sensitivities, or Greeks, or hedging parameters), even when the solution (value) itself appears correct and smooth. This is a pretty well-known problem when using the CN scheme for option pricing and for this reason some advocate the use of alternative schemes. That been said, the CN family of schemes are easy to implement and can theoretically achieve quadratic convergence in time for any volatility structure. For this reason we would like to keep using them, if only there was a remedy for the above problem. Luckily there is and it's pretty simple too.
First thing we need to do is to somehow effectively "smooth" the discontinuity. There are different ways of doing this and in most cases covered by the pricer I chose to implement the simplest one (?), which is to always make sure that the discontinuity (say the strike) lies in the middle between two grid points. So the grid generator needs to make sure of that. For the case of discretely monitored barrier options I chose an alternative technique, directly smoothing the initial and periodic conditions by averaging around the grid points at discontinuities, as described in [1]. In this case the initial conditions are averaged around the strike and the periodic conditions imposed at each monitoring date are averaged around the barrier(s). Either technique (grid-shifting or averaging) goes a long way towards restoring the quadratic convergence promised by the CN scheme. The pricer smooths discontinuities by default so there is currently no way of appreciating the effect on the achieved accuracy. But you are invited to check for yourselves if you are building your own implementation. (Also see end of the page.)
Then we need to do something for those spurious oscillations. The "trick" needed is easy too and it's called Rannacher time-stepping (see Rannacher, 1984 [2], or Giles & Carter, 2006 [3]). This simply involves dividing the first time-step after a discontinuity in 2 or 4 equal sub-steps and using the implicit scheme for those sub-steps only. Those few implicit steps are sufficient to effectively filter out high frequency error components. The loss of accuracy is negligible and overall second-order convergence is retained. Combining this with the "smart" construction of the grid and/or averaging the initial conditions outlined before, pretty much eliminates the aforementioned oscillations and we're good to go.
In the case of discretely monitored barrier options where a discontinuity is basically re-imposed periodically, repeated Rannacher procedures are applied after every monitoring date. The same applies for Bermudan-style options after every exercise date. This of course increases the computational cost (and erodes the quadratic convergence in time), especially when the number of monitoring / exercise dates is large compared to the total number of time steps used, but it's still more economical (and safer) than just using the original CN scheme with sufficiently large number of time steps. Because I forgot to mention, the spurious oscillations disappear without any modification to the original CN scheme when we use a sufficiently large number of time-steps (i.e. decrease dt). Though exactly how much is sufficient is not known a priori and has to be found experimentally. An alternative scheme with better inherent oscillation-damping properties may be more efficient in this case.
The presence of discontinuities in the initial conditions creates problems for the solution of the discretized Black-Scholes PDE (and not only). There can be discontinuities either in the payoff function itself (e.g. digital option), or its derivatives (e.g. vanilla option). We can also be introducing discontinuities periodically at certain time points in our solution, like for example at exercise dates for Bermudan-style options (first derivative discontinuities). Or even worse, option value discontinuities at monitoring dates when we solve for discretely monitored barrier options.
There are two kinds of problems in such cases. One is that such discontinuities "pollute" the solution and will in general result in a reduction from the theoretical rate of convergence of the numerical scheme, i.e. a loss of expected accuracy. The other is that when central finite difference discretizations are used for the time derivative, as is effectively the case with the Crank-Nicolson (CN) scheme, spurious oscillations are introduced. Interestingly, those can affect the derivatives of the solution (otherwise referred to as sensitivities, or Greeks, or hedging parameters), even when the solution (value) itself appears correct and smooth. This is a pretty well-known problem when using the CN scheme for option pricing and for this reason some advocate the use of alternative schemes. That been said, the CN family of schemes are easy to implement and can theoretically achieve quadratic convergence in time for any volatility structure. For this reason we would like to keep using them, if only there was a remedy for the above problem. Luckily there is and it's pretty simple too.
First thing we need to do is to somehow effectively "smooth" the discontinuity. There are different ways of doing this and in most cases covered by the pricer I chose to implement the simplest one (?), which is to always make sure that the discontinuity (say the strike) lies in the middle between two grid points. So the grid generator needs to make sure of that. For the case of discretely monitored barrier options I chose an alternative technique, directly smoothing the initial and periodic conditions by averaging around the grid points at discontinuities, as described in [1]. In this case the initial conditions are averaged around the strike and the periodic conditions imposed at each monitoring date are averaged around the barrier(s). Either technique (grid-shifting or averaging) goes a long way towards restoring the quadratic convergence promised by the CN scheme. The pricer smooths discontinuities by default so there is currently no way of appreciating the effect on the achieved accuracy. But you are invited to check for yourselves if you are building your own implementation. (Also see end of the page.)
Then we need to do something for those spurious oscillations. The "trick" needed is easy too and it's called Rannacher time-stepping (see Rannacher, 1984 [2], or Giles & Carter, 2006 [3]). This simply involves dividing the first time-step after a discontinuity in 2 or 4 equal sub-steps and using the implicit scheme for those sub-steps only. Those few implicit steps are sufficient to effectively filter out high frequency error components. The loss of accuracy is negligible and overall second-order convergence is retained. Combining this with the "smart" construction of the grid and/or averaging the initial conditions outlined before, pretty much eliminates the aforementioned oscillations and we're good to go.
In the case of discretely monitored barrier options where a discontinuity is basically re-imposed periodically, repeated Rannacher procedures are applied after every monitoring date. The same applies for Bermudan-style options after every exercise date. This of course increases the computational cost (and erodes the quadratic convergence in time), especially when the number of monitoring / exercise dates is large compared to the total number of time steps used, but it's still more economical (and safer) than just using the original CN scheme with sufficiently large number of time steps. Because I forgot to mention, the spurious oscillations disappear without any modification to the original CN scheme when we use a sufficiently large number of time-steps (i.e. decrease dt). Though exactly how much is sufficient is not known a priori and has to be found experimentally. An alternative scheme with better inherent oscillation-damping properties may be more efficient in this case.
The effectiveness of the Rannacher treatment is evident. Combined with either grid-shifting or payoff averaging, which in effect both locally "diffuse" the initial payoff discontinuity, it enables the Crank-Nicolson scheme to truly live up to its theoretical quadratic potential. Both options were calculated on a uniform grid with dS=1.1 and dt=1/15.
For examples of how these smoothing techniques (and also non-uniform grids) can enable safe and accurate pricing of discrete barrier options see Discrete Barriers with Crank-Nicolson.
Although here the use of the above techniques is only illustrated within the simple (constant volatility, GBM) Black-Scholes framework of the pricer, the same ideas are readily applicable in the context of more realistic option pricing models. See for example [4], where the idea behind Rannacher smoothing is reported to eliminate oscillation and convergence problems for three different schemes (Crank-Nicolson, Douglas and Craig-Sneyd) used to solve the 2-D Heston (stochastic volatility) PDE.
Please refer to [1] for more details on possible treatments of discontinuities in option pricing.
You can reproduce the above graphs, or experiment further if you wish, using the standalone pricer (free beta version for Windows PCs).
For examples of how these smoothing techniques (and also non-uniform grids) can enable safe and accurate pricing of discrete barrier options see Discrete Barriers with Crank-Nicolson.
Although here the use of the above techniques is only illustrated within the simple (constant volatility, GBM) Black-Scholes framework of the pricer, the same ideas are readily applicable in the context of more realistic option pricing models. See for example [4], where the idea behind Rannacher smoothing is reported to eliminate oscillation and convergence problems for three different schemes (Crank-Nicolson, Douglas and Craig-Sneyd) used to solve the 2-D Heston (stochastic volatility) PDE.
Please refer to [1] for more details on possible treatments of discontinuities in option pricing.
You can reproduce the above graphs, or experiment further if you wish, using the standalone pricer (free beta version for Windows PCs).
EDIT: For some reason this is the most visited page on this website, yet most of you seem to leave without checking any of the cross-links. Perhaps a more detailed treatment of the subject is what you are after, while this is only meant as a quick demonstration of the basic numerical techniques one can see in action using the pricer. To this end I've now added a little bit more here, regarding the effect of the discontinuity smoothing / averaging, plus the piece of code that makes it happen.
References
[1] D. M. Pooley , K. R. Vetzal , and P. A. Forsyth, Convergence Remedies For Non-Smooth Payoffs in Option Pricing, University of Waterloo, (2002).
[2] Rannacher, R. Finite element solution of diffusion problems with irregular data, Numerische Mathematik, 43 (1984), pp. 309–327.
[3] Giles M. & Carter R. Convergence analysis of Crank–Nicolson and Rannacher time-marching, Journal of Computational Finance, 9 (4) (2006), pp. 89-112.
[4] Hout K. J. In ’t & Foulon S. ADI finite difference schemes for option pricing in the Heston model with correlation, International Journal of Numerical Analysis and Modeling, 7 (2) (2010), pp. 303-320.