Tradable Schemes
CWI
P.O.~Box 94079
1090 GB Amsterdam
The Netherlands
In this article we present a new approach to the numerical valuation of derivative securities. The method is based on our previous work where we formulated the theory of pricing in terms of tradables. The basic idea is to fit a finite difference scheme to exact solutions of the pricing PDE. This can be done in a very elegant way, due to the fact that in our tradable based formulation there appear no drift terms in the PDE. We construct a mixed scheme based on this idea and apply it to price various types of arithmetic Asian options, as well as plain vanilla options (both european and american style) on stocks paying known cash dividends. We find prices which are accurate to $\sim 0.1\%$ in about 10ms on a Pentium 233MHz computer and to $\sim 0.001\%$ in a second. The scheme can also be used for market conform pricing, by fitting it to observed option prices.
cond-mat0009042.tex
\documentclass{article}
\usepackage{amsmath}

% short cuts
\renewcommand{\a}{\alpha} 
\renewcommand{\b}{\beta}
\newcommand{\g}{\gamma} 
\newcommand{\G}{\Gamma}
\renewcommand{\d}{\delta} 
\newcommand{\D}{\Delta}
\renewcommand{\k}{\kappa} 
\renewcommand{\l}{\lambda} 
\renewcommand{\L}{\Lambda} 
\newcommand{\m}{\mu} 
\newcommand{\n}{\nu}
\newcommand{\p}{\pi} 
\renewcommand{\r}{\rho} 
\newcommand{\s}{\sigma}
\renewcommand{\S}{\Sigma} 
\renewcommand{\sb}{\bar{\sigma}}
\renewcommand{\t}{\tau} 
\renewcommand{\O}{\Omega}

\newcommand{\tm}{\tilde{\mu}}
\newcommand{\tP}{\tilde{P}}
\newcommand{\tx}{\tilde{x}}
\newcommand{\ty}{\tilde{y}}
\newcommand{\tz}{\tilde{z}}
\newcommand{\tV}{\tilde{V}}
\newcommand{\ts}{\tilde{\sigma}}

\newcommand{\cF}{{\cal F}}
\newcommand{\cL}{{\cal L}}
\newcommand{\cP}{{\cal P}}

\newcommand{\pd}{\partial}

\newcommand{\half}{\frac{1}{2}}
\newcommand{\shalf}{{\textstyle\frac{1}{2}}}
\renewcommand{\today}{}
\newcommand{\bS}{\bar{S}}

\begin{document}

\author{Jiri Hoogland\footnote{jiri@cwi.nl} 
  and Dimitri Neumann\footnote{neumann@cwi.nl}\\
  CWI, P.O.~Box 94079, 1090 GB  Amsterdam, The Netherlands}
\title{\textbf{Tradable Schemes}}
\maketitle

\thispagestyle{empty}
\begin{abstract}
In this article we present a new approach to the numerical
valuation of derivative securities. The method is based on
our previous work where we formulated the theory of pricing 
in terms of tradables. The basic idea is to fit a finite
difference scheme to exact solutions of the pricing PDE.
This can be done in a very elegant way, due to the fact that
in our tradable based formulation there appear no drift terms
in the PDE. We construct a mixed scheme based on this idea and
apply it to price various types of arithmetic Asian options, as
well as plain vanilla options (both european and american style)
on stocks paying known cash dividends. We find prices which are
accurate to $\sim 0.1\%$ in about 10ms on a Pentium 233MHz
computer and to $\sim 0.001\%$ in a second. The scheme can
also be used for market conform pricing, by fitting it to
observed option prices.
\end{abstract}

\newpage

\section{Introduction}

One of the most popular methods for pricing (exotic)
derivative securities is to make use of finite difference
schemes to solve the PDE associated with the pricing problem.
In a world where prices are driven by Wiener processes such PDE's
are usually of generalized diffusion type
%
\[ \left( \partial_t + \a(x,t)
                     + \b(x,t) \partial_x
                     + \g(x,t) \partial_x^2 \right) 
V(x,t) = 0 \]
%
In such an equation the terms containing $\a,\b$ and $\g$
will be called the constant, drift and diffusion term respectively.
In the traditional formulation of option pricing theory,
the PDE to be solved generally contains not only diffusion terms
but also non-trivial constant and drift terms. The most obvious
example is of course the Black-Scholes PDE:
%
\[ \left( \partial_t -r +rS\partial_S 
   +\frac{1}{2}\sigma^2S^2\partial_S^2 \right) V(S,t)=0 \]
%
It is well known that exactly the presence of drift terms in
the PDE can lead to severe numerical problems, unless they are
handled with much care.

In this article we present a new approach to the numerical
valuation of derivative securities. The approach is based on our
previous work \cite{HooglandNeumann99a,HooglandNeumann99b,
HooglandNeumann00a} where we introduced a new formalism for
contingent claim pricing. The core of this formalism is the idea
that problems should be formulated in terms of {\it tradable objects
only}. (Note that we use a broad definition of the term tradable:
every quantity that can be represented by a self-financing portfolio
is considered to be a tradable). From a numerical point of view,
the formalism has the distinct advantage that pricing PDE's never
contain drift nor constant terms. This makes it a very natural
starting point for the construction of finite difference schemes
for pricing derivative securities.

Our key idea is to require that a given set of solutions of the
underlying PDE should also be an exact solution of the numerical
scheme. We consider the case where there are two underlying tradables
in the pricing problem, leading to a one dimensional PDE. It then
turns out that we only need three exact solutions to fix a fully
implicit (or explicit) scheme.  By combining the fully implicit and
fully explicit schemes into a Crank-Nicolson type scheme, we obtain a
very powerful mixed scheme, still fitted to the exact solutions.
Details on convergence and stability properties will be treated in
future work.

So how do we fix the scheme? A very natural choice is to use the two
tradables themselves as exact solutions of the PDE. So we need only
one more non-trivial solution of the PDE. Such a solution is in
general not too hard to obtain, as we show in this article. Note that
instead of using exact solutions we could also use observed market
prices to fix the scheme, generalizing in a natural way the concept of
implied trees of Ref.~\cite{DermanKani94}. The latter idea will be
explored in future work.

In this article we present results on the performance of our scheme
when applied to the pricing of a well known problematic case: the
arithmetic Asian option, and furthermore results on the pricing of
plain vanilla options on stocks paying cash dividends, which are
related to arithmetic Asians by a symmetry operation (see
Ref.~\cite{HooglandNeumann00a}).  Note however that these applications
only serve as an example of the power of the our scheme. The scheme
itself can be used in a much broader class of pricing problems.

Let us recall some other approaches to the problem of pricing 
arithmetic Asians which can be found in the literature. To start with,
there are the (semi-)analytical approaches. The first result in this
direction was given in Ref.~\cite{GemanYor93}, who derived a closed
form expression for the Laplace-transform of the price of a
continuously sampled average price call. In our
paper~\cite{HooglandNeumann00a} we provided a similar solution
for the price of an arithmetic average strike put. Exploiting the
various symmetries underlying the pricing of contingent claims,
we furthermore showed that unseasoned arithmetic average price
and strike options are closely related objects, which can be
transformed into each other by a suitable substitution of parameters.
However, to find actual prices, one needs to calculate an inverse
Laplace transform. This turns out to be a hard problem, which
requires a substantial amount of numerical work~\cite{FuMadanWang98}
and makes the method less suitable for practical purposes.

For this reason, people usually revert to approximative or numerical
methods instead. These methods can be roughly classified in three
categories. The first category consists of analytical approximations.
In Ref.~\cite{TurnbullWakeman91} the first two moments of the
distribution of the arithmetic average are fitted to a lognormal
distribution. This leads to a Black-Scholes type pricing
formula. Alternatively, in Refs.~\cite{Curran94,RogersShi95,
Thompson99} quite accurate upper- and lower bounds on prices
are derived. These methods can be very fast. Disadvantages are
that they have a fixed accuracy and they can not easily be adapted
to handle discretely sampled Asians and early exercise features. 

The second category consists of methods which use the path integral or
Feynman-Kac formulation of the problem as a starting point. A path
integral can easily be evaluated using a Monte Carlo
approach~\cite{KemnaVorst92}. Just generate a large number of paths
and take averages over the payoffs associated with every individual
path. This method is versatile, simple to use and easy to implement.
Main disadvantages are that convergence is slow, and the incorporation
of early exercise features is notably hard. To speed up the
calculation, one can make use of a proper control-variate to reduce
the variance. In the case of arithmetic Asians, the obvious choice of
a control variate is a geometric Asian for which closed form formulas
do exist. Another disadvantage of Monte Carlo simulation is that paths
are sampled discretely. Therefore the method inherently makes a
discretization error when calculating continuously sampled Asians.

The third category consists of methods which numerically solve the PDE
associated to the pricing problem. This approach is flexible and early
exercise features can be incorporated in a straightforward manner. For
arithmetic Asians there exist various forms of this PDE (e.g.
Refs.~\cite{Ingersoll87,RogersShi95,Zhang99,HooglandNeumann99b}). In
principle all these forms can be related to each other by suitable
changes of variables. However, to the best of our knowledge, our
formulation of pricing theory in terms of tradables is the first and
only one which leads in a natural and straightforward way to a PDE
without drift and constant terms. Other approaches lead to PDE's which
are plagued by the presence of drift terms. The main problem
associated to the appearance of a drift term is that for certain
parameter ranges it tends to dominate the diffusion term. The PDE then
becomes of hyperbolic type instead of parabolic type.  If such a
problem is attacked using standard techniques for solving parabolic
(diffusion) equations, one finds spurious oscillations in the
numerical solution.  Similar problems are well known in the field of
computational fluid dynamics, where they are known as boundary layer
problems. It is this field in which methods were developed to
circumvent the problem. One approach is to make use of so-called
flux-delimiters. Their use in the pricing of arithmetic Asians was
introduced in Ref.~\cite{ZvanForsythVetzal97}. Unfortunately, their
scheme is rather complicated to implement as it uses a non-uniform
grid. Another approach is to use so-called fitted
schemes~\cite{Duffy,Morton96}. Here the idea is to construct a finite
difference scheme in such a way that stationary (time-independent)
solutions of the underlying PDE are exact solutions of the numerical
scheme.

Of course, boundary layer problems can be trivially avoided if
drift terms are absent. The elegance of our idea lies in the fact that 
it is based on a formulation which accomplishes just this. This is
a consequence of using the proper coordinates: tradables.

The outline of this article is as follows. Section 2 gives some
background and motivation. In section 3 the construction of our
finite difference scheme is described. In section 4 we apply the
scheme to the PDE for Asian type options as well as vanilla options
on stock paying cash dividend. Section 5 provides numerical results
for both type of options. In section 6 we conclude and give an outlook. 

\section{Motivation}

In previous work \cite{HooglandNeumann99a,HooglandNeumann99b,
HooglandNeumann00a}, we have shown that in a market
with two tradables, say $S$ and $P$, where price processes are driven 
by Brownian motions, the pricing PDE can be reduced to the form
%
\[ \left(-\partial_{\t}+\half\s(x,t)^2x^2\partial_x^2\right)V(x,\t)=0 \]
%
where $P$ was chosen as numeraire, $\t$ is time to maturity, $x\equiv
S/P$ and the price is $PV(x,\t)$.  Note the absence of a drift term.
Due to this fact, the PDE has the trivial solutions $x$ and $1$,
corresponding to the basic tradables $S$ and $P$ respectively. So
the pricing problem is fixed by knowledge of $\s(x,\t)$. Alternatively,
suppose we know one more solution of this equation, one that has a
non-vanishing second derivative with respect to $x$ (gamma), call it
$R(x,\t)$. Then we can write
%
\[ \frac{1}{2}\s(x,\t)^2 x^2 = \frac{\partial_{\t}R(x,\t)}
{\partial_x^2 R(x,\t)} \]
%
In other words, the knowledge of the price of one sufficiently
well-behaved derivative security also fixes the model. Let us consider
as an example the Black-Scholes context. It is easy to construct
a tradable with payoff $x^2$ at time $\t=0$ (We will call it a
quadratic tradable. It is a special case of a power tradable.
See Ref.~\cite{HooglandNeumann99b}). It is given by
%
\[ x^2 e^{\s^2\t} \]
%
Plugging this into the formula we find
%
\[ \s(x,t)=\s \]
%
as expected. Note that if we use observed option prices
of, say, call options, taking derivatives w.r.t. expiration
time and strike, we recover the concept of local volatility,
the basic idea behind implied trees \cite{DermanKani94}.

\section{Finite differences}

We can use the same line of thought to construct very efficient
finite difference schemes. The idea is to construct a scheme in
such a way that it has the underlying tradables as well as one
given derived tradable as exact solutions. We will now show that
these conditions uniquely fix a fully implicit scheme. Indeed,
a fully implicit scheme is defined by the relations
%
\[ a \d_x^+ \d_x^- V(x,\t) + b \d_x^0 V(x,\t)+ c V(x,\t) = 
   d \d_\t^- V(x,\t) \]
%
where
%
\[ \d_x^+ \d_x^- V(x,\t) \equiv 
   \frac{V(x+\d x,\t)-2V(x,\t)+V(x-\d x,\t)}{\d x^2} \]
\[ \d_x^0 V(x,\t) \equiv \frac{V(x+\d x,\t)-V(x-\d x,\t)}{2\d x} \]
\[ \d_\t^- V(x,\t) \equiv \frac{V(x,\t)-V(x,\t-\d\t)}{\d\t} \]
%
and $a,b,c,d$ are functions of $x$ and $\t$. Now demanding that
$V=x$ and $V=1$ are solutions of the scheme corresponds to setting
$b=0, c=0$. Next, demanding that a given tradable $R(x,\t)$ is also
a solution leads to
%
\[ a \d_x^+ \d_x^- R(x,\t) = d \d_\t^- R(x,\t) \]
%
Therefore, the fully implicit scheme, implied by the tradables
is given by
%
\begin{equation} \Theta^-(x,\t) \d_x^+ \d_x^- V(x,\t) = 
\Gamma(x,\t) \d_\t^- V(x,\t)
\label{eq:imp} \end{equation}
%
where
%
\[ \Theta^-(x,\t) \equiv \d_\t^- R(x,\t) \]
\[ \Gamma(x,\t)   \equiv \d_x^+ \d_x^- R(x,\t) \]
%
A remarkably simple scheme, by virtue of the fact that in
our formulation of the pricing problem there are no drift terms
in the PDE. The absence of these drift terms also make the
scheme unconditionally stable (see later article). Of course we
can also derive an explicit scheme along the same lines. We find
%
\begin{equation} \Theta^+(x,\t) \d_x^+ \d_x^- V(x,\t) = 
\Gamma(x,\t) \d_\t^+ V(x,\t)
\label{eq:exp} \end{equation}
%
where now
%
\[ \d_\t^+ V(x,\t) \equiv \frac{V(x,\t+\d\t)-V(x,\t)}{\d\t} \]
\[ \Theta^+(x,\t)  \equiv \d_\t^+ R(x,\t) \]
%
To further improve the accuracy of the scheme, we have combined the
two schemes into a Crank-Nicolson type of scheme, i.e. we take the
sum of Eqs.~\ref{eq:imp},\ref{eq:exp}, taking care of a proper time
shift in one of them.

\section{Application to a specific PDE}

A very interesting application of the scheme is in finding
solutions of the PDE
%
\begin{equation}
  (-\partial_\t +\half \s^2 (x-\phi(\t))^2 \partial_x^2)V(x,\t)=0
  \label{eq:pde}
\end{equation}
%
where $\phi(\t)$ is a deterministic function. As was shown in our
articles Ref.~\cite{HooglandNeumann99b, HooglandNeumann00a}, this PDE
can be used to price arithmetic Asian options as well as plain vanilla
options on stocks paying cash dividends. Let us briefly recall how the
PDE is related to such options. To price an arithmetic average strike
put (unseasoned) with a payoff defined by
%
\begin{equation}
  \left( \int_0^\t w(u)\frac{S(u)}{P(u)}du - kS \right)^+ 
  \label{eq:asp}
\end{equation}
%
we set
%
\[ \phi(\t) = \int_0^\t w(u) du \]
%
and then solve the PDE with boundary condition
%
\[ V(x,0) = (x-k)^+ \]
%
The price then follows from
%
\[ \mbox{Price} = S V(\phi(\t),\t) \]
%
The PDE can also be used to price average price options (using
time reversal duality) and seasoned Asians in general. Details
can be found in Ref.~\cite{HooglandNeumann00a}. To price a vanilla
option (say a call) with strike $K$ on a stock paying a stream
of cash dividends with density $w(\t)$, expressed in units of
the bond, we set
%
\[ \phi(\t) = - \int_0^\t w(u) du \]
%
(notice the sign) and then solve the PDE with boundary condition
%
\[ V(x,0) = (x-K)^+ \]
%
The price then follows from
%
\[ \mbox{Price} = P V(S/P+\phi(\t),\t) \]
%
Note that if dividend payments are discrete (or for the Asian,
sampling is discrete), $w(\t)$ becomes a weighted sum of Dirac
delta-functions, and $\phi(\t)$ becomes a piecewise constant
function, making jumps at dividend (sample) dates.

\vspace{1\baselineskip} \noindent Now the key question is: can we find
exact solutions to the PDE, simple enough, which can be used to set up
our implied mixed scheme?  Fortunately, the answer is yes. Again the
idea is to use a quadratic tradable, equalling $x^2$ at $\t=0$. This
is a good choice for two reasons. Firstly it is the simplest
non-trivial tradable. Secondly it has an $x$-independent gamma, which
is convenient for numerical reasons. Assuming that the solution
remains a quadratic polynomial in $x$ we try a solution of the form
%
\[ R(x,\t) = A(\t)x^2+B(\t)x+C(\t) \]
%
Plugging this into Eq.~\ref{eq:pde}, we find the following
relations for the functions $A,B,C$:
%
\[ \partial_\t A(\t) =    \s^2            A(\t) \]
\[ \partial_\t B(\t) = -2 \s^2 \phi(\t)   A(\t) \]
\[ \partial_\t C(\t) =    \s^2 \phi(\t)^2 A(\t) \]
%
and they have the following solution
%
\[ A(\t) = e^{\s^2\t} \]
\[ B(\t) = -2 \s^2 \int_0^\t \phi(u)e^{\s^2 u} du \]
\[ C(\t) = \s^2 \int_0^\t \phi(u)^2 e^{\s^2 u} du \]
%
These equations can easily be solved exactly, both in the case
of discrete sampling (where $\phi$ is piecewise constant) and
continuous sampling. For example, if we have a continuous
exponential weight function $w(\t)=e^{-r\t}/T$, we have
%
\[ \phi(\t)=\frac{1-e^{-r\t}}{rT} \]
%
and
%
\[ B(\t) = \frac{2}{T(r-\s^2)}-\frac{2e^{\s^2\t}}{rT}\left(
  1+\frac{e^{-r\t}\s^2}{r-\s^2} \right) \]
\[ C(\t) = -\frac{2}{T^2(r-\s^2)(2r-\s^2)} +
   \frac{e^{\s^2\t}}{r^2T^2}\left( 1+\frac{2e^{-r\t}\s^2}{r-\s^2}
   -\frac{e^{-2r\t}\s^2}{2r-\s^2}\right) \]

\section{Results}

We have implemented the mixed scheme in C++. The numerical tests were
performed on a Pentium 233MHz machine. We have considered various
Asian options as well as options on stocks paying cash dividends. For
each option, we have compared results for three different grid sizes.
The results coming from the largest grid are so much more accurate
than the ones that we could find in the literature, that we have used
this as benchmark. We claim that these results are accurate to at
least six significant digits. The results compare well with numbers
recently obtained in Ref.~\cite{Zhang99}. The gridsizes that we have
used are summarized in the table.

\begin{center} \begin{tabular}{|c|c|}
\hline Name & $N_x N_\t$ \\ \hline
``Exact'' & $10^8$ \\ \hline
1 sec & $10^6$ \\ \hline
10 ms & $10^4$ \\ \hline
\end{tabular} \end{center}

\noindent The time labels of course indicate the execution speed
of the algorithm on our computer. The total number of points on
the grid were divided over the $x$ and $\t$ direction in such a
way that $N_\t/N_x\sim\s^2 T$. In all cases, care was taken that 
non-differentiable points on the payoff (at the strike) fell
on gridpoints. The boundary conditions in the $\t$-direction
were placed at zero and twice the strike. They are taken to be
time-independent (since gamma is very small there). So for a
payoff of the form
%
\[ V(x,0) = (x-k)^+ \]
%
we also imposed
%
\[ V(0,\t) = 0, \hspace{5mm} V(2k,\t)=k \]
%
Note that the scheme can be improved on this point: for
high volatility it might be neccessary to place the bounds
further away from the strike, while for low volatility the
scheme can be improved by moving them closer. This leads to
a speedup of at least a factor 5 for the lowest volatilities.

\vspace{1\baselineskip} \noindent
The first instrument we consider is a standard
continuously sampled average strike Asian put option.
This corresponds to the choice of weight function
$w(\t)=e^{-r\t}/T$ (see Eq.~\ref{eq:asp} with $k=1$). We
use the parameters values used in Ref.~\cite{RogersShi95}:
initial stockprice $S=100$ and expiry time is 1 year.
Note that except for the lowest volatility setting, the
1 second results are practically equal to the exact
ones. As was mentioned before, the results can be
improved by using tighter boundary conditions for low
volatility.

\begin{center} \begin{tabular}{|c|c|c|c|c|}
\hline $\s$ & $r$ & Exact & 1 sec & 10 ms \\ \hline
    & 0.05 & 1.24546 & 1.24546 & 1.24617 \\ \cline{2-5}
0.1 & 0.09 & .699292 & .699311 & .701360 \\ \cline{2-5}
    & 0.15 & .251676 & .251712 & .255256 \\ \hline
    & 0.05 & 3.40481 & 3.40481 & 3.40500 \\ \cline{2-5}
0.2 & 0.09 & 2.62202 & 2.62202 & 2.62224 \\ \cline{2-5}
    & 0.15 & 1.71019 & 1.71021 & 1.71193 \\ \hline
    & 0.05 & 5.62603 & 5.62602 & 5.62592 \\ \cline{2-5}
0.3 & 0.09 & 4.73955 & 4.73954 & 4.73940 \\ \cline{2-5}
    & 0.15 & 3.60981 & 3.60981 & 3.60985 \\ \hline
\end{tabular} 
\\[1\baselineskip] 
Table 1: Continuously sampled average strike put
\end{center}

\noindent To see how the scheme performs in a discrete
sampling setting, we next consider a discretely sampled
average strike Asian put. Parameters settings are $S=100$,
$\s=0.2$, $r=0.1$ and expiry time is 1 year. There are $N$
sample dates, all with weight $1/N$ in terms of the money
value of the stock and taken at the beginning of each of
the $N$ equal length time periods in which the year is
divided. This corresponds to a weight function
%
\[ w(\t) = 
\sum_{i=1}^N \frac{e^{-r\t}}{N} \d\left(\t-\frac{i}{N}\right) \]
%
Note that for $N=1$ the option is essentially a plain
vanilla put with strike $100$. For $N\to\infty$, the
option becomes a continuously sampled Asian. It must be noted
that in most occasions sample dates do not correspond to
gridpoints in the time direction. In some cases there are many
more gridpoints than there are samples, in other cases
the reverse is true. Obviously, the scheme handles both
cases very well. This is due to the fact that the scheme
is fitted to an exact solution of the PDE.

\begin{center} \begin{tabular}{|c|c|c|c|} \hline
$N$ & Exact & 1 sec & 10 ms \\ \hline
       1 & 3.75342 & 3.75342 & 3.75334 \\ \hline
       2 & 3.12047 & 3.12047 & 3.12062 \\ \hline
       4 & 2.79055 & 2.79055 & 2.79106 \\ \hline
       8 & 2.62151 & 2.62151 & 2.62217 \\ \hline
      16 & 2.53578 & 2.53578 & 2.53645 \\ \hline
      32 & 2.49257 & 2.49257 & 2.49324 \\ \hline
      64 & 2.47088 & 2.47088 & 2.47153 \\ \hline
     128 & 2.46001 & 2.46001 & 2.46065 \\ \hline
     256 & 2.45456 & 2.45457 & 2.45521 \\ \hline
     512 & 2.45184 & 2.45185 & 2.45249 \\ \hline
    1024 & 2.45048 & 2.45048 & 2.45112 \\ \hline
$\infty$ & 2.44912 & 2.44912 & 2.44976 \\ \hline
\end{tabular}
\\[1\baselineskip] 
Table 2: Discretely sampled average strike put
\end{center}

\noindent Since prices of average price Asians can be
related to prices of average strike Asians by T(ime-reversal)
duality \cite{HooglandNeumann00a}, it is not really neccessary
to give results for average price Asians. But in order to
allow the reader to compare our result to those in the
literature, we will give the results anyway. We consider
standard continuously sampled average price calls with parameter
settings $S=100$, $r=0.09$ and expiry in 1 year.

\begin{center} \begin{tabular}{|c|c|c|c|c|}
\hline $\s$ & $K$ & Exact & 1 sec & 10 ms \\ \hline
     &  95 & 8.80884 & 8.80884 & 8.80895 \\ \cline{2-5}
0.05 & 100 & 4.30823 & 4.30825 & 4.31013 \\ \cline{2-5}
     & 105 & .958384 & .958385 & .958493 \\ \hline
     &  95 & 8.91185 & 8.91189 & 8.91538 \\ \cline{2-5}
 0.1 & 100 & 4.91512 & 4.91515 & 4.91802 \\ \cline{2-5}
     & 105 & 2.07006 & 2.07006 & 2.07022 \\ \hline
     &  90 & 14.9840 & 14.9841 & 14.9951 \\ \cline{2-5}
 0.3 & 100 & 8.82876 & 8.82880 & 8.83275 \\ \cline{2-5}
     & 110 & 4.69671 & 4.69670 & 4.69640 \\ \hline
     &  90 & 18.1886 & 18.1888 & 18.2055 \\ \cline{2-5}
 0.5 & 100 & 13.0281 & 13.0282 & 13.0357 \\ \cline{2-5}
     & 110 & 9.12429 & 9.12429 & 9.12454 \\ \hline
\end{tabular}
\\[1\baselineskip] 
Table 3: Continuously sampled average price call
\end{center}

\noindent As a final example we consider plain vanilla
options on a stock paying cash dividend. We consider a stock
with initial value $S=100$ and volatility $\s=0.1$. The
stock will pay a cash dividend of 5 after half a year.
Interest rate $r=0.05$. We consider a put and a call option
on this stock expiring in 1 year. In this case we
not only look at European style but also at American style
options. To calculate the latter we take the maximum
of the early exercise payoff and the calculated option
value at each timestep. For a call, the early exercise payoff
takes the form
%
\[ (x-\phi(\t)-Ke^{r\t})^+ \]
%
in our coordinates. (Note that we can also use this technique
to valuate American style average strike Asians). The results
show that convergence is slower in the American case. This can
be explained by the fact that the early exercise feature is only
enforced at gridpoints, in effect approximating the American
with a Bermudan option. Therefore the value is systematically
underestimated. Of course this is a general problem when
evaluating American options with finite difference schemes.
Nevertheless, the accuracy of our scheme is still of order $0.5\%$
for such options in the 10 ms gridsize.

\begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline
\multicolumn{1}{|c|}{Call} & 
\multicolumn{3}{c|}{European} &
\multicolumn{3}{c|}{American} \\ \hline
$K$ & Exact & 1 sec & 10 ms & Exact & 1 sec & 10 ms \\ \hline
 95 & 6.63807 & 6.63808 & 6.63910 & 8.00342 & 8.00405 & 7.97394 \\ \hline
100 & 3.89199 & 3.89199 & 3.89207 & 4.55708 & 4.55755 & 4.52858 \\ \hline
105 & 2.05220 & 2.05220 & 2.05248 & 2.28620 & 2.28646 & 2.27272 \\ \hline
\end{tabular} \end{center}

\begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline
\multicolumn{1}{|c|}{Put} & 
\multicolumn{3}{c|}{European} &
\multicolumn{3}{c|}{American} \\ \hline
$K$ & Exact & 1 sec & 10 ms & Exact & 1 sec & 10 ms \\ \hline
 95 & 1.88141 & 1.88142 & 1.88244 & 2.26310 & 2.26192 & 2.25389 \\ \hline
100 & 3.89148 & 3.89148 & 3.89156 & 4.72489 & 4.72226 & 4.70623 \\ \hline
105 & 6.80784 & 6.80784 & 6.80812 & 8.22660 & 8.22212 & 8.20011 \\ \hline
\end{tabular}
\\[1\baselineskip] 
Table 4: Vanilla options with cash dividends
\end{center}

\section{Conclusions and outlook}

In this article we introduced a very simple and natural
finite-difference scheme for pricing derivative securities.  The
scheme is easy to implement and very flexible.  No special tricks need
to be used to reach a high accuracy.  The scheme follows in a
straightforward manner from our formulation of the pricing problem in
terms of tradables.  The key idea is that one can often find {\it
  exact} solutions to the governing PDE. These solutions can be used
to tune the finite-difference scheme in a very simple manner.
Problems usually associated to the presence of drift terms, e.g.
boundary layers, are trivially avoided. Numerical computations for
arithmetic Asian options show that convergence is fast and neither the
solution nor the greeks are plagued by oscillations. Also, financial
instruments often depend on values of underlying on discrete points in
time, and this can lead to discretization errors in a finite
difference scheme when these points do not match with gridpoints. Our
algorithm compensates for this problem by making use of exact
solutions.

Although this article focussed on adapting a finite-difference
scheme to exact solutions of a particular pricing PDE, it does not take
too much effort to extent our method in such a way that observed
prices are used to construct an implied finite difference scheme,
extending the idea of implied trees. We will come back to this in a
future article.

\section*{Acknowledgements}

We would like to thank Daniel Duffy and Piet Hemker for extensive
discussions on boundary layer problems, fitting schemes, and singular
perturbation methods.

\begin{thebibliography}{FMW98}

\bibitem[Cur94]{Curran94}
M. Curran,
{\small\it Valuing Asian and portfolio options by conditioning on
the geometric mean price},
Management Science {\small\bf 40} (1994) 1705--1711.

\bibitem[DK94]{DermanKani94}
E.~Derman and I.~Kani,
{\small\it Riding on a smile}, Risk Magazine {\small\bf 7} (1994)
32--39 (February).

\bibitem[Duf00]{Duffy}
Daniel~Duffie, Private communication.

\bibitem[FMW98]{FuMadanWang98}
M.C.~Fu, D.B.~Madan and T.~Wang,
{\small\it Pricing continuous time Asian options: A comparison
of Monte Carlo and Laplace transform inversion methods},
Journal of Computational Finance {\small\bf 2-2} (1998) 49--74.

\bibitem[GY93]{GemanYor93}
H.~Geman and M.~Yor,
{\small\it Bessel processes, Asian options and perpetuities},
Mathematical finance {\small\bf 3} (1993) 349--375.

\bibitem[HN99a]{HooglandNeumann99a}
J.K.~Hoogland and C.D.D.~Neumann,
{\small\it Local scale invariance and contingent claim pricing},
Technical Report MAS--R9914, CWI, (1999),
accepted for publishing in IJTAF.

\bibitem[HN99b]{HooglandNeumann99b}
J.K.~Hoogland and C.D.D.~Neumann,
{\small\it Local scale invariance and contingent claim pricing {II}:
  path-dependent contingent claims},
Technical Report MAS--R9919, CWI, (1999),
accepted for publishing in IJTAF.

\bibitem[HN00a]{HooglandNeumann00a}
J.K.~Hoogland and C.D.D.~Neumann,
{\small\it Asians and cash dividends: Exploiting symmetries
in pricing theory},
Technical Report MAS--R0019, CWI, (2000).

\bibitem[Ing87]{Ingersoll87}
J.~Ingersoll~Jr.,
{\small\it Theory of financial decision making},
Roman \& Littlefield, Totowa, NJ, (1987).

\bibitem[KV92]{KemnaVorst92} A.~Kemna and A.~Vorst,
{\small\it A pricing method for options based on average asset
values}, Journal of Banking and Finance {\small\bf 14} (1990), 113--129.

\bibitem[Mor96]{Morton96}
K.W.~Morton,
{\small\it Numerical solution of convection-diffusion problems},
Chapman \& Hall, London (1996).

\bibitem[RS95]{RogersShi95}
L.C.G.~Rogers and Z.~Shi,
{\small\it The value of an Asian option},
Journal of Applied Probability {\small\bf 32} (1995) 1077--1088.

\bibitem[Tho99]{Thompson99}
G.~Thompson,
{\small\it Fast narrow bounds on the value of Asian options},
Working paper (1999).

\bibitem[TW91]{TurnbullWakeman91}
S.M.~Turnbull and L.M.~Wakeman,
{\small\it A quick algorithm for pricing european average options},
Journal of financial and quantative analysis {\small\bf 26} (1991)
377--389.

\bibitem[Zha99]{Zhang99}
J.E.~Zhang,
{\small\it Arithmetic Asian options with continuous sampling},
Working paper (1999).

\bibitem[ZFV97]{ZvanForsythVetzal97}
R.~Zvan, P.A.~Forsyth and K.R.~Vetzal,
{\small\it Robust numerical methods for PDE models of Asian options},
Journal of Computational Finance {\small\bf 1-2} (1997) 38--78.

\end{thebibliography}

\end{document}







cond-mat0009042.extracted_bib
\begin{thebibliography}{FMW98}

\bibitem[Cur94]{Curran94}
M. Curran,
{\small\it Valuing Asian and portfolio options by conditioning on
the geometric mean price},
Management Science {\small\bf 40} (1994) 1705--1711.

\bibitem[DK94]{DermanKani94}
E.~Derman and I.~Kani,
{\small\it Riding on a smile}, Risk Magazine {\small\bf 7} (1994)
32--39 (February).

\bibitem[Duf00]{Duffy}
Daniel~Duffie, Private communication.

\bibitem[FMW98]{FuMadanWang98}
M.C.~Fu, D.B.~Madan and T.~Wang,
{\small\it Pricing continuous time Asian options: A comparison
of Monte Carlo and Laplace transform inversion methods},
Journal of Computational Finance {\small\bf 2-2} (1998) 49--74.

\bibitem[GY93]{GemanYor93}
H.~Geman and M.~Yor,
{\small\it Bessel processes, Asian options and perpetuities},
Mathematical finance {\small\bf 3} (1993) 349--375.

\bibitem[HN99a]{HooglandNeumann99a}
J.K.~Hoogland and C.D.D.~Neumann,
{\small\it Local scale invariance and contingent claim pricing},
Technical Report MAS--R9914, CWI, (1999),
accepted for publishing in IJTAF.

\bibitem[HN99b]{HooglandNeumann99b}
J.K.~Hoogland and C.D.D.~Neumann,
{\small\it Local scale invariance and contingent claim pricing {II}:
  path-dependent contingent claims},
Technical Report MAS--R9919, CWI, (1999),
accepted for publishing in IJTAF.

\bibitem[HN00a]{HooglandNeumann00a}
J.K.~Hoogland and C.D.D.~Neumann,
{\small\it Asians and cash dividends: Exploiting symmetries
in pricing theory},
Technical Report MAS--R0019, CWI, (2000).

\bibitem[Ing87]{Ingersoll87}
J.~Ingersoll~Jr.,
{\small\it Theory of financial decision making},
Roman \& Littlefield, Totowa, NJ, (1987).

\bibitem[KV92]{KemnaVorst92} A.~Kemna and A.~Vorst,
{\small\it A pricing method for options based on average asset
values}, Journal of Banking and Finance {\small\bf 14} (1990), 113--129.

\bibitem[Mor96]{Morton96}
K.W.~Morton,
{\small\it Numerical solution of convection-diffusion problems},
Chapman \& Hall, London (1996).

\bibitem[RS95]{RogersShi95}
L.C.G.~Rogers and Z.~Shi,
{\small\it The value of an Asian option},
Journal of Applied Probability {\small\bf 32} (1995) 1077--1088.

\bibitem[Tho99]{Thompson99}
G.~Thompson,
{\small\it Fast narrow bounds on the value of Asian options},
Working paper (1999).

\bibitem[TW91]{TurnbullWakeman91}
S.M.~Turnbull and L.M.~Wakeman,
{\small\it A quick algorithm for pricing european average options},
Journal of financial and quantative analysis {\small\bf 26} (1991)
377--389.

\bibitem[Zha99]{Zhang99}
J.E.~Zhang,
{\small\it Arithmetic Asian options with continuous sampling},
Working paper (1999).

\bibitem[ZFV97]{ZvanForsythVetzal97}
R.~Zvan, P.A.~Forsyth and K.R.~Vetzal,
{\small\it Robust numerical methods for PDE models of Asian options},
Journal of Computational Finance {\small\bf 1-2} (1997) 38--78.

\end{thebibliography}