Serving the Quantitative Finance Community

 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Monotone Schemes: what are they and why are they good?

September 25th, 2020, 5:53 pm

On suggestion from JohnLeM.

Always good to start with a definition,thus avoiding other alternate mental models

https://www.cfd-online.com/Wiki/Monotone_scheme
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 25th, 2020, 8:28 pm

On suggestion from JohnLeM.

Always good to start with a definition,thus avoiding other alternate mental models

https://www.cfd-online.com/Wiki/Monotone_scheme
Excellent !
A first comment: we might wish to slightly modify this definition, because it does not seem to match finite difference schemes, that are the basic schemes one should study.

For instance consider a mesh of I points [$] x^1,...,x^I [$], denote a discretized function as a vector [$]u^n := (u^n_i \sim u(t^n,x^i))_i[$]. Considering a linear problem, after discretization, we often get a linear semi-group having form
[$] u^{n+1} = H(x^1,...,x^I) u^{n}[$], where [$]H(x^1,...,x^N)[$] is a matrix of size [$]I \times I[$]. Hence we should modify slightly the definition pointed out on cfd on line:

A scheme [$]v = H(u)[$], [$] H : \mathbb{R}^I \mapsto  \mathbb{R}^I[$] is monotone if  the Jacobian [$]\nabla H = \Big( \partial_{u^i} H_j(u) \Big)[$] is a positive matrix. 

Let us test this view on the heat equation [$]\partial_t u = \Delta u[$] for a simple euler scheme [$]u^{n+1} = u^{n} + \delta_t \Delta^h u^n, \Delta^h[$] being your favorite discretization of the Laplacian, [$]\delta_t[$] a time step. The scheme is monotone provided that the matrix[$]I_d + \delta_t \Delta^h[$] is a positive matrix. If one takes for instance the classical difference scheme [$]\Delta^h = \frac{1}{\delta_x^2}(...,+1,-2,+1,...) [$] we get that the scheme is monotone if [$] \frac{\delta_t}{\delta_x^2} \le 1 [$], that is also the quite known CFL condition for the heat equation.
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 26th, 2020, 8:53 am

On suggestion from JohnLeM.

Always good to start with a definition,thus avoiding other alternate mental models

https://www.cfd-online.com/Wiki/Monotone_scheme
Some incentives towards monotone schemes that comes to my mind:
1) Stability: usually numerical schemes come with stationary solutions ([$]u=H(u)[$] with the notations above). Hence for every two ordered stationary solutions [$]u_1 \le u_2[$], the scheme [$]v = H(u)[$] is stable in the range [$]u_1 \le v \le u_2[$]
2) Markov interpretation: this is probably the most important property to my mind for Finance applications. A linear scheme ([$]v = H(x)u[$] with the notations above) that is monotone means [$]H_{i,j}(x) \ge 0[$]. If [$]H(x)[$] is stochastic (a common case), then the scheme [$]u^{n+1} = H(x)u^n[$] is basically a Markov chain for which the matrix [$]H(x)[$] can be interpreted as a probability transition matrix, each entry [$]H_{i,j}(x)[$] being the probability to jump from the state [$]x^i[$] to [$]x^j[$].

Other candidates nice properties
3) Not oscillating scheme: a linear scheme [$]v = H(x)u[$] that is monotone implies that the matrix [$]H(x)[$] has real, positive, eigenvalues. This property impeaches spurious oscillations, that are due to complex eigenvalues in [$]H(x)[$].
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 26th, 2020, 9:09 am

A question now that took me a while to answer: consider a numerical scheme built from a general construction as the Crank Nicolson approach. Then the scheme produced is not monotone. 

The question is: is it possible to modify slightly the Crank Nicolson approach to produce a monotone scheme ? The answer is yes, and it is not very hard. The resulting schemes enjoy moreover the nice original Crank Nicolson properties: unconditionally stables, energy dissipative (or conservative) schemes.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Monotone Schemes: what are they and why are they good?

September 28th, 2020, 10:13 am

The classico Crank Nicolson scheme is A-stable and not L-stable, in general the solution is

[$]AU^{n+1} = U^{n}[$] where A is ideally an M-matrix, making the scheme monotone. However, in the case of CN the matrix [$]A[$] can have complex eigenvalues. Well-known at this stage. We get oscillations in  the greeks.

unconditionally stables,
yes and no (A or L?)

My exponential fitting results in a monotone scheme with fully implicit, but CN destroys that property. I stumbled on this in 1974 when doing a FEM project. It took the industry a number of years before it saw the light of day in finance.

https://wwwf.imperial.ac.uk/~ajacquie/IC_Num_Methods/IC_Num_Methods_Docs/Literature/DuffyCN.pdf


See Lawson and Morris here

https://www.lexifi.com/quant/possible-s ... equations/

What is the magic modification? Do you resolve the problems here?

https://cs.uwaterloo.ca/research/tr/1977/CS-77-20.pdf
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 28th, 2020, 2:17 pm

unconditionally stables,
yes and no (A or L?)
Both. For instance consider the one-dimensional heat equation, and the notations above ([$]u_i^{n+1} \sim u(t^n,x^i)[$]). To be precise, there exists a finite-difference scheme [$]u^{n+1} = H u^{n}[$], H being a [$]I \times I[$] matrix having REAL eigenvalues, satisfying BOTH properties
1) monotonicity :  [$]\|u^{n+1}\|_\infty \le \|u^{n}\|_\infty[$]
2) conservative / dissipative : [$]\sum u_i^{n+1} = \sum u_i^{n}[$], [$]\sum (\delta_x u_i^{n+1})^2 \le \sum (\delta_x u_i^{n})^2[$]
[$]\delta_x u = \frac{u_{i+1}-u_{i}}{h}[$] being the forward difference operator.
In contrast : Crank Nicolson satisfies only 2), fully implicit satisfy only 1)

Both is better ! Indeed, as I solve heat-type equations in higher dimensions, I definitively need monotone conservative / dissipative schemes. I am using this small idea since 6/7 years now, it is a quite general and robust construction. In particular, I use it together with the RHKS approach described in our wilmott paper .

To my perception, it is a small enhancement of CN that I use. I thought this was known since decades, but I never checked. Since Vivien Begot wrote on this topic in 2012, could it be unknown ? I could write some pages on this topic if you find the idea interesting.
Last edited by JohnLeM on September 28th, 2020, 3:04 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Monotone Schemes: what are they and why are they good?

September 28th, 2020, 2:43 pm

Point 1) is stability in some norm, it has nothing to do with monotone scheme which is one that satisfies maximum principle.

See here

https://www.researchgate.net/publicatio ... _Equations

I worked it out in my PhD thesis all them years ago.
Attachments
From Navier-Stokes to Black-Scholes Numerical Methods in Computational Finance.pdf
(87.78 KiB) Downloaded 130 times
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Monotone Schemes: what are they and why are they good?

September 28th, 2020, 2:53 pm

Can you write down the precise 'ehancements'? e.g. for heat equation and then BS?
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 28th, 2020, 3:15 pm

Point 1) is stability in some norm, it has nothing to do with monotone scheme which is one that satisfies maximum principle.
Yes you are right in a general context. However this stability property is equivalent to monotonicity for finite-difference schemes for the heat equations. Anyhow, I just meant monotone in the sense above: H has real eigenvalues.

Can you write down the precise 'ehancements'? e.g. for heat equation and then BS?
Ok ok, I'll send the math to your datasim address to have your feedback on it.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Monotone Schemes: what are they and why are they good?

September 28th, 2020, 4:21 pm

Thanks!

BTW have you noticed how quiet it is here! Where have all the flowers gone?

www.youtube.com/watch?v=Zy9aB4WrgqM
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 29th, 2020, 7:13 am

Thanks!

BTW have you noticed how quiet it is here! Where have all the flowers gone?

www.youtube.com/watch?v=Zy9aB4WrgqM
You are right ! Might it be a side-effect of artificial quantum intelligence and economical slump, dragging out young brains to twilight zone ?
 
User avatar
jherekhealy
Posts: 20
Joined: December 11th, 2017, 2:25 pm

Re: Monotone Schemes: what are they and why are they good?

September 29th, 2020, 9:08 am

The Crank-Nicolson scheme becomes monotone for small enough time-steps (in relation to the space-steps ^2). Either the limit corresponds to the explicit scheme stability limit or to twice the latter, I don't remember exactly.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Monotone Schemes: what are they and why are they good?

September 29th, 2020, 10:02 am

The Crank-Nicolson scheme becomes monotone for small enough time-steps (in relation to the space-steps ^2). Either the limit corresponds to the explicit scheme stability limit or to twice the latter, I don't remember exactly.

It's not possible to be "half pregnant".
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 29th, 2020, 12:19 pm

The Crank-Nicolson scheme becomes monotone for small enough time-steps (in relation to the space-steps ^2). Either the limit corresponds to the explicit scheme stability limit or to twice the latter, I don't remember exactly.
Hélas non :/ Crank Nicolson approach always produces non monotone schemes. To experience them: take the Crank Nicolson scheme for the heat equation, with a nasty initial condition, as heavyside (u_0(x) = 0, x<0, +1, x >0}. You should see oscillations whatever the time step is. But it is true that oscillations are damped out with smaller time step.
 
User avatar
JohnLeM
Posts: 379
Joined: September 16th, 2008, 7:15 pm

Re: Monotone Schemes: what are they and why are they good?

September 29th, 2020, 12:36 pm

Can you write down the precise 'ehancements'? e.g. for heat equation and then BS?
I started to work on it. I need a half day more to finish a first readable draft. I hope you will receive it at end of this week !