Serving the Quantitative Finance Community

Cuchulainn
Topic Author
Posts: 64439
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

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

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
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

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.

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

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)$.

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

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.

Cuchulainn
Topic Author
Posts: 64439
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

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

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
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

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.

Cuchulainn
Topic Author
Posts: 64439
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

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

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
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Cuchulainn
Topic Author
Posts: 64439
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

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

Can you write down the precise 'ehancements'? e.g. for heat equation and then BS?
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

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?

Cuchulainn
Topic Author
Posts: 64439
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

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

Thanks!

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

"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

Thanks!

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

You are right ! Might it be a side-effect of artificial quantum intelligence and economical slump, dragging out young brains to twilight zone ?

jherekhealy
Posts: 18
Joined: December 11th, 2017, 2:25 pm

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

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.

Cuchulainn
Topic Author
Posts: 64439
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

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

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".
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

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.

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

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 !