Serving the Quantitative Finance Community

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

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

October 5th, 2020, 8:29 am

@Cuchulain I was rereading your exponential fitting paper. As far as I understand, you produce a monotone scheme using a pertinent change of variable of the mesh itself. This change of variable ensures that the discretization of the advection terms are dominated by the diffusion ones. Technically, you end writing a M-matrix to conclude. Is that correct ?
 
User avatar
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?

October 5th, 2020, 8:59 am

@Cuchulain I was rereading your exponential fitting paper. As far as I understand, you produce a monotone scheme using a pertinent change of variable of the mesh itself. This change of variable ensures that the discretization of the advection terms are dominated by the diffusion ones. Technically, you end writing a M-matrix to conclude. Is that correct ?
Not exactly.
We use a modified diffusion term.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 5th, 2020, 9:05 am

@Cuchulain I was rereading your exponential fitting paper. As far as I understand, you produce a monotone scheme using a pertinent change of variable of the mesh itself. This change of variable ensures that the discretization of the advection terms are dominated by the diffusion ones. Technically, you end writing a M-matrix to conclude. Is that correct ?
Not exactly.
We use a modified diffusion term.
Is it the diffusion term is denoted [$]D^+D^-[$] in your paper ? Isn't it a standard discretization of second order derivative on non uniform grid ?
 
User avatar
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?

October 5th, 2020, 9:13 am

@Cuchulain I was rereading your exponential fitting paper. As far as I understand, you produce a monotone scheme using a pertinent change of variable of the mesh itself. This change of variable ensures that the discretization of the advection terms are dominated by the diffusion ones. Technically, you end writing a M-matrix to conclude. Is that correct ?
Not exactly.
We use a modified diffusion term.
Is it the diffusion term is denoted [$]D^+D^-[$] in your paper ? Isn't it a standard discretization of second order derivative on non uniform grid ?
You're guessing! please do a bit of research.
Exponential fitting A-Z is described here, RTFM in bocca al lupo!
Attachments
DuffyExponentialFitting.pdf
(234.26 KiB) Downloaded 36 times
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 5th, 2020, 10:15 am



Not exactly.
We use a modified diffusion term.
Is it the diffusion term is denoted [$]D^+D^-[$] in your paper ? Isn't it a standard discretization of second order derivative on non uniform grid ?
You're guessing! please do a bit of research.
Exponential fitting A-Z is described here, RTFM in bocca al lupo!
I read quickly. You define the fitting factor in (31), the full scheme is at (33). (34) shows that the scheme is consistent with the equation
[$]\sigma_h u'' + \mu u' = 0[$] (forget the others terms), [$]\sigma_h \sim \sigma + \frac{\mu^2 h^2}{\sigma}[$]
This might cause problems as [$]\sigma \mapsto 0[$] ?
 
User avatar
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?

October 5th, 2020, 11:07 am


Is it the diffusion term is denoted [$]D^+D^-[$] in your paper ? Isn't it a standard discretization of second order derivative on non uniform grid ?
You're guessing! please do a bit of research.
Exponential fitting A-Z is described here, RTFM in bocca al lupo!
I read quickly. You define the fitting factor in (31), the full scheme is at (33). (34) shows that the scheme is consistent with the equation
[$]\sigma_h u'' + \mu u' = 0[$] (forget the others terms), [$]\sigma_h \sim \sigma + \frac{\mu^2 h^2}{\sigma}[$]
This might cause problems as [$]\sigma \mapsto 0[$] ?
RTFM  :mrgreen:
Section 5.4 (Graceful degradation) ... upwinding QED.

I read quickly
Not a good idea. I really don' have time to explain that have already been documented. It's time wastage.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 5th, 2020, 12:14 pm



You're guessing! please do a bit of research.
Exponential fitting A-Z is described here, RTFM in bocca al lupo!
I read quickly. You define the fitting factor in (31), the full scheme is at (33). (34) shows that the scheme is consistent with the equation
[$]\sigma_h u'' + \mu u' = 0[$] (forget the others terms), [$]\sigma_h \sim \sigma + \frac{\mu^2 h^2}{\sigma}[$]
This might cause problems as [$]\sigma \mapsto 0[$] ?
RTFM  :mrgreen:
Section 5.4 (Graceful degradation) ... upwinding QED.

I read quickly
Not a good idea. I really don' have time to explain that have already been documented. It's time wastage.
You could also feel empathy for another mathematician that is interested by your work and is struggling to analyze it :)
 
A small error in your paper : I compute that the function [$](h,a) \mapsto h coth{\frac{h}{a}}[$] has the limit [$]\lim_{a \mapsto 0} (h,a) =h[$] that does not seem to be the one computed in your paper section 5.4 (you computed +1, not +h). Don't worry, it seems to be ok while inserting into the equations (48), I retrieve the upwind scheme.

I understand the construction that you made here, but I do wonder what is behind. A good point is that you retrieve a monotone scheme whatever the diffusive part is. The price to pay for that is to loose all nice properties of Crank Nicolson.
 
User avatar
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?

October 5th, 2020, 4:03 pm

That paper was from 1998, so it was corrected in my later books.
I am a trainer so I expect you to read what I post :-) Especially stuff I invented.

One way to get monotonicity without fitting is to use use upwinding in convection.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 5th, 2020, 4:34 pm

That paper was from 1998, so it was corrected in my later books.
I am a trainer so I expect you to read what I post :-) Especially stuff I invented.

One way to get monotonicity without fitting is to use use upwinding in convection.
Another way is to split the equation : move the grid according to the advection equation. Then solve an auto-adjoint problem similar to the heat equation, for which monotoniticy is an easy task. Doing so one does not destroy the nice properties of CN and can interpret the diffusion as a Markov chain. 
 
User avatar
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?

October 5th, 2020, 6:34 pm

That paper was from 1998, so it was corrected in my later books.
I am a trainer so I expect you to read what I post :-) Especially stuff I invented.

One way to get monotonicity without fitting is to use use upwinding in convection.
Another way is to split the equation : move the grid according to the advection equation. Then solve an auto-adjoint problem similar to the heat equation, for which monotoniticy is an easy task. Doing so one does not destroy the nice properties of CN and can interpret the diffusion as a Markov chain. 
Looks like overkill. What's the story about Markov??
There are several methods >> CN around.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 5th, 2020, 7:19 pm

That paper was from 1998, so it was corrected in my later books.
I am a trainer so I expect you to read what I post :-) Especially stuff I invented.

One way to get monotonicity without fitting is to use use upwinding in convection.
Another way is to split the equation : move the grid according to the advection equation. Then solve an auto-adjoint problem similar to the heat equation, for which monotoniticy is an easy task. Doing so one does not destroy the nice properties of CN and can interpret the diffusion as a Markov chain. 
Looks like overkill. What's the story about Markov??
There are several methods >> CN around.
Overkill is the only way at my disposal to tackle efficiently high dimensional problems.

For Markov: you can interpret a scheme as a Markov Chain provided u^{n+1}=Au^n, A stochastic matrix (a monotone scheme is necessary, but not sufficient. You need conservative properties). If you consider a heat equation with advection through exponential fitting or upwind, A is no longer stochastic. You can't anymore interpret your equation as a Markov chain. But, we really need a Markov interpretation for PDE pricing, for instance if  one want to price Asian type options or Autocalls.
 
User avatar
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?

October 6th, 2020, 1:26 pm


Another way is to split the equation : move the grid according to the advection equation. Then solve an auto-adjoint problem similar to the heat equation, for which monotoniticy is an easy task. Doing so one does not destroy the nice properties of CN and can interpret the diffusion as a Markov chain. 
Looks like overkill. What's the story about Markov??
There are several methods >> CN around.
Overkill is the only way at my disposal to tackle efficiently high dimensional problems.

For Markov: you can interpret a scheme as a Markov Chain provided u^{n+1}=Au^n, A stochastic matrix (a monotone scheme is necessary, but not sufficient. You need conservative properties). If you consider a heat equation with advection through exponential fitting or upwind, A is no longer stochastic. You can't anymore interpret your equation as a Markov chain. But, we really need a Markov interpretation for PDE pricing, for instance if  one want to price Asian type options or Autocalls.
I would need a bit more convincing on that one.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 6th, 2020, 1:53 pm


Looks like overkill. What's the story about Markov??
There are several methods >> CN around.
Overkill is the only way at my disposal to tackle efficiently high dimensional problems.

For Markov: you can interpret a scheme as a Markov Chain provided u^{n+1}=Au^n, A stochastic matrix (a monotone scheme is necessary, but not sufficient. You need conservative properties). If you consider a heat equation with advection through exponential fitting or upwind, A is no longer stochastic. You can't anymore interpret your equation as a Markov chain. But, we really need a Markov interpretation for PDE pricing, for instance if  one want to price Asian type options or Autocalls.
I would need a bit more convincing on that one.
easy: consider simply the upwind scheme and try to deduce transition probabilities from it. [$]u_i^{n+1}=u_i^{n} -\frac{dt}{dx}(u_{i+1}^{n} - u_{i}^{n})[$] gives [$] A = (..0,1+\frac{dt}{dx},-\frac{dt}{dx},0...)[$]. You get one negative entries and the diagonal is greater than one, this is not a stochastic matrix. If you consider a backward difference, this is better, but boundary conditions will ruin it. If you move the mesh, you get [$]u_i^{n+1}=u_i^{n}, A = I_d[$], a beautiful stochastic matrix. Hence : if the exponential fitting degenerates as an upwind scheme, I can't use it straightforwardly - unless there are some trick to recover a stochastic matrix from it.

By the way, moving the mesh is very classical in Finance: all binomial and trinomial trees based technology uses it. Tree methods are more popular than FD ones, precisely because the Markov interpretation is very clear in a tree. They have a clear financial meaning, that any practioner, even if he does not know anything about PDE, can feel.

Above research, in an industrial context, a skilled quant practionner should ask you : "is your pricing martingale ?" - you can't imagine the number of time this question has been asked concerning my methods- If the guy that developed the pricer is not able to exhibit a stochastic matrix at this stage, you have no chance to sell it.
 
User avatar
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?

October 7th, 2020, 7:27 am

Your scheme above

[$]u_i^{n+1}=u_i^{n} -\frac{dt}{dx}(u_{i+1}^{n} - u_{i}^{n})[$] 

is unconditionally unstable (use von Nemann discrete Fourier analysis) if we take (de facto standard) forward time [$]t > 0[$]. But maybe you mean something else (e.g. the confusing  'binomial' way [$]t < T[$] in this context).

Even if we get the FDM 'right' you need to satisfy CFL (Courant-Friedrichs-Lewy) constraint [$]\Delta t/\Delta x < 1[$].I have removed this constraint in my 2018 C++ book (p. 748) and it is unconditionally stable.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 7th, 2020, 7:35 am

Your scheme above

[$]u_i^{n+1}=u_i^{n} -\frac{dt}{dx}(u_{i+1}^{n} - u_{i}^{n})[$] 

is unconditionally unstable (use von Nemann discrete Fourier analysis) if we take (de facto standard) forward time [$]t > 0[$]. But maybe you mean something else (e.g. the confusing  'binomial' way [$]t < T[$] in this context).

Even if we get the FDM 'right' you need to satisfy CFL (Courant-Friedrichs-Lewy) constraint [$]\Delta t/\Delta x < 1[$].I have removed this constraint in my 2018 C++ book (p. 748) and it is unconditionally stable.
Yes you are right. So let us write this scheme properly:
[$]u_i^{n+1}=u_i^{n} +\frac{dt}{dx}(u_{i+1}^{n} - u_{i}^{n})[$] gives [$] A = (..0,1-\frac{dt}{dx},+\frac{dt}{dx},0...)[$], and of course [$]\frac{dt}{dx} \le 1[$]. This is still not a stochastic matrix due to boundary conditions, one can see this without writing math picking up [$]dt = dx[$] : the last line must be zero, not summing to one. My guess is that it can't be stochastic if the mesh is fixed.