Serving the Quantitative Finance Community

 
User avatar
Mars
Posts: 115
Joined: November 13th, 2002, 5:10 pm

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

September 29th, 2020, 2:38 pm

Am I missing something or in Crank Nicolson oscillations come when H (or A in the Daniel post) got real but NEGATIVE eigenvalues (for the high frequency eigenvectors)?
 
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?

September 29th, 2020, 4:26 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.
100%
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
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?

September 29th, 2020, 4:44 pm

Am I missing something or in Crank Nicolson oscillations come when H (or A in the Daniel post) got real but NEGATIVE eigenvalues (for the high frequency eigenvectors)?
No, complex eigenvalues! See Strang and Fix 1974, Lawson and Morris 1978 for a full answer.
There was a time (until I came along) that no one talked about CN oscillations ;-) aka denial.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
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?

September 29th, 2020, 4:49 pm

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

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
Mars
Posts: 115
Joined: November 13th, 2002, 5:10 pm

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

September 30th, 2020, 8:36 am

Am I missing something or in Crank Nicolson oscillations come when H (or A in the Daniel post) got real but NEGATIVE eigenvalues (for the high frequency eigenvectors)?
No, complex eigenvalues! See Strang and Fix 1974, Lawson and Morris 1978 for a full answer.
There was a time (until I came along) that no one talked about CN oscillations ;-) aka denial.
When I look in the Lawson and Morris article you provide, just below eq 1.7 there is a discussion where the oscillation is linked to the negative (close to -1) eigenvalues when timestep is too large. The problem studied is heat equation, without first order derivatives the coefficient below and above the diagonal are the same, so the eigenvalues of the tridiagonal toeplitz matrix H are real.
Adding convection (first order derivative) can bring convection dominance. When coefficient below and above the diagonal are of opposite sign you will have complex eigenvalues but not with heat equation as far as I understand the problem.
 
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?

September 30th, 2020, 8:46 am

Am I missing something or in Crank Nicolson oscillations come when H (or A in the Daniel post) got real but NEGATIVE eigenvalues (for the high frequency eigenvectors)?
No, complex eigenvalues! See Strang and Fix 1974, Lawson and Morris 1978 for a full answer.
There was a time (until I came along) that no one talked about CN oscillations ;-) aka denial.
When I look in the Lawson and Morris article you provide, just below eq 1.7 there is a discussion where the oscillation is linked to the negative (close to -1) eigenvalues when timestep is too large. The problem studied is heat equation, without first order derivatives the coefficient below and above the diagonal are the same, so the eigenvalues of the tridiagonal toeplitz matrix H are real.
Adding convection (first order derivative) can bring convection dominance. When coefficient below and above the diagonal are of opposite sign you will have complex eigenvalues but not with heat equation as far as I understand the problem.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
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?

September 30th, 2020, 8:50 am

Use my exponential fitting to give M-matrix [$]A[$] leading to monotone FDM.
This is all well-known at this stage. 

https://en.wikipedia.org/wiki/M-matrix
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl
 
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?

September 30th, 2020, 11:06 am

Mars,
The most mathematically rigorous approach to stability is via continuous and discrete maximum principle as here (Lemmas 1, 2). No need for (in this case) erroneous discrete Fourier or eigenvalue analysis. This is the way it should be done.
Attachments
DuffyExponentialFitting.pdf
(234.26 KiB) Downloaded 44 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?

September 30th, 2020, 4:23 pm


When I look in the Lawson and Morris article you provide, just below eq 1.7 there is a discussion where the oscillation is linked to the negative (close to -1) eigenvalues when timestep is too large. The problem studied is heat equation, without first order derivatives the coefficient below and above the diagonal are the same, so the eigenvalues of the tridiagonal toeplitz matrix H are real.
Adding convection (first order derivative) can bring convection dominance. When coefficient below and above the diagonal are of opposite sign you will have complex eigenvalues but not with heat equation as far as I understand the problem.
Lawson and Morris conducted mainly a Fourier analysis in eq 1.7 and below. You are right, the matrix A has positive real eigenvalues. However the propagator resulting from the CN discretization is [$](I_d + \tau A)^{-1}(I_d - \tau A)[$]. This is the matrix we are talking about having complex eigenvalues. 
 
User avatar
Mars
Posts: 115
Joined: November 13th, 2002, 5:10 pm

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

October 1st, 2020, 7:49 am


When I look in the Lawson and Morris article you provide, just below eq 1.7 there is a discussion where the oscillation is linked to the negative (close to -1) eigenvalues when timestep is too large. The problem studied is heat equation, without first order derivatives the coefficient below and above the diagonal are the same, so the eigenvalues of the tridiagonal toeplitz matrix H are real.
Adding convection (first order derivative) can bring convection dominance. When coefficient below and above the diagonal are of opposite sign you will have complex eigenvalues but not with heat equation as far as I understand the problem.
Lawson and Morris conducted mainly a Fourier analysis in eq 1.7 and below. You are right, the matrix A has positive real eigenvalues. However the propagator resulting from the CN discretization is [$](I_d + \tau A)^{-1}(I_d - \tau A)[$]. This is the matrix we are talking about having complex eigenvalues. 
I do not agree, if [$] \lambda_i[$] are thre eigenvalues of [$]A[$] then [$]\frac{1 - \lambda_i}{1 + \lambda_i}[$] are the eigenvalues of  [$](I_d + \tau A)^{-1}(I_d - \tau A)[$].  You will have complex eigenvalues for the second one only when [$] A [$] got complex eigenvalues and (with constant coefficients and constant space step) it will only happen with convection dominance. The Exponential fitting is a solution to avoid that.
My point is that with heat equation as in the Lawson Morris article, or in the example you provide with heaviside function, or in the Peter Jaeckel analysis https://jaeckel.000webhostapp.com/Finit ... imants.pdf (and reference therein) there are spurious oscillations without complex eigenvalues. The problem happen when amplification factor is close to -1.  
 
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 1st, 2020, 9:51 am

There are two orthogonal issues here

1. Convection-dominance (got to do with cell Peclet/Reynolds number..)
2. (Discontinuous) initial condition in interior of domain and their smoothing as time goes by.
3. ! Discontinuity between boundary and initial conditions at corners.

Only 1 has to do with monotonicity.

// Looking at eigenvalues is only for simple pdes. The maximum principle is more mathematically elegant and general.
"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 2nd, 2020, 7:17 am

I do not agree, if [$] \lambda_i[$] are thre eigenvalues of [$]A[$] then [$]\frac{1 - \lambda_i}{1 + \lambda_i}[$] are the eigenvalues of  [$](I_d + \tau A)^{-1}(I_d - \tau A)[$].  
Let us suppose that you missed a [$]\tau[$] here. So there exists eigenvectors [$] v^i [$] such that [$]v^i(\tau) = (I_d + \tau A)^{-1}(I_d - \tau A) v^i = \frac{1 -  \tau \lambda_i}{1 + \tau \lambda_i} v^i[$], with  [$]\lambda_i > 0[$]?
Thus [$]\sum_n v^i_n(\tau) = \frac{1 -  \tau \lambda_i}{1 + \tau \lambda_i} \sum_n v_n^i(\tau) < \sum_n v^i_n[$] ? 

However the CN scheme can be written as [$]\frac{u^{n+1}-u^{n}}{\tau} = A \frac{u^{n+1}+u^{n}}{2}[$], satisfying [$]\sum_n u_i^{n+1} = \sum_n u_i^{n}[$]. It seems to lead to a contradiction ?

Maybe there is a confusion here : [$](I_d + \tau A)^{-1}(I_d - \tau A) \neq f(A)[$], where [$]f(x) = \frac{1-\tau x}{1 + \tau x}[$]

Another possibility to explain the misunderstanding: we might not consider the same equations. For finance applications, it is important to preserve expectations, i.e.  [$]\sum_n u_i^{n+1} = \sum_n u_i^{n}[$]. What you are saying might be correct if we consider heat equation with null boundary Dirichlet conditions at boundaries, for which the solution damp to zero.
 
User avatar
Mars
Posts: 115
Joined: November 13th, 2002, 5:10 pm

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

October 2nd, 2020, 8:27 am

I do not agree, if [$] \lambda_i[$] are thre eigenvalues of [$]A[$] then [$]\frac{1 - \lambda_i}{1 + \lambda_i}[$] are the eigenvalues of  [$](I_d + \tau A)^{-1}(I_d - \tau A)[$].  
Let us suppose that you missed a [$]\tau[$] here. So there exists eigenvectors [$] v^i [$] such that [$]v^i(\tau) = (I_d + \tau A)^{-1}(I_d - \tau A) v^i = \frac{1 -  \tau \lambda_i}{1 + \tau \lambda_i} v^i[$], with  [$]\lambda_i > 0[$]?
Thus [$]\sum_n v^i_n(\tau) = \frac{1 -  \tau \lambda_i}{1 + \tau \lambda_i} \sum_n v_n^i(\tau) < \sum_n v^i_n[$] ? 

However the CN scheme can be written as [$]\frac{u^{n+1}-u^{n}}{\tau} = A \frac{u^{n+1}+u^{n}}{2}[$], satisfying [$]\sum_n u_i^{n+1} = \sum_n u_i^{n}[$]. It seems to lead to a contradiction ?

Maybe there is a confusion here : [$](I_d + \tau A)^{-1}(I_d - \tau A) \neq f(A)[$], where [$]f(x) = \frac{1-\tau x}{1 + \tau x}[$]

Another possibility to explain the misunderstanding: we might not consider the same equations. For finance applications, it is important to preserve expectations, i.e.  [$]\sum_n u_i^{n+1} = \sum_n u_i^{n}[$]. What you are saying might be correct if we consider heat equation with null boundary Dirichlet conditions at boundaries, for which the solution damp to zero.
Yes in the previous post I miss the [$] \tau [$], but for the remaining I do not agree : once you got [$]A v = \lambda v[$] then [$]v[$] is an eigenvector of [$](I_d + \tau A)^{-1}(I_d - \tau A) [$] with eigenvalue [$]\frac{1 - \tau \lambda}{1 + \tau \lambda} [$] (not considering the pathological case  [$]1 + \tau \lambda = 0[$]). It will also be true for a function [$]f(A)[$] when it is a rational function.
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 2nd, 2020, 11:20 am

I do not agree, if [$] \lambda_i[$] are thre eigenvalues of [$]A[$] then [$]\frac{1 - \lambda_i}{1 + \lambda_i}[$] are the eigenvalues of  [$](I_d + \tau A)^{-1}(I_d - \tau A)[$].  
Let us suppose that you missed a [$]\tau[$] here. So there exists eigenvectors [$] v^i [$] such that [$]v^i(\tau) = (I_d + \tau A)^{-1}(I_d - \tau A) v^i = \frac{1 -  \tau \lambda_i}{1 + \tau \lambda_i} v^i[$], with  [$]\lambda_i > 0[$]?
Thus [$]\sum_n v^i_n(\tau) = \frac{1 -  \tau \lambda_i}{1 + \tau \lambda_i} \sum_n v_n^i(\tau) < \sum_n v^i_n[$] ? 

However the CN scheme can be written as [$]\frac{u^{n+1}-u^{n}}{\tau} = A \frac{u^{n+1}+u^{n}}{2}[$], satisfying [$]\sum_n u_i^{n+1} = \sum_n u_i^{n}[$]. It seems to lead to a contradiction ?

Maybe there is a confusion here : [$](I_d + \tau A)^{-1}(I_d - \tau A) \neq f(A)[$], where [$]f(x) = \frac{1-\tau x}{1 + \tau x}[$]

Another possibility to explain the misunderstanding: we might not consider the same equations. For finance applications, it is important to preserve expectations, i.e.  [$]\sum_n u_i^{n+1} = \sum_n u_i^{n}[$]. What you are saying might be correct if we consider heat equation with null boundary Dirichlet conditions at boundaries, for which the solution damp to zero.
Yes in the previous post I miss the [$] \tau [$], but for the remaining I do not agree : once you got [$]A v = \lambda v[$] then [$]v[$] is an eigenvector of [$](I_d + \tau A)^{-1}(I_d - \tau A) [$] with eigenvalue [$]\frac{1 - \tau \lambda}{1 + \tau \lambda} [$] (not considering the pathological case  [$]1 + \tau \lambda = 0[$]). It will also be true for a function [$]f(A)[$] when it is a rational function.
Ok, I think that you are right now and that I am wrong. Complex eigenvalues comes from advection discretization, leading to non-symetric A. It does not seem to appear with symmetric semi-definite positive matrix A.
 
User avatar
JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

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

October 2nd, 2020, 5:33 pm

Following Mars objection, I also checked my answer to jherekhealy. I tested on a very simple example: whatever tau is, I obtain a non monotone scheme (the matrix (I-\tau A)^{-1}(I+\tau A) has some negative entries). Excel sheet here for those who want to toy with it