Corso di Laurea in Matematica
Tesi di Laurea Magistrale
Numerical methods for option pricing:
Finite differences and multigrid
techniques
Candidato:
Relatore:
Francesco Cordoni
Prof. Dario A. Bini
Controrelatore:
Prof.ssa Beatrice Meini
Vorrei ringraziare tutti coloro che mi hanno aiutato a scrivere questa tesi, in particolare:
Il mio relatore Dario Bini, per avermi supportato e sopportato, aiutan-domi con i suoi consigli sempre utili.
Il prof. Maurizio Pratelli, per la disponibilit`a data. Elena, per l’aiuto dato.
Sara, per il sostegno che mi ha fornito.
La mia famiglia, per il supporto che mi ha dato.
I miei amici e compagni, per aver condiviso questi anni con me. Francesco Cordoni
Abstract v
Introduction vii
1 The Black–Scholes model 1
1.1 The model . . . 1
1.2 Option styles . . . 3
1.2.1 European and American options . . . 4
1.2.2 Exotic options . . . 7
1.3 Basic problems . . . 9
1.4 Risk sensitivities . . . 9
2 Classical methods 12 2.1 Binomial Lattices . . . 12
2.2 The Monte Carlo method . . . 16
2.2.1 The Longstaff-Schwartz algorithm . . . 19
2.3 Finite difference methods . . . 21
2.3.1 Motivations . . . 22
2.3.2 Fundamentals of numerical analysis . . . 23
2.3.3 A first discretization . . . 24
2.3.4 Explicit method . . . 29
2.3.5 Implicit method . . . 31
2.3.6 Crank-Nicolson method . . . 32
2.3.7 American options . . . 33
3 Exponentially fitted schemes 37 3.1 Oscillation problems . . . 39
3.2 The maximum principle . . . 40
3.3 Exponentially fitted schemes . . . 42
3.3.1 The Il’in scheme . . . 42
4 American option pricing 52
4.1 A first simple approach and the LCP formulation . . . 53
4.2 Introduction to free boundary problems . . . 55
4.3 Front-fixing for American put options . . . 57
4.3.1 Theoretical results . . . 60
4.4 Front-fixing for American call options . . . 61
4.5 Implicit front-fixing method . . . 63
4.6 Han and Wu’s method and time stretching . . . 66
4.6.1 Han and Wu’s method . . . 66
4.6.2 Finite difference with time stretching schemes . . . 68
5 The multigrid method 70 5.1 Notation and first look at multigrid . . . 70
5.1.1 Basic notation . . . 70
5.1.2 Poisson’s equation . . . 71
5.1.3 First look at multigrid . . . 72
5.1.4 High and lower frequencies . . . 73
5.2 Basic multigrid . . . 75
5.2.1 Error smoothing procedures . . . 75
5.2.2 Two-grid cycle . . . 76
5.2.3 Multigrid cycle . . . 82
5.2.4 Computational work and convergence factor . . . 84
5.2.5 Full multigrid . . . 85
5.2.6 Some generalizations . . . 86
5.3 Elementary multigrid theory . . . 88
5.4 Local Fourier analysis . . . 90
5.4.1 Introduction to LFA . . . 90
5.4.2 Notation . . . 90
5.4.3 Smoothing analysis . . . 92
5.4.4 Two-grid analysis . . . 93
5.4.5 Simplified two-grid analysis . . . 94
5.4.6 h-ellipticity . . . 95
5.5 Multigrid for option pricing . . . 97
5.5.1 A first example . . . 97
5.5.2 Multigrid as preconditioner . . . 99
5.5.3 Multigrid for the Black-Scholes equation . . . 99
6.2 American options . . . 108 6.3 Multi-asset options . . . 112
Conclusions and future developments 119
L’argomento principale di questa tesi `e la descrizione e l’analisi del problema dell’option pricing, da un punto di vista computazionale, nelle ipotesi del modello di Black-Scholes e delle sue generalizzazioni. Particolare attenzione `
e posta alle tecniche numeriche introdotte per la sua soluzione, con riguardo al metodo delle differenze finite e alle tecniche multigrid. La descrizione e l’analisi numerica dei principali algoritmi `e effettuata insieme alla sperimen-tazione numerica, in maniera da evidenziare le caratteristiche e svantaggi delle differenti tecniche di soluzione.
Un’opzione `e un tipo di derivato finanziario, che concede al compratore il diritto, ma non l’obbligo, di comprare o vendere uno specifico sottostante, come un’azione, ad un determinato prezzo, entro un certa data. Un’opzione si dir`a Europea, se pu`o essere esercitata solamente alla data di maturit`a, mentre si dir`a Americana, se pu`o essere esercitata in ogni momento fino alla data di maturit`a.
Il modello di Black-Scholes costituisce la base per l’option pricing e fu introdotto nel 1973 da Fischer Black e Myron S. Scholes [5]. Dal modello si ricava che il prezzo dell’opzione f `e descritto dalla seguente equazione differenziale alle derivate parziali,
∂f ∂t + 1 2σ 2 S2∂ 2f ∂S2 + rS ∂f ∂S = rf,
dove r `e il tasso di interesse privo di rischio e σ `e la volatilit`a di S. L’equazione di sopra `e detta equazione differenziale di Black-Scholes.
Nel caso di opzione di tipo Europeo esiste una soluzione esplicita dell’ equazione di Black-Scholes. Purtroppo, nel caso Americano, e in certi tipi di opzioni esotiche, non esiste una soluzione esplicita come nel caso Europeo. Quindi, `e necessario l’uso di un approccio numerico per ricavare una ap-prossimazione della soluzione dell’equazione. Nel capitolo 1 introduciamo brevemente il modello di Black-Scholes ed i tipi di opzione che considereremo successivamente.
Esistono tre approcci numerici classici: il metodo binomiale, che si basa sulla costruzione di un modello a tempi discreti, il metodo Monte Carlo, che
capitolo 2 descriviamo i tre tipi di approcci numerici, per poi porre attenzione maggiore sul metodo delle differenze finite, evidenziandone i vantaggi rispetto ai precedenti due.
Essendo l’equazione di Black-Scholes un’equazione di tipo convezione-diffusione, gli schemi alle differenze finite classici come il metodo di Crank-Nicolson, producono soluzioni numeriche con oscillazioni spurie, quando l’ equazione diventa convection-dominated. Nel capitolo 3 presentiamo e anal-izziamo numericamente l’exponentially fitted scheme, il quale permette di evitare la presenza di queste oscillazioni [29, 17, 11].
Nel capitolo 4 studiamo il caso Americano attraverso la formulazione di un opportuno free boundary value problem. In particolare, analizziamo dal punto di vista numerico la tecnica del front-fixing [66, 44, 21]. Tramite test numerici confronteremo poi questo metodo con gli altri.
Un semplice esempio di opzione esotica `e l’opzione di scambio e la sua generalizzazione detta opzione spread. Nel capitolo 5 presentiamo il metodo multigrid, analizzando gli aspetti teorici e numerici. Successivamente ap-plichiamo la tecnica multigrid al caso delle opzioni di scambio e di spread, con opportuni confronti numerici che saranno riportati, come per tutti gli altri metodi, nel capitolo 6. Infine concluderemo e presenteremo possibili sviluppi futuri.
The main topic of this thesis is the description and the analysis of the option pricing under the Black and Scholes model and its generalizations, from a computational point of view. We pay particular attention to the numerical techniques introduced for its solution with specific regard to multigrid and finite difference techniques. The description and the numerical analysis of the main algorithms for this problem are carried out together with some numerical experiments, which point out the main features and drawbacks of the different solution techniques.
An option is a financial derivative which is a contract sold by one party, called option writer, to another party, called option holder. The option gives the buyer the right, but not the obligation, to buy or sell an underlying asset, which is specified at the beginning of the contract, for a certain price, called strike price, during a certain period of time or on a specific date, called exercise date or maturity date. We can distinguish two basic types of options, depending on the right of the holder to buy or to sell the underlying asset. A call option gives the holder the right to buy the underlying asset, whereas a put option gives the holder the right to sell the underlying asset. Options are also distinguished as European and American options. A European option can be exercised only on expiration date, while an American option can be exercised at any time up to maturity date. In this way, the American option allows the early-exercise possibility. These types of options are often called vanilla for their simplicity. Other type of options, which are not vanilla, are called exotic. Examples of exotic options are given by the so-called path-dependent options, e.g., barrier and Asian options. Later on, we will deal with exchange and spread options, that are also multi-asset derivatives.
For every option contract, there are two possible positions. On one side there is the investitor position, who has bought the option, so he/she has taken a long position, and on the other side there is the writer position, who has sold the option, so he/she has a short position. In this work we consider only long position. Therefore, when we refer to the call/put payoff we refer to the long position payoff. However, if we denote by T the expiration date,
max(ST − K, 0),
while the payoff of a European put is
max(K − ST, 0).
For the American option, the payoff at maturity date is the same that of the European option, but the American option can be exercised at any time, so it is necessary to check when it is optimal early-exercise. An option may have many variations with respect to the vanilla case. One simple change is the possibility that the underlying asset may release during its life a pay-ment return, which is called dividend. When it is necessary, we will consider constant continuous dividend expressed by a dividend yield.
Obviously, an option, as every financial derivative, has a price. To avoid arbitrage opportunities, every option must have a fair price. In this thesis, we focus on option pricing. The Black-Scholes model has been introduced by Fischer Black and Myron S. Scholes, in 1973 [5]. This model is the base of option pricing. In Chapter 1 we introduce the Black-Scholes model and option types. Black and Scholes have showed how the price evolution of a European call or European put, under their model, is governed by a parabolic partial differential equation, which is called the Black-Scholes equation:
∂f ∂t + 1 2σ 2 S2∂ 2f ∂S2 + rS ∂f ∂S = rf.
They also have provided an explicit solution for the European option pricing problem [5]. Unfortunately, in the American case there is not a closed-form solution such as in the European case. Then, it is necessary to use a numerical approximation of the solution of the Black-Scholes equation.
In the wide literature, in this research area, we may encounter three main computational approaches: the binomial method, the Monte Carlo method and the finite difference methods. In Chapter 2, we give an outline concerning the first two approaches and then we analyze in detail the third approach, where we take into account different numerical tools. The Binomial method is a discrete-time method, since it is based on a discrete-time model. The Monte Carlo method is a SDE approach, since it simulates the possible trajectories of the underlying asset price. The finite differences method is a PDE approach, since the problem is reduced to solve the Black-Scholes equation.
The binomial method considers a discrete market model, whereas the Black-Scholes model is a continuous model. It was introduced by Cox et al. [13].
of the Black-Scholes model until maturity date and after it discounts the payoff.
The finite difference methods approximate the solution of the partial differential Black-Scholes equation on a specific grid.
We focus on the finite differences method, because it has more advantages in comparison to other methods. One of this, it is the possibility to obtain all fair prices for every spot price and maturity dates on the specific grid. Furthermore, when the underlying asset releases a dividend, if we use the binomial or Monte Carlo method, we must take into account the dividend payment date, while for finite differences we have to change one parameter on the Black-Scholes equation.
The Black-Scholes equation is a linear parabolic equation with constant risk-free rate and volatility. More precisely, it is a linear convection–diffusion PDE. Despite there are well established numerical methods to solve this clas-sic numerical problem, it turns out that, due to the specificity of the problem, the numerical solution reveals some undesired oscillations. This happens in the cases where the convection component is dominant with respect to the diffusion part. This fact makes it problematic to design reliable solution al-gorithms for this important problem. We have examined the exponentially fitted scheme [21], which relies on modifying the finite differences method with a fitted parameter. We discuss this technique in Chapter 3. This tech-nique was first studied by Il’in for two-point boundary value problems [29], later on it was generalized to convection–diffusion equations by Duffy [17] and finally it was applied to the Black–Scholes equation by Cooney [11]. We show how the use of a fitted parameter avoids spurious oscillations when the equation is convection-dominated. We provide numerical analysis results and we numerically compare classical methods with the exponentially fitted scheme. This scheme is very flexible, moreover, the technique underlying this method can be applied to other approaches such as the multigrid scheme.
Unfortunately, for the American option pricing problem a closed-form of the solution does not exist for general setting of parameters, such as for the European option pricing problem. However, many works have been published and we can distinguish two approaches: the analytic approximation and the numerical approximation. Johnson [32] uses an analytic approximation for American put options on a nondividend paying stock, while Geske and Johnson [25] obtain a series form for American put options on a dividend paying stock. However, the analytic approximation is often impracticable, thus the numerical approach is a natural way for the American option pricing problem.
parisons. In 1977 Brennan and Schwartz published an algorithm, based on finite differences, for the American option pricing problem [43, 7] and many other works have been published in this scope, see [21, 56, 57, 65]. Since, for the American option pricing problem the optimal exercise boundary be-longs to the solution, the Black-Scholes equation can not give the correct price for an American option1. Then, the American option pricing problem
can be viewed as a linear complementarity problem (LCP) or free boundary value problem [21, 65, 57]. We focus on the free boundary value formulation, which is very common in the so-called moving boundary value problems, that are sometimes called Stefan problems, the Austrian mathematician who studied the melting of the polar ice cap. The three main ways, for this formulation, are: front-fixing technique, penalty methods and variational formulation [21, 44]. In Chapter 4, we deal with the American option pricing problem and we study the front-fixing technique. It was used for the first time in option pricing by Wu and Kwok [66, 44, 21], and we show qualitative and numerical analysis results. We also numerically compare the front-fixing technique with classical methods for the American option pricing problem, such as the LCP method and the generalized European option method.
Until now we have considered option pricing under the Black-Scholes model. Since the Black-Scholes model hypotheses are unrealistic, the results of option pricing may be considered in an idealistic market model [36, 28, 64, 65, 4]. Therefore, there are many other models with realistic assumptions, e.g., stochastic volatility models, such as Heston and CEV model [28, 4, 36, 64]. However, in this work we only consider option pricing under the Black-Scholes model, but we extend the Black-Scholes model to a multi-asset scenario. An option may have one or more underlying assets, but we consider only two-asset scenarios. We study the exchange and spread option pricing problem, that are also exotic options. For exchange option there is an exact formula provided by Margrabe [41], whereas for spread option there is an approximation, under certain hypothesis, called Kirk’s approximation [34]. This approximation underprices or overprices the option depending on the value of the strike price [3]. Furthermore, when closed form does not exist, e.g., for American spread options, it is necessary to use a numerical approximation. The Monte Carlo method is the standard approach for multi-asset scenario rather than finite differences, although it usually takes a long time to run. In Chapter 5, we present the multigrid
1An exception is the American call option without dividend, because in this case the
on a specific grid. We briefly introduce to elementary multigrid theory and local Fourier analysis. Finally, we numerically test the multigrid technique to the exchange and spread option pricing problem.
The thesis is organized as follows. In Chapter 1, we briefly introduce the Black-Scholes model and the options, including some exotic options. In Chapter 2, we describe classical methods for option pricing and we focus on finite difference methods. In Chapter 3, we show how classical finite difference methods, such as Crank-Nicolson scheme, provide spurious oscillations, when the equation becomes convection-dominated, and we explain how to overcome this problem with the exponentially fitted scheme. In Chapter 4, we deal with the American option pricing problem and we present the front-fixing technique. Later on, in Chapter 5, we introduce the multigrid technique and we apply it to the exchange and spread option pricing problem as an example of a multi-asset option pricing problem. We numerically compare methods through numerical experiments, which are presented in Chapter 6. Finally, we draw some conclusions and we discuss some possible future developments.
The Black–Scholes model
We recall some fundamental concepts of mathematical finance. For a rig-orous treatment we refer to [36, 4, 28]. We explain the Black-Scholes (B-S) model. Fischer Black, Myron Scholes and Robert Merton gave a fundamental contribution to the option pricing theory in the early 70s. The Black-Scholes-Merton model, briefly Black-Scholes model, has had a huge influence in the way that traders price options.
We denote the cumulative distribution function of the standard normal distribution by Φ(x) and with N (a, b) we denote the normal distribution with mean a and variance b.
1.1
The model
First of all, we recall the definition of Brownian motion. We denoted by P the market measure and let (Ω,F , P) be a fixed probability space with the natural filtration {Ft}t≥0.
Definition 1.1 (Brownian motion (Wiener process)). A process (Bt)t≥0 is a
Brownian motion on [0, T ] ⊂ R if : B0 = 0. If 0 ≤ t1 ≤ · · · ≤ tn ≤ T, then (Bt1, Bt2 − Bt1, . . . , Btn − Btn−1) are independent. If s < t, (Bt− Bs) have a N (0, t − s) distribution. The trajectories 1 of (B
t) are almost surely continuous.
In the Black-Scholes model, if S is a stock with a drift rate µ and volatility σ, then the dynamics of S is described by the geometric Brownian motion, i.e.,
dSt = St(µdt + σdBt∗), t > 0, (1.1)
where St is the stock price at time t, Bt∗ a P-Brownian motion and S0 a fixed
value. If Q is the equivalent martingale measure, the dynamics of St is given
by
dSt= St(rdt + σdBt), t > 0, (1.2)
where Btis a Q-Brownian motion. Here, for the sake of simplicity, we do not
make distinction between P-Brownian motion and Q-Brownian motion. Remark 1.2. In the Black-Scholes model the price of a risk-free instrument is described by
dBt = rBtdt
where r is the risk-free rate.
With these assumptions, we exclude the arbitrage opportunity, see [36, 4, 28].
An explicit solution of equation (1.2) can be derived by Itˆo’s formula, so we obtain St= S0exp r − σ 2 2 t + σBt , that is, St is a log-normal variable, i.e., log St is normal.
Let f be the fair price of some derivatives with underlying S, which depends only on S and t. If the spot price S has a dynamics as (1.1), then we obtain that the price f must satisfy the B-S partial differential equation (B-S PDE), see [36, 28] for further details,
∂f ∂t + 1 2σ 2S2∂ 2f ∂S2 + rS ∂f ∂S = rf (1.3)
where r is the risk-free rate. There are many hypotheses underlying B-S PDE, see [36, 4, 28], but we neglect these because we focus our interest in understanding how to solve efficiently B-S PDE.
Remark 1.3 (Dividend Yield). The Black-Scholes equation (1.3) can be gen-eralized to the case of continuous dividend yield q in the following way:
∂f ∂t + 1 2σ 2S2∂ 2f ∂S2 + (r − q)S ∂f ∂S = rf where the stock price process (St)t≥0 is given by
Remark 1.4 (Multidimensional case). We can generalize equation (1.3) to a multi-asset environment: ∂f ∂t + 1 2 n X i,j=1 σiσjρijSiSj ∂2f ∂Si∂Sj + n X j=1 (r − qj)Sj ∂f ∂Sj = rf (1.4)
where σi and qi represent the volatility and dividend yield of the i-th asset,
and ρij is the correlation between assets i and j. So we have n stochastic
processes which describe the dynamics of underlying assets, i.e., dSi(t) = (r − qi)Si(t)dt + σiSi(t)dBti, t > 0, i = 1, 2, . . . , n,
where dBitdBtj = ρijdt.
Remark 1.5. The coefficients of equation of (1.3) depend on S. We can introduce a suitable change of variable which transforms equation (1.3) in a constant coefficients equation. This advantage is appreciated in the numerical methods. Indeed, if Z = ln(S), then equation (1.3) becomes
∂f ∂t + 1 2σ 2∂2f ∂Z2 + r − σ 2 2 ∂f ∂Z = rf (1.5)
and the coefficients of the latter equation are no longer dependent on S. We will see more details on this regard when we show classical numerical methods.
If we want to univocally identify the solution we must select suitable boundary conditions. Therefore, boundary conditions fully characterize deriva-tives type. In some cases, where f is an option price of a vanilla call or put, there exists a closed-form solution of B-S PDE [36, 28], but when the option is for example path-dependent or in more complicate cases, there is not a closed-form solution. Then we must solve numerically equation (1.3) with some suitable boundary conditions which characterize the contract type.
1.2
Option styles
We now describe the derivative types which we will use for numerical exper-iments, however we consider only option case.
An option is a contract which offers the owner the right but not the obligation, i.e., an option, to buy or sell an underlying asset at a specified strike price K on a specified date T . For the simplicity of contract, the above derivative is often called vanilla option. An option is called call if it grants the right to buy at the strike price the underlying considered asset,
and an option is called put if it grants the right to sell at the strike price the underlying asset. We denote with St the spot price at time t. An option,
during its life, can be at-the-Money, in-the-Money and out-the-Money. At time t, an at-the-Money option is an option whose strike price K is equal to the spot price St. At time t, an in-the-Money call (put) option is a call (put)
option whose strike price K is less (greater) than the spot price St. At time
t, an out-the-Money call (put) option is a call (put) option whose strike price K is greater (less) than the spot price St.
The main options types are the European and American option, later on, we recall some exotic options.
1.2.1
European and American options
A European (EU) option is an option that may only be exercised at the expiry date T specified at the beginning of the contract.
An American (AM) option is an option that may be exercised at any time until the expiration of the contract. Unless specified, we consider options with underlying asset that doesn’t pay dividends. We momentarily focus on the European option case.
Remark 1.6. The payoff of a European call at time T is max(ST − K, 0),
since we will exercise our right if ST ≥ K. Otherwise, if ST ≤ K, it is more
convenient to buy the underlying asset at the spot price. Similarly, the payoff of a European put at time T is
max(K − ST, 0),
since we have the right to sell but not to buy.
The relationship between a European call (c) and a European put (p) option, with same underlying asset, expiration date and strike price K, is given by the put-call parity equation:
c + Ke−rT = p + S0.
Example 1.7. We illustrate the analysis of Black, Scholes and Merton capital structure of a company by options [5, 42, 28]. Consider a company that has assets that are financed with zero-coupon bonds (ZCBs) and stocks. The ZCBs expire in T years with a par value of K. We also suppose that the company pays no dividends. Then after T years, if assets are worth more than K, the stockholders choose to repay the bondholders, whereas if the assets
are worth less than K, the stockholders choose to declare bankruptcy and the bondholders end up owning the company. Therefore, the value of stocks in T years is equal to max(ST − K, 0), where ST is the value of the company
assets at time T and it is clear that stockholders have a T -year European call option on the company assets with strike price K. The bondholders payoff is min(ST, K), that is equal to K − max(K − ST, 0), so the current value of
ZCBs in T -years is equal to the difference between the present value of the ZCBs par value and the present value of a T -year European put option on the asset with strike price K.
Therefore, if c and p denote the present value of the call and put options on assets, respectively and r is the risk-free rate, we obtain
The value of stocks= c.
The value of debt= Ke−rT − p.
Let S0 be the current value of the company assets, then the value of assets
must be equal to the liabilities
S0 = c + Ke−rT − p,
and we finally obtain the put-call parity equation c + Ke−rT = p + S0.
From the Black-Scholes model, knowing that the payoff of a call at time T is cT = (ST − K)+ and the payoff of a put at time T is pT = (K − ST)+,
we can derive the current non-arbitrage price of call and put, [28, 36]:
c0 = S0Φ(d1) − Ke−rTΦ(d2), (1.6) p0 = Ke−rTΦ(−d2) − S0Φ(−d1), (1.7) with d1 = ln(S0/K) + (r + σ2/2)T σ√T , d2 = d1− σ √ T ,
where r is the risk-free rate and σ is the volatility of the underlying asset S. Remark 1.8. In (1.6), Φ(d2) has a very simple meaning, i.e., it is the
prob-ability, in a risk-free world, that the call is exercised. Therefore the term S0Φ(d1)erT is the expected value, in a risk-free world, of the payoff of the
emphasize this fact by rewriting the Black-Scholes formula for call in the following equation c0 = e−rT S0erT Φ(d1) Φ(d2) − K Φ(d2)
where we can discern the – discounting factor, e−rT
– expected value of ST, conditioned by ST > K, S0erT Φ(dΦ(d1)
2)
– strike price, K
– probability of exercise a call, Φ(d2).
Let’s now discuss how to deal with American options. Since, it does not exist a closed-form solution, as in the case of European options, to obtain the non-arbitrage price for American options, we have to provide an approximate solution given by some numerical methods, such as binomial lattice, Monte Carlo method or finite difference methods. Later on, we show how to use finite differences for the American option pricing problem.
We have seen the put-call parity, which is only true for EU options. How-ever, it is possible to obtain an analogue relation for AM options without dividends [28, 64]:
S0− K ≤ C − P ≤ S0− Ke−rT,
where C and P are the values of an AM call option and an AM put option, respectively.
Remark 1.9 (American call options without dividends). It can be shown that for a EU call c it holds, see [28, 64]
c ≥ max(S0− Ke−rT, 0),
so c ≥ S0− Ke−rT. The owner of an AM call has the same exercise
oppor-tunity of the owner of a EU call, thus C ≥ c. Therefore C ≥ S0− Ke−rT
and if r > 0, it follows that C > S0− K and, if early exercise is optimal, C
would be S0−K. Then, early exercise is never optimal, see [28, 64] for further
details. However, the fair price for an AM call option without dividends2 is
equal to the price of the equivalent EU call option. If the option has a dividend, early exercise may be optimal near the dividend issue date. Later on, we will be interested in the American call option pricing problem, so we will suppose that the stock underlying the options has a dividend during its life.
Remark 1.10 (American put options without dividends). Contrary to AM call, for AM put it may be optimal the early exercise if q = 0. Indeed, if we are in the extreme case where S = 0, then, the early exercise earns to the owner K, but if the investor waits to exercise, the payoff will be less than K, because the price S cannot be negative. So, it is reasonable to consider AM put options without dividends.
Remark 1.11. If we have an option with dividend Q, the put-call parity becomes
c + Q + Ke−rT = p + S0
for EU options and
S0− Q − K ≤ C − P ≤ S0− Ke−rT
for AM options.
Let’s now discuss the case of the exchange option as exotic option.
1.2.2
Exotic options
We consider exchange options as an example of multi-asset and exotic op-tions.
The exchange options are options that allow to exchange an activity with another [28]. We consider a EU option which allows to exchange one asset S2 with another asset S1 at expiration date T . Therefore, the payoff will be
max(S1(T ) − S2(T ), 0).
If r is the risk-free rate and if we suppose that S1 and S2 have a geometric
Brownian motion dynamic with volatility σ2 and σ1, respectively, we have
the Q-dynamics
dSi(t) = Si(t)(rdt + σidBti), t > 0, i = 1, 2,
where ρ is the correlation between two Brownian motions Bt1 and Bt2, i.e., dB1dB2 = ρdt. Then, we can derive the two-asset Black-Scholes equation
rf = ∂f ∂t + 1 2(σ1S1) 2∂ 2f ∂S2 1 + 1 2(σ2S2) 2∂ 2f ∂S2 2 + σ1σ2ρS1S2 ∂2f ∂S1∂S2 + rS1 ∂f ∂S1 + rS2 ∂f ∂S2 . (1.8)
A formula for pricing this option is Margrabe’s formula [41, 28]. We also suppose that q1 and q2 are the dividend yields of S1 and S2, respectively.
Then, the fair price of the exchange option is given by
EO = S1(0)e−q1TΦ(d1) − S2(0)e−q2TΦ(d2) (1.9) d1 = ln(S1(0)/S2(0)) + (q2− q1+ ˆσ2/2)T ˆ σ√T d2 = d1− ˆσ √ T ˆ σ = q σ2 1 + σ22 − 2ρσ1σ2.
It is interesting to note that the fair price does not depend on the risk-free rate r [41, 28].
Remark 1.12. If we consider an option which allows to obtain the best or the worse between two asset,
min(S2(T ), S1(T )), max(S2(T ), S1(T ))
we can observe that
min(S2(T ), S1(T )) = S1(T ) − max(S1(T ) − S2(T ), 0),
max(S2(T ), S1(T )) = S2(T ) + max(S1(T ) − S2(T ), 0).
So, we can see this option as a combination of a position on one of the two assets with an exchange option.
A generalization of exchange option to exchange one asset with another is the spread option, which is another exotic option. In a call spread option the payoff is given by
max(S1(T ) − S2(T ) − K, 0)
and in a put spread option it is given by
max(K − S1(T ) + S2(T ), 0)
where K is the strike price. When K is zero the spread option becomes an exchange option. The Kirk approximation is an option pricing formula for spread option. When the strike is close to zero, the Kirk approximation tends to underprice the spread option while, when the strike is far from zero, it tends to overprice, as Bjerksund and Stensland showed in [3]. See [3, 47, 37] for further details for spread option pricing. We will see how to price these types of options by solving equation (1.8) with multigrid method .
1.3
Basic problems
In order to solve equation (1.3) we must have an initial condition and bound-ary conditions. From a numerical point of view it is convenient to apply the substitution τ = T − t, in order to solve forward in time. So equation (1.3) becomes ∂f ∂τ = 1 2σ 2S2∂ 2f ∂S2 + rS ∂f ∂S − rf. (1.10)
Using the same notation above, we introduce some instances which we will use in numerical experiments, then we present pricing problems for European and American options. The domain is R × (0, T ).
Problem 1 (European call). ∂c ∂τ = 1 2σ 2S2∂2c ∂S2 + rS ∂c ∂S − rc c(S, 0) = max(S − K, 0), ∀S (1.11) c(0, τ ) = 0, c(S → ∞, τ ) = S, ∀τ Problem 2 (European put).
∂p ∂τ = 1 2σ 2S2∂2p ∂S2 + rS ∂p ∂S − rp p(S, 0) = max(K − S, 0), ∀S (1.12) p(0, τ ) = Ke−rτ, p(S → ∞, τ ) = 0, ∀τ
The main difficulty in pricing an American option is early exercise possi-bility. So, at each point of the domain, to avoid arbitrage, the option value cannot be less than the intrinsic value, i.e., the immediate payoff if the option is exercised, is
c(S, τ ) ≥ max(S(τ ) − K, 0), p(S, τ ) ≥ max(K − S(τ ), 0).
For example, if p(S, τ ) ≥ max(K − S(τ ), 0) is not satisfied, it is possible to make an arbitrage if we buy the option and the underlying stock and immediately exercise the option. Then we can generalize problems 1 and 2 to American options simply taking into account the above inequalities. We will give more details when we present classical finite difference methods.
1.4
Risk sensitivities
In this section we recall some risk sensitivities, also known as greek letters, or simply Greeks, or sensitivities. All Greeks measure a risk dimension of a position on options. We focus on ∆, Γ and Θ.
∆ is defined as the first derivative of f with respect to the underlying asset price S:
∆ = ∂f ∂S.
Many traders use ∆ to create the Delta neutral position, i.e., the position with ∆ equal to 0. This strategy is called Delta hedging, because traders protect their positions by the change of the underlying asset price.
Remark 1.13. From Black-Scholes formula for call/put, we obtain that ∆c= Φ(d1) ∆p = Φ(d1) − 1
where ∆c and ∆p are the call ∆ and put ∆, respectively.
Γ is the second derivative of f with respect to S: Γ = ∂
2f
∂S2.
Γ measures how many times Delta hedging must be rebalanced, i.e., if Γ is small then ∆ changes slowly and the rebalancing to obtain Delta neutral position should not be done frequently.
Remark 1.14. From the Black-Scholes we have formula for call/put
Γ = Φ 0(d 1) S0σ √ T where Φ0(x) = √1 2πe −x2/2 .
Θ is the first derivative of f with respect to time t: Θ = ∂f
∂t.
It indicates time decay of the option, i.e., it measures the value change of the option when time passes.
Remark 1.15. Concerning call/put options we obtain Θc = −S0Φ0(d1)σ 2√T − rKe −rT Φ(d2) Θp = −S0Φ0(d1)σ 2√T + rKe −rT Φ(−d2)
Obviously we can define sensitivities of a portfolio composed by positions on the same underlying asset [28, 64]. If the current value of the portfolio is Π, then [28]
Θ + rS∆ + 1 2σ
2S2Γ = rΠ
and if ∆Π is the change in the portfolio value at time ∆t with neutral Delta position, then by Taylor’s formula up to second order we obtain
Θ∆t + 1
2Γ(∆S)
2 ≈ ∆Π.
As we will see, greek letters allow us to see how classical finite difference methods produce a numeric solution of (1.3) with spurious oscillations. In the next chapter, we introduce classical methods and we focus on finite difference methods.
Classical methods
We are now interested for option pricing, i.e., we want to find the fair price of an option. There are three classical approaches:
1. Binomial lattices
2. The Monte Carlo method (MCM) 3. Finite difference methods (FDM).
In the next section we introduce briefly these methods. Binomial lat-tices are the standard way for option pricing when we have a discrete market model. Monte Carlo methods are very useful for pricing multi-asset deriva-tives, but they are very expensive from a numerical point of view. They are also used to study future scenarios with hedging strategies. Finite difference methods allow us to solve directly the Black-Scholes PDE, and obviously they use Black-Scholes model for modelling asset price dynamics. Monte Carlo methods, are very useful to evaluate path-dependent derivatives, while binomial lattices and FDM are used for the valuation of American options. Furthermore, these methods can be used to estimate risk sensitivities, e.g., Delta, Gamma and Theta.
We will focus our interest on finite difference methods. Particular atten-tion is devoted to classical methods such as Crank-Nicolson. Before studying FDM we introduce binomial lattices and Monte Carlo methods, and we show how these methods can be used for option pricing.
2.1
Binomial Lattices
A simple way for evaluating options in a risk-free world is to built a binomial price tree. This approach was introduced by Cox, Ross and Rubinstein in
1979 [13]. Therefore the underlying model is called binomial option pricing model. It is very used for American options as well as for Bermuda options1.
We now present the simple binomial tree and some generalization.
Let S0 be the stock price and f the option price with this stock as
un-derlying asset and T as expiration date. During its life, the stock price may increase from S0 to S0u or go down from S0 to S0d, with u > 1, d < 1. We
indicate with fu, fd the option value if the stock price increases or goes down
respectively, see figure 2.1. If r is the risk-free rate we obtain the formulas
S0 f S0u fu S0d fd
Figure 2.1: Binomial lattice with one step for option pricing [28]
f = e−rT[pfu+ (1 − p)fd], (2.1)
where p is the stock price increase probability
p = e
rT − d
u − d . (2.2)
Obviously we can generalize with a two-step tree, with a time step ∆t, see figure 2.2. Therefore, we obtain
f = e−rT[pfu+ (1 − p)fd] (2.3)
p = e
r∆t− d
u − d . (2.4)
and if we apply (2.1) to fu and fd we arrive to
f = e−2r∆t[p2fuu+ 2p(1 − p)fud+ (1 − p2)fdd]. (2.5)
Example 2.1. Now we describe how binomial lattices are used for the valua-tion of American opvalua-tions. If we consider an opvalua-tion without dividends, since in final node the American option value is the same as European option, the
S0 f S0u fu S0d fd S0u2 fuu S0ud fud S0d2 fdd
Figure 2.2: Binomial lattice with two step
procedure is to go back in the tree and check at each node if early exercise has been advantageous. However, as we have seen, if we consider an Ameri-can call option without dividends it is not optimal to exercise option before maturity date. On the other hand, if the option has a dividend during its life it may be optimal to exercise before a dividend issue date. So for every nodes, before expiration, the option value is the maximum value between
The value given by equation (2.3). The value given by early exercise.
Remark 2.2 (Volatility Calibration). With elementary2 probability steps [13,
28], we find
u = eσ
√
∆t, d = e−σ√∆t.
When the interval step size is ∆t, we can set up the binomial method with the following equations:
u = eσ √ ∆t d = e−σ √ ∆t p = a − d u − d a = er∆t.
2Just note that the volatility σ is defined so that σ√∆t is the standard deviation of
Remark 2.3 (Dividend yield). We suppose now that the stock has a dividend yield equal to q. We also suppose another condition [13, 28]
u = 1
d (2.6)
and in the same way as before we obtain u = eσ √ ∆t d = e−σ √ ∆t p = a − d u − d a = e(r−q)∆t
where a is often called growth factor. It is clear that using (2.6), at time i∆t there are i + 1 possible prices
S0ujdi−j j = 0, 1, . . . , i.
However, it is most realistic that the stock has a known dividend Q instead of a known dividend yield. If we suppose that dividend issue date is τ , and k∆t ≤ τ ≤ (k + 1)∆t, then we have these possible cases:
1. If i ≤ k the tree nodes at time i∆t are the same to the prices S0ujdi−j j = 0, 1, . . . , i.
2. If i = k + 1 the tree nodes are the same to the prices S0ujdi−j− Q j = 0, 1, . . . , i.
3. If i = k + 2 the tree nodes at time i∆t are the same to the prices (S0ujdi−1−j− Q)u and (S0ujdi−1−j− Q)d j = 0, 1, . . . , i − 1,
so there are 2i nodes instead of i + 1. In the case of i = k + m there are m(k + 2) nodes instead of k + m + 1.
Therefore, the tree does not recombine and the number of nodes may become huge.
Example 2.4. We apply binomial tree to American options on a non-dividend paying stock. Suppose to divide the option life in N intervals with size ∆t. We refer to the j-th node at time i∆t as the node (i, j). So the stock price at (i, j) is S0ujdi−j. Hence at expiration date the option value is
fN,j = max{S0ujdN −j− K, 0} j = 0, 1, . . . , N.
for a call and
fN,j = max{K − S0ujdN −j, 0} j = 0, 1, . . . , N.
for a put. In any previous node we compare the value obtained without early exercise with the option value with early exercise, so we obtain for call and put option respectively
fi,j = max{S0ujdi−j − K, e−r∆t[pfi+1,j+1+ (1 − p)fi+1,j]}
fi,j = max{K − S0ujdi−j, e−r∆t[pfi+1,j+1+ (1 − p)fi+1,j]}
for 0 ≤ i ≤ (N − 1) and 0 ≤ j ≤ i. The option value at time i∆t does not only capture the early exercise effect at time i∆t, but also the early exercise possibility of future dates. As we have seen for the American call option without dividends, the early exercise is not optimal, so its fair price is the same of the corresponding European call option.
2.2
The Monte Carlo method
The Monte Carlo method (MCM) allows not only to price derivatives but also to simulate hedging strategies. As we will see, MCM allows pricing multi-asset option. Although MCM is a flexible method, from a numerical point of view it is very expensive. We apply MCM for option pricing.
For the sake of simplicity, we consider momentarily only one-asset deriva-tives. Since the dynamics of the stock price is described by a stochastic differential equation, MCM uses the random generation of sample paths for simulation of the underlying asset. Therefore, we can use MCM for path-dependent options. Suppose we have an option with expiration date T with constant interest rate, then a simple procedure to price this derivative is:
1. Simulate the underlying asset path, in a risk-free world. 2. Evaluate the option payoff.
3. Repeat step 1 and 2 in order to obtain some payoff values in a risk-free world.
4. Estimate the expected value of the payoff, with arithmetic mean. 5. Obtain the current value of the derivative by discounting the expected
value of the payoff.
Consider the following stochastic differential equation which models the underlying asset dynamic:
dSt= a(St, t)dt + b(St, t)dBt. (2.7)
Recall that the increases of the Brownian motion are independent and Bt− Bs ∼ N (0, t − s) ∼
√
t − s · N (0, 1),
then, a simple discretization of (2.7) by means of the Euler scheme is St+∆t = St+ a(St, t) · ∆t + b(St, t) ·
√
∆t · Z Z ∼ N (0, 1),
where ∆t is the discretization time step. Given a time interval [0, T ] and a discretization πn = {0 = t0 ≤ t1. . . ≤ tn = T }, with ti+1− ti = ∆t,
we generate (Zi)i=1:N independent Gaussian random variables and then we
define the following sequences, where, to simplify the notation, we indicate with Si = Sti and Zi = Zti:
Si+1= Si+ a(Si, ti) · ∆t + b(Si, ti) ·
√
∆t · Zi, i = 0, 1, . . . , N − 1,
where S0 is fixed.
Remark 2.5. There are two sources of errors in path generation:
Sampling error, which can be mitigated by using variance reduction techniques [8, 28].
Discretization error, due to the type of discretization.
Therefore, suppose the dynamics of S is described by the simple geometric Brownian motion, i.e.,
dSt= St(ˆrdt + σdBt), (2.8)
where ˆr is the expected interest rate in a risk-free world3 and σ is the
volatil-ity. The Euler scheme yields at time ti
Si+1= (1 + ˆr∆t)Si+ σSi
√ ∆tZi,
3If S does not pay dividends, ˆr = r, while if S pays dividends, ˆr = r − q, where r is
but, by using Itˆo’s Lemma, we may find a solution of (2.8): St= S0exp ˆ r − σ 2 2 t + σBt . Discretizing the above equation we get
St+∆t = Stexp ˆ r − σ 2 2 ∆t + σ√∆tZ , Z ∼ N (0, 1)
and rewriting this, we find an equation which is simple to vectorize in a numerical program code
log St+∆t− log St= (ˆr − σ2/2)∆t + σ
√ ∆tZ. Multi-asset derivatives
We now consider a multi-asset derivative, which depends on d underlying assets. Let ˆri, σi be the expected interest rate and the volatility, respectively,
for the i-th asset, and we indicate with ρij the correlation between the i-th
and j-th asset. As we have seen, for one-asset, the discrete version of i-th process Si(t) is
Si(t + ∆t) = (1 + ˆri∆t)Si(t) + σiSi(t)
√
∆tZi(t),
where Zi is a Gaussian r.v., and Zi, Zj have a correlation ρij for 1 ≤ i, j ≤ d.
The standard way to generate a sample of a multidimensional Gaussian r.v. with covariance matrix Σ is to find the Cholesky factor L of Σ,
Σ = LLT
and if ˜Z = ( ˜Zi)i=1:d are independent Gaussian r.v. then we set up
Z = L · ˜Z with Z = (Zi)i=1:d.
Example 2.6. The two-asset case, i.e., d = 2, we have Σ =1 ρ ρ 1 , thus we obtain L =1 0 ρ p1 − ρ2 , therefore, Z1 = ˜Z1 Z2 = ρ ˜Z1+ p 1 − ρ2Z˜ 2,
Estimate Greek letters
We want to estimate ∂f∂x, where f is the derivative current value and x a underlying variable. With MCM we obtain an estimate ˆf of the current value, therefore after changing x by ∆x, with MCM we obtain another current value
ˆ
f∗. Then a simple estimate of ∂f
∂x is given by
ˆ f∗− ˆf
∆x .
Obviously we must keep the same sample r.v. when we estimate ˆf and ˆf∗.
2.2.1
The Longstaff-Schwartz algorithm
The Monte Carlo method is very used for path-dependent options, while the binomial and finite difference methods are used for the American option pricing problem. Longstaff and Schwartz followed another approach for the valuation of American options. They have used Monte Carlo method and the least squares approach [38]. They have obtained the conditional expected value of continuation by regression. We give an outline of the Longstaff-Schwartz algorithm, by the same example of them [38, 28]. Another approach is provided by Andersen [1, 28].
Example 2.7. We consider an American put option with a non-dividend pay-ing stock. The strike price is K = 1.10, the put is exercisable at times 1, 2, amd 3, where T = 3. The risk-free rate is r = 0.06. For the sake of simplicity, we consider only eight sample paths for the stock price, which are given by the following matrix
P = 1.00 1.09 1.08 1.34 1.00 1.16 1.26 1.54 1.00 1.22 1.07 1.03 1.00 0.93 0.97 0.92 1.00 1.11 1.56 1.52 1.00 0.76 0.77 0.90 1.00 0.92 0.84 1.01 1.00 0.88 1.22 1.34 ,
where each rows indicate the number of paths and each columns indicate the times, starting from t = 0 to t = 3. We now consider the cash flows at time 3, that is, if the option was exercisable only at T , the option value would be
the payoff at time T , C = − − 0.00 − − 0.00 − − 0.07 − − 0.18 − − 0.00 − − 0.20 − − 0.09 − − 0.00 .
If the put is in-the money at time 2, the optionholder must decide if exercise the option. From P , there are only 5 paths for which the option is in-the-money at time 2, they are given by rows 1, 3, 4, 6 and 7. We denote by X the stock prices at time4 2 for these paths, P (i, 3) for i = 1, 3, 4, 6, 7, and we denote by Y the discounted value of C(i, 3) for i = 1, 3, 4, 6, 7. Thus, we suppose that
Y = a + bX + cX2 (2.9)
and we fit the value of a, b, and c by using the least squares approach, i.e., the values which minimize the residues sum
5
X
i=1
(Yi − a − bXi− cXi2).
We observe that Y is the value of the option not exercised. We obtain a = −1.070, b = 2.983 and c = −1.813. Therefore, we have regress Y on a constant, X and X2, and we have find the conditional expectation function E[Y |X]. We can now compare the value of immediate exercise at time 2, given by the payoff function K − S with stock prices at time 2 for in-the-money paths, with the value from continuation, given by the relation (2.9) after the fitting. If the value of immediate exercise is greater than the value from continuation, it is more convenient exercise the option at time 2, so the cash flow matrix becomes
C = − 0.00 0.00 − 0.00 0.00 − 0.00 0.07 − 0.13 0.00 − 0.00 0.00 − 0.33 0.00 − 0.26 0.00 − 0.00 0.00 .
Where the last column becomes zero when the immediate exercise at time 2 is convenient and so there is not further cash flows. Proceeding recursively, we watch the prices at time 1 and we examine if the option should be exercised at time 1. In this case, Y may contain cash flows at time 2 or at time 3, but we have to discount back each of them to time 1. Therefore, we obtain the stopping rule matrix
T = 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 ,
where 1 denotes the exercise date and we obtain the option cash flow matrix, by exercising the option in the columns where there is a one in T ,
C = 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.07 0.17 0.00 0.00 0.00 0.00 0.00 0.34 0.00 0.00 0.18 0.00 0.00 0.22 0.00 0.00 .
Thus, discounting C back to time zero and averaging over all rows we obtain the American put price.
We conclude paying attention to Monte Carlo’s error. Let M be the number of simulations, in addition to calculate a mean for estimating the current value, then, we calculate the standard deviation ω obtained with the M simulations. The standard error of our estimate is
ω √
M,
so the MCM decays as M−1/2 regardless of the dimension d. So if we want a double estimate precision we must multiply by 4 the number of simulations.
2.3
Finite difference methods
Beware. Until this moment, we considered the price S as a stochastic process and we denoted this by the probability standard notation (St)t≥0, where St is
the process at time t. Now we consider S as a space variable that may change in time and we refer to S(t) as the continuous price at time t, and we will denote by Sn the discrete price at time tn.
In this section we present a summary of finite difference methods applied to pricing derivatives. Finite difference methods (FDM) allow us to evaluate an option by solving the corresponding PDE. In particular we focus on clas-sical FDM as the explicit, implicit and Crank-Nicolson scheme. We point out how these methods can fail, and how we can interpret this instability from a financial point of view. Crank-Nicolson scheme, in a suitable configuration of parameters, provides a solution with spurious oscillation [29, 18, 17, 20], but we will see this in the next chapter. We will see also how FDM can be applied to American options and barrier options [57, 58, 8]. First of all, we recall some fundamental numerical analysis facts.
2.3.1
Motivations
Binomial lattices and Monte Carlo are methods that can be used for option pricing. However, if we use one of these simulative methods, we generate many possible trajectories with specific initial conditions, i.e., we generate many possible trajectories of the dynamic of the underlying asset price. This means that our results depend on the specific initial condition, and if we want to know the value of the derivative with another starting price, we must repeat all the simulations, and so this requires a huge work time. With FDM, since the price is seen as a spatial coordinate, it is sufficient to solve the corresponding PDE, associated to the option price, on a specific grid to know the derivative value for each asset initial price. Other reasons of why we use FDM are:
• With FDM there is a clear relation between precision and computa-tional cost, unlike Monte Carlo methods. Furthermore, the error im-pact on MCM has not a simple interpretation unlike FDM. Therefore, FDM is more efficient than the other methods.
• We can simple deal with complex options.
• Finite difference methods succeed in capturing early exercise with a continuous time approximation.
However, with finite difference methods we encounter some difficulties:
• The driving process is Markovian and this does not reflect path-dependent options [57].
• The number of underlying assets must be small, if we want an efficient method.
2.3.2
Fundamentals of numerical analysis
Let us recall some numerical analysis aspects. Let L be a differential operator, and Lh its approximation.
Definition 2.8. We define the local discretization error (or local truncation error ) by
δ(x) := Lu(x) − Lhu(x)
Definition 2.9. We say that Lh approximates L with order p > 0 around
the point x, if
δ(x) = O(hp) where h is the step size discretization.
Definition 2.10. We define the global discretization error by en := u(xn) − un
where un is the numerical solution.
Therefore, the difference between the exact and numerical solution is called global discretization error. It is the accumulation of the local dis-cretization errors caused by many iterations, while the local disdis-cretization error is due to one step iteration of approximation.
Definition 2.11. A method is convergent if the global error tends to zero as the step size goes to zero. A method is convergent of order p if the global error goes to zero as hp tends to zero.
Definition 2.12. A method is consistent if the local discretization error is O(h). A method is consistent of order p if δ(·) = O(hp).
Definition 2.13. Let || · || be a norm on Rn. A numerical method is said || · ||-stable if
max
i ||ui|| ≤ C||u0||
where uiis the numerical solution at xi = ih. and C is a constant independent
of h.
If a numerical method is stable for any grid without restriction on h, it is called unconditionally stable.
A fundamental theorem of numerical analysis is the Lax Equivalence The-orem.
Theorem 2.14 (Lax equivalence theorem). Given a consistent finite dif-ferences method for a well-posed linear initial value problem, the method is convergent if and only if it is stable.
2.3.3
A first discretization
Before we describe classical finite difference methods, we generalize the Black-Scholes equation. The typical pricing equation is
∂u ∂t + Convection z }| { a∂u ∂S + b ∂u ∂r + c ∂u ∂I + Diffusion z }| { d∂ 2u ∂S2 + eρ ∂2u ∂S∂r + f ∂2u ∂r2 = Source z }| { ru − h Z η(ξ)u(ξ)dξ | {z } Convolution −u | {z } Jump , (2.10)
where S and r are Itˆo process, a, b, c, d, e and f are functions of S, r and t, I is a coordinate that does not have a diffusion term, h is a Poisson jump intensity and η(·) is the jump density. When the I coordinate and the jump term are missing, a = rS, b = e = f = 0 and d = σ2S2/2 (2.10) becomes the
Black-Scholes equation and we mark this distinction by changing notation, i.e., the derivative value u becomes f :
∂f ∂t + 1 2σ 2 S2∂ 2f ∂S2 + rS ∂f ∂S = rf (2.11)
and we refer to (2.11) as the standard Black-Scholes PDE . We can infer some generalization of the standard Black-Scholes equation. If the option has a continuous dividend yield q, we can generalize (2.11) to
∂f ∂t + 1 2σ 2 S2∂ 2f ∂S2 + (r − q)S ∂f ∂S = rf, whereas with multi-asset derivative we have
∂f ∂t + 1 2 d X i,j=1 ρijσiσjSiSj ∂2f ∂Si∂Sj + d X j=1 (r − qj)Sj ∂f ∂Sj = rf,
where ρij is the correlation coefficient between i-th and j-th asset and qi, σi
are the dividend yield and volatility of the i-th asset, respectively. We ob-serve that the Black-Scholes equation is a parabolic PDE and the equation
(2.10) is a type of convection-diffusion equation. Therefore we can apply finite difference techniques that were developed for parabolic equations and convection-diffusion problems, but first we recall and summarize some clas-sical methods for PDE applied to the Black-Scholes equation. For the sake of clarity, at the moment we do not consider multi-asset problems.
Rewriting (2.11) as ∂f ∂t = − 1 2σ 2S2∂2f ∂S2 − rS ∂f ∂S + rf
we observe that Black-Scholes equation is a PDE in reverse time, i.e., we must use a backward iteration for advancing from maturity T toward t = 0. So, it is useful to use a reverse time change of variable by t∗ = T − t, where t∗ is time to maturity, and we finally obtain
∂f ∂t∗ = 1 2σ 2 S2∂ 2f ∂S2 + rS ∂f ∂S − rf.
For the sake of simplicity, we write t in place of t∗. Therefore, the Black-Scholes equation becomes
∂f ∂t = 1 2σ 2 S2∂ 2f ∂S2 + rS ∂f ∂S − rf. (2.12)
We can now distinguish three fundamental problems depending on bound-ary conditions [18, 22]:
1. The Cauchy problem: The solution of (2.12) is characterized by the initial condition (which is a final condition without the reverse time change)
f |t=0 = φ(S),
where f (S, t) is a function which satisfies (2.12) in R × (0, T ) and the above initial condition and φ(S) is a given function such as the option payoff. Cauchy problems emerge in the case of European and American options.
2. The Dirichlet problem: Let us define the domain D = Ω × (0, T ) where Ω ⊂ R is a bounded set, the solution f (S, t) must satisfy
f |t=0= φ(S)
f |Γ= ψ(S, t), S ∈ Γ = ∂Ω.
3. The Neumann, Robin problems: They are very similar to the Dirichlet problems. Indeed, we have
f |t=0 = φ(S) ∂f ∂η + a(x, t)f Γ = ψ(S, t) S ∈ Γ,
where ∂f∂η is the derivative of f with respect to η, the outward normal at Γ. These problems arise when modelling certain kinds of put options. Remark 2.15. There is a straightforward way to generalize these boundary problems to multi-asset problems.
If we want to use FDM, for computational purposes we must define a finite mesh and if the domain is R × (0, T ), we have to choose a large enough asset price Smax for bounding the domain with respect to the asset price. The
value Smaxmust be a price that cannot be reached by S within the considered
time interval [0, T ]. We set up two step sizes, h for price (space) direction and k for time direction. We define a uniform grid with h = Smax/M and
k = T /N , then
Si = i · h, i = 0, 1, . . . , M,
tn = n · k, n = 0, 1, . . . , N,
where SM = Smax e tN = T . We use the following notation fin = f (Si, tn).
Now we would study the European call/put option case, and we would obtain the discretization of boundary conditions. The payoff functions of a call and put option are, respectively5:
f (S, 0) = c(S) = max{S−K, 0}, f (S, 0) = p(S) = max{K −S, 0}, ∀S ∈ R. Let us consider only the call option: when the price S is large enough we may be (almost) sure that option will be in-the-money at expiration with payoff S(T ) − K. Considering that the arbitrage-free price at time t for the underlying asset is S(t), the value of option at time t requires discounting back the term K. Therefore a suitable boundary condition for a call option is
f (Smax, t) = Smax− Ke−rt ∀t.
Obviously in the case of S(t) = 0, since the asset price remains zero, the option will expire worthless
f (0, t) = 0 ∀t.
In grid notation, we have boundary conditions discretized as fi0 = max(i · h − K, 0), i = 0, 1, . . . , M
f0n= 0, n = 0, 1, . . . , N
fMn = M · h − Ke−rnk, n = 0, 1, . . . , N.
For the put option when St is large enough we may be sure that it will stay
out-of-the-money at expiration, so the option is worthless f (Smax, t) = 0 ∀t.
However, when S(t) = 0, the asset price will remain zero, so it will be in-the-money at maturity date, and discounting back to time t, we have
f (0, t) = Ke−rt, ∀t. Therefore the boundary condition discretized are
fi0 = max[K − i · h, 0], i = 0, 1, . . . , M f0n = Ke−rnk, n = 0, 1, . . . , N
fMn = 0, n = 0, 1, . . . , N.
We can now present classical finite difference methods for the Black-Scholes equation. We recall three fundamental discretizations for the spatial and time discretization of the corresponding partial derivatives and the three-point formula for the spatial second derivative:
Forward difference: ∂f (ih, nk) ∂S ≈ fn i+1− fin h =: ∂ + xf n i ∂f (ih, nk) ∂t ≈ fin+1− fn i k =: ∂ + t f n i Backward difference: ∂f (ih, nk) ∂S ≈ fn i − fi−1n h =: ∂ − xfin ∂f (ih, nk) ∂t ≈ fin− fin−1 k =: ∂ − t fin
Central difference: ∂f (ih, nk) ∂S ≈ fn i+1− fi−1n 2h =: ∂ 0 xf n i ∂f (ih, nk) ∂t ≈ fin+1− fn−1 i 2k =: ∂ 0 tf n i Three-point formula ∂2f (ih, nk) ∂S2 ≈ fn i+1− 2fin+ fi−1n h2 =: ∂xxf n i
The forward and backward differences give a first-order discretization, i.e., the discretization error is O(h) and O(k), depending on the discretization case. The central difference and the three-point formula provide a second-order discretization, i.e., the discretization error is O(h2) and O(k2),
depend-ing on the discretization case.
We can now discretize the Black-Scholes equation with a classical θ-method. First we consider the spatial discretization of (2.12) using the central difference and the three-point formula at time tn and we denote by Ai,n the
discrete operator of A(f ) := 1 2σ 2 S2∂ 2f ∂S2 + rS ∂f ∂S − rf, Ani(f ) := 1 2σ 2 i2h2· ∂xxfin+ rih · ∂ 0 xf n i − rf n i .
For the time discretization we use the forward difference at time tn, ∂t+fin.
Remark 2.16. Until now, we obtained a spatial discretization of the Black-Scholes equation, so we have a semi-discretization in space
dfi
dt = Aif,
where fi = f (Si, t) and Ai is the discrete operator Ani omitting the
depen-dence from time layer n. If F = (f1, f2, . . . , fM −1)T and A is the matrix with
coefficient defined by Ai we have an ODE system
dF
dt = AF.
Therefore, if we want a discretization of (2.12) we can apply a time dis-cretization. We can see ∂t+fn
i as a weighted average in time of the spatial
discretization, that is, let θ ∈ [0, 1] we have
where we see the LHS of (2.13) as a central difference at time tn+1/2 and
the RHS of (2.13) as a central difference at time tn+θ. The method with the
discretization equation (2.13) is said θ-method. Depending on the choice of θ we obtain classical methods :
if θ = 0, we have the explicit method. if θ = 1, we have the implicit method.
if θ = 1/2, we have the Crank-Nicolson method.
2.3.4
Explicit method
With the choice of θ = 0 we have the explicit method. Expanding (2.13) with θ = 0 we obtain fin+1− fn i k = 1 2σ 2i2h2· f n i+1− 2fin+ fi−1n h2 + rih · fn i+1− fi−1n 2h − rf n i ,
and starting from n = 0, with boundary conditions, we can solve forward in time with an explicit scheme:
fin+1 = aifi−1n + bifin+ cifi+1n n = 0, 1, . . . , N − 1, i = 1, 2, . . . , M − 1, where ai = 1 2k(σ 2i2− ri) bi = 1 − k(σ2i2+ r) ci = 1 2k(σ 2i2+ ri).
Although the explicit method is simple to implement, it is conditionally sta-ble. If we apply the explicit method to the benchmark equation for parabolic PDE, i.e., the heat equation
∂u ∂t =
∂2u
∂x2,
with matrix approach we have that the time step must be restricted by the condition
k ≤ h
2
2 to have a stable method.
Remark 2.17 (Logarithmic transformation). If Z = ln(S), then the equation ∂f ∂t = 1 2σ 2S2∂ 2f ∂S2 + rS ∂f ∂S − rf becomes ∂f ∂t = 1 2σ 2∂2f ∂Z2 + r − σ 2 2 ∂f ∂Z − rf
and after the discretization, we obtain coefficients which do not depend on i. Remark 2.18 (Probabilistic interpretation of the instability of the explicit method). The explicit method is related to trinomial lattices [28, 8]. If we replace in the explicit method the right-hand term rfin by rfin+1, we obtain
fin+1− fn i k = 1 2σ 2i2h2· f n i+1− 2fin+ fi−1n h2 + rih · fi+1n − fn i−1 2h − rf n+1 i ,
and the corresponding scheme
fin+1= a∗ifi−1n + bi∗fin+ c∗ifi+1n , where a∗i = 1 1 + rk −1 2rik + 1 2σ 2i2k b∗i = 1 1 + rk(1 − σ 2 i2k) c∗i = 1 1 + rk 1 2rik + 1 2σ 2i2k
which have a probabilistic interpretation as follows: πd= −
1 2rik +
1 2σ
2i2 : probability that the asset price decreases from
ih to (i − 1)h in a time interval k. π0 = 1 − σ2i2k : probability that the asset price remains
at ih in a time interval k. πu = 1 2rik + 1 2σ
2i2 : probability that the asset price increases from
ih to (i + 1)h in a time interval k.
Therefore, πd+ π0 + πu = 1 and the expected growth of asset price is rSk,
σ2S2k. So the three probabilities must be positive, but it is clear that this
does not always happen. If we apply a logarithmic transformation, we have that the probabilities above become respectively
− ∆t 2∆Z(r − σ 2 /2) + ∆t 2∆Z2σ 2 1 − ∆t ∆Z2σ 2 ∆t 2∆Z(r − σ 2/2) + ∆t 2∆Z2σ 2.
The variation corresponds to the S-variation from S to Se−∆Z, S and Se∆Z,
respectively.
2.3.5
Implicit method
Recall that if θ = 1 the theta method is implicit and we have:
fin+1− fn i k = 1 2σ 2 i2h2· f n+1 i+1 − 2f n+1 i + f n+1 i−1 h2 + rih · f n+1 i+1 − f n+1 i−1 2h − rf n+1 i (2.14)
and if we rewrite this equation, we obtain aifi−1n+1+ bifin+1+ cifi+1n+1 = f n i where ai = 1 2rik − 1 2σ 2 i2k bi = 1 + σ2i2k + rk ci = − 1 2rik − 1 2σ 2i2k.
In matrix form, the equation (2.14) becomes b1 c1 a2 b2 c2 a3 b3 c3 . .. . .. . .. aM −2 bM −2 CM −2 aM −1 bM −1 f1n+1 f2n+1 f3n+1 .. . fM −2n+1 fM −1n+1 = f1n fn 2 fn 3 .. . fM −2n fM −1n − a1f0n+1 0 0 .. . 0 cM −1fMn+1 ,
where we have imposed boundary conditions at time layer n in order to obtain, for each time layer n, M − 1 unknowns with M − 1 equations. So we can solve this system at each time layer to find a solution. The implicit method unlike the explicit method, is unconditionally stable.
2.3.6
Crank-Nicolson method
The Crank-Nicolson method corresponds to the choice of θ = 1/2. We ob-serve that we have an average at time tn+1and tnto obtain an approximation
at time tn+1/2. Rewriting the equation we arrive to
− αifi−1n+1+ (1 − βi)fin+1− γifi+1n+1 = αifi−1n + (1 + βi)fin+ γifi+1n (2.15)
where αi = k 4(σ 2i2− ri) βi = − k 2(σ 2i2+ r) γi = k 4(σ 2i2+ ri).
With suitable boundary conditions bc, the matrix formulation of (2.15) is M1fn+1= M2fn+ bc, where fn = (fn 1, f2n, . . . , fM −1n )T, M1 = 1 − β1 −γ1 −α2 1 − β2 −γ2 −α3 1 − β3 −γ3 . .. . .. . .. −αM −2 1 − βM −2 −γM −2 −αM −1 1 − βM −1 , M2 = 1 + β1 γ1 α2 1 + β2 γ2 α3 1 + β3 γ3 . .. . .. . .. αM −2 1 + βM −2 γM −2 αM −1 1 + βM −1 .
So we can solve these systems with iterative or direct methods in order to obtain a numerical solution. The Crank-Nicolson method, as well as the
