BackwardEuler

[Gilbert Peffer]

It's quite a rollercoaster ride for the uninitiated, those templates and
operators :). My first question about the BackwardEuler class is: Why does
the constructor take an operatortype as an argument if backward Euler should
implement D_?
Gilbert

[Luigi Ballabio-3]

At 07:14 PM 7/4/01 +0200, Gilbert Peffer wrote:
>It's quite a rollercoaster ride for the uninitiated, those templates and
>operators :).

I agree. Sorry for it. To better understand what the thing does, I suggest
to disregard the #if QL_TEMPLATE_METAPROGRAMMING_WORKS clause and look at
the #else clause instead. Now that I look back at the thing after a while
since I've writter it, I'm actually thinking of removing this particular
metaprogramming trick (it's not that it improves efficiency or anything...)

>My first question about the BackwardEuler class is: Why does
>the constructor take an operatortype as an argument if backward Euler should
>implement D_?

Hmm. Maybe you are thinking of some particular problem called backward
Euler as well. Or maybe the name "D" was an unhappy choice for the operator
name, since it seems to suggest that we're talking of a simple first
derivative. This tells me I have to go and add some more documentation to
the thing.

In the meantime, I'd have to e-mail you a blackboard here... I'll try to
make do with pseudo-LaTeX. If you (or anyone else) can't read or compile
it, drop me a line and I'll try and send the thing as a PDF.

Also, apologies in advance if I'm repeating things you probably know
already, but they may be of interest to other people on the list.

BackwardEuler, ForwardEuler and CrankNicolson classes are meant to help
solving a differential equation
\frac{\partial f}{\partial t} = Lf
where L is a _generic_ differential operator in space, i.e., no
partial derivatives in t - the only one in the equation is the one on the
left hand side - but any other derivative in x, y or constant coefficients
you like. For instance, you can write the Black-Scholes equation in the
above form and L would be the differential operator
L = - \frac{\sigma^2}{2} \frac{\partial^2}{\partial x^2}
     - \nu \frac{\partial}{\partial x}
     + r I
which you can discretize using either D_+, D_-, D_0, etc. For instance,
QuantLib::FiniteDifferences::BSMOperator uses D_0 for the first derivative
and D_+D_- for the second derivative.

The point of BackwardEuler, ForwardEuler and CrankNicolson is: we
determined what L is and discretized it (this is done outside such classes
- that is why L is passed as a constructor argument). Now, how do we go
about discretizing the time derivative? These three classes correspond to
three well-known methods, namely: for all three, we write \frac{\partial
f}{\partial t} at time t_k as \frac{f^{(k+1)}-f^{(k)}}{\Delta t};

for forward Euler, we write the rhs as Lf^{(k)} and end up with
f^{(k+1)} = (I + \Delta t L) f^{(k)}
which explicitly gives f at next time step;

for backward Euler, we write the rhs as Lf^{(k+1)} and end up with
(I - \Delta t L) f^{(k+1)} = f^{(k)}
which implicitly gives f at next time step (we'll have to solve a linear
system, instead of simply applying the operator);

for Crank-Nicolson, we write the rhs as L \frac{f^{(k+1)}+f^{(k)}}{2} and
end up with
\left( I - \frac{\Delta t}{2} L \right) f^{(k+1)} =
\left( I + \frac{\Delta t}{2} L \right) f^{(k)}
which is another implicit method - sligtly more complex, but usually more
stable.

Oh, yes, I wrote the above assuming that time flows forwards - physicists
often do :) The algebraic signs might be different in the classes since
option pricing is done backwards.

In short, they embody the discretization of the time derivative - and of it
only. The discretization of the space derivatives are up to you (you can
either write your operator by hand, or compose the ones already available
such as D_0), and that's why the operator is passed to the constructor.

Hope this helped (and was readable at all),
                         Luigi

[Gilbert Peffer]

Aaah...  OK, so Operator in the template definition of BackwardEuler refers
to the space (or whatever, but not time) operator. Got it, thanks.
Gilbert

>-----Mensaje original-----
>De: Luigi Ballabio [mailto:[hidden email]]
>Enviado el: 05 July 2001 12:33
>Para: Gilbert Peffer; QuantLibUsers
>Asunto: Re: [Quantlib-users] BackwardEuler
>
>
>At 07:14 PM 7/4/01 +0200, Gilbert Peffer wrote:
>>It's quite a rollercoaster ride for the uninitiated, those templates and
>>operators :).
>
>I agree. Sorry for it. To better understand what the thing does, I suggest
>to disregard the #if QL_TEMPLATE_METAPROGRAMMING_WORKS clause and look at
>the #else clause instead. Now that I look back at the thing after a while
>since I've writter it, I'm actually thinking of removing this particular
>metaprogramming trick (it's not that it improves efficiency or anything...)
>
>>My first question about the BackwardEuler class is: Why does
>>the constructor take an operatortype as an argument if backward
>Euler should
>>implement D_?
>
>Hmm. Maybe you are thinking of some particular problem called backward
>Euler as well. Or maybe the name "D" was an unhappy choice for the
>operator
>name, since it seems to suggest that we're talking of a simple first
>derivative. This tells me I have to go and add some more documentation to
>the thing.
>
>In the meantime, I'd have to e-mail you a blackboard here... I'll try to
>make do with pseudo-LaTeX. If you (or anyone else) can't read or compile
>it, drop me a line and I'll try and send the thing as a PDF.
>
>Also, apologies in advance if I'm repeating things you probably know
>already, but they may be of interest to other people on the list.
>
>BackwardEuler, ForwardEuler and CrankNicolson classes are meant to help
>solving a differential equation
>\frac{\partial f}{\partial t} = Lf
>where L is a _generic_ differential operator in space, i.e., no
>partial derivatives in t - the only one in the equation is the one on the
>left hand side - but any other derivative in x, y or constant coefficients
>you like. For instance, you can write the Black-Scholes equation in the
>above form and L would be the differential operator
>L = - \frac{\sigma^2}{2} \frac{\partial^2}{\partial x^2}
>     - \nu \frac{\partial}{\partial x}
>     + r I
>which you can discretize using either D_+, D_-, D_0, etc. For instance,
>QuantLib::FiniteDifferences::BSMOperator uses D_0 for the first derivative
>and D_+D_- for the second derivative.
>
>The point of BackwardEuler, ForwardEuler and CrankNicolson is: we
>determined what L is and discretized it (this is done outside such classes
>- that is why L is passed as a constructor argument). Now, how do we go
>about discretizing the time derivative? These three classes correspond to
>three well-known methods, namely: for all three, we write \frac{\partial
>f}{\partial t} at time t_k as \frac{f^{(k+1)}-f^{(k)}}{\Delta t};
>
>for forward Euler, we write the rhs as Lf^{(k)} and end up with
>f^{(k+1)} = (I + \Delta t L) f^{(k)}
>which explicitly gives f at next time step;
>
>for backward Euler, we write the rhs as Lf^{(k+1)} and end up with
>(I - \Delta t L) f^{(k+1)} = f^{(k)}
>which implicitly gives f at next time step (we'll have to solve a linear
>system, instead of simply applying the operator);
>
>for Crank-Nicolson, we write the rhs as L \frac{f^{(k+1)}+f^{(k)}}{2} and
>end up with
>\left( I - \frac{\Delta t}{2} L \right) f^{(k+1)} =
>\left( I + \frac{\Delta t}{2} L \right) f^{(k)}
>which is another implicit method - sligtly more complex, but usually more
>stable.
>
>Oh, yes, I wrote the above assuming that time flows forwards - physicists
>often do :) The algebraic signs might be different in the classes since
>option pricing is done backwards.
>
>In short, they embody the discretization of the time derivative -
>and of it
>only. The discretization of the space derivatives are up to you (you can
>either write your operator by hand, or compose the ones already available
>such as D_0), and that's why the operator is passed to the constructor.
>
>Hope this helped (and was readable at all),
>                         Luigi
>