程序代写代做代考 chain matlab scheme algorithm FMO6

FMO6
FMO6 Lecture 8
Dr John Armstrong King’s College London August 3, 2016

FMO6
Finite Di􏺈erence Methods
Finite Di􏺈erence Methods

FMO6
Finite Di􏺈erence Methods
Risk neutral pricing
We have learned how to price the following by Monte Carlo European Call Options
European Put Options
Digital Call Options
Knockout Options
Asian Options
But what options can’t we price?

FMO6
Finite Di􏺈erence Methods
Motivation
Finite di􏺈erence methods allow us to price American Options
They given us alternative methods of pricing European Options which is great for testing
Excahange traded options on stocks are typically American We can’t price Google options yet!

FMO6
Finite Di􏺈erence Methods
European Options
In your project you might want to numerically test examples about European options. It helps to know that:
Excahange traded options on indices are typically European
Call options on non dividend paying stocks have the same price whether they are European or American.
So if you want to 􏺉nd real data to test a theory, you can.

FMO6
Finite Di􏺈erence Methods
The Black􏺋Scholes PDE
Finite di􏺈erence methods
Finite di􏺈erence methods are a method of solving PDEs (partial di􏺈erential equations)
In a Black􏺋Scholes world, the risk neutral price of a derivative on a stock obeys the Black􏺋Scholes PDE.
Vt + 1σ2S2VSS + rSVS − rV = 0 2
∂V 1 ∂2V ∂V
+ σ2S2 +rS −rV =0
∂t 2 ∂S2 ∂S
V is the price of the derivative. S is the stock price. t is time.

FMO6
Finite Di􏺈erence Methods
The Black􏺋Scholes PDE
How to remember the PDE
It’s a PDE for V
It’s 􏺉rst order in time It’s second order in S It’s linear
In other words it looks like this:
∂V ∂2V ∂V
∗∂t +∗∂S2 +∗∂S +∗V =0

FMO6
Finite Di􏺈erence Methods
The Black􏺋Scholes PDE
Dimensional analysis: The S terms
To remember the coe􏺍cients WLOG the coe􏺍cient of
∂V =1 ∂t
$years−1 So the equation must be
∂V ∂S
Each term has units of
∂V ∂t
∂2V ∂S2
+∗S with the ∗’s having units of years−1
+∗V =0
+∗S2

FMO6
Finite Di􏺈erence Methods
The Black􏺋Scholes PDE
The last coe􏺍cient
Any derivative must obey the PDE including
A derivative with payo􏺈 V = ert (i.e. the cash account). In this case
∂V ∂V
∂t =rert, ∂S =0,
∂2V
∂2S =0
−rV =0
So PDE must be:
∂V ∂t
+∗S2
∂2V ∂S2
+∗S
∂V ∂S

FMO6
Finite Di􏺈erence Methods
The Black􏺋Scholes PDE
The second to last coe􏺍cient
The stock also obeys the PDE. It satis􏺉es
We deduce that the PDE must be:
∂V ∂V
∂t =0, ∂S =1,
∂2V
∂2S =0
−rV =0
∂V ∂t
+∗S2
∂2V ∂S2
+rS
∂V ∂S

FMO6
Finite Di􏺈erence Methods
The Black􏺋Scholes PDE
Conclusion
All you have to remember is that ∗ = 1σ2! 2
∂V 1 ∂2V ∂V
+ σ2S2 +rS −rV =0
∂t 2 ∂S2 ∂S
Note that the units are dollars/year throughout.

FMO6
Finite Di􏺈erence Methods
The Explicit Method
The Explicit Method
Suppose that I know the payo􏺈 at time T as a function of S. This is VT(S).
∂V ∂2V
I can then compute ∂S and ∂S2 .
Plugging this into the Black􏺋Scholes PDE I can now compute
Using
∂V ∂t
VT−δt ≈ Vt − ∂V δt ∂t
we can now compute VT−δt
So given payo􏺈 function at time T we can approximate the
price at VT−δt.
Stepping back in time we can compute the price at time 0.

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Picture of algorithm

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Grid notation
Equivalently we compute a grid of values showing how price V varies with S and t.
δS = Smax , δt = T MN

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Let V(i,j) be the value at point (i,j) in this grid with i and j integers.
We have central di􏺈erence estimate
∂V ≈ V(i,j+1) − V(i,j−1)
∂S (i,j) Second derivative estimate
2δS
∂2V ∂S2 (i,j)
≈
V(i,j+1) − 2V(i,j) + V(i,j−1) (δS)2
By PDE, plus backwards estimate for ∂V : ∂t
V(i−1,j) ≈V(i,j) −δt∂V
∂t (i,j)
􏰔1 􏰕
≈V +δt σ2S2V +rSV −rV
(i,j)
2
SS S

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Recurrence equation
This gives a recurrence equation
V(i−1,j) = some function of V at later time i
with 􏺆initial􏺊 condition (for a call option)
V(N,j) =payo􏺈atmaturity=max{jδS−K,0}
However, we also need to consider the top and bottom boundaries

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Boundary conditions

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Boundary conditions for European Call Option
Our recurrence equation breaks down at the top and bottom boundary
We impose boundary conditions derived using simple heuristic arguments (or more rigorously limiting arguments)
When S = 0, a call option is worthless. So V(t,0) = 0. So V(i,0) = 0.
When S = Smax, it is unlikely to end out of the money.
V (t, Smax) = EQ (payo􏺈)
≈ EQ (Smax − K )
= EQ(Smax) − EQ(K) = Smax − e−r(T−t)K

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Boundary conditions for European Call Option
So our boundary conditions are:
V(N,j) =max{Sj −K,0}
V(i,0) = 0
V(i,M) = Smax − e−r(T−t)K
We have a recurrence relation for all other V(i,j) We can now solve this in Matlab

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Boundary conditions

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Step 1

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Step 2

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Step 3

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Explicit calculation
Before proceeding to the Matlab, let’s compute the di􏺈erence equation explicitly.
Black􏺋Scholes PDE
∂V 1 ∂2V ∂V + σ2S2 +rS
∂t 2 ∂S2 ∂S
Finite di􏺈erence equations
∂V(i,j) − V(i−1,j) 1 +
∂t 2
+ rSj 2δS − rV(i,j) = 0
−rV =0
􏰔V(i,j+1) − 2V(i,j) + V(i,j−1) 􏰕 (δS)2
σ 2 S j2
􏰔V(i,j+1) − V(i,j−1) 􏰕
Central di􏺈erence in S. Backwards di􏺈erence in t.

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Rearrange to get
where
V(i−1,j) = αjV(i,j+1) + βjV(i,j) + γjV(i,j−1)
α = 1 σ2Sj2δt + rSj δt 2 δS2 2δS
σ2S2δt
β = 1 − j − rδt
δS2
γ = 1 σ2Sj2δt − rSj δt 2 δS2 2δS
Check: everything is dimensionless.

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Matlab code – slide 1
function [ price, V ] = priceCallByExplicitMethod( …
K, T, S0, r, sigma, SMax, N, M )
%PRICECALLBYEXPLICITMETHOD Price a call option by the explicit method
% using the Black Scholes PDE directly
iMin = 1;
iMax = N+1;
jMin = 1;
jMax = M+1;
dS = SMax/M;
dt = T/N;
t=0:dt:T;
S=0:dS:SMax;

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Matlab code – slide 2. Boundary conditions.
V=zeros(N+1,M+1);
V(iMax,:)=max(S-K,0); % Call option payoff
V(:,jMax)=SMax – exp(-r*(T-t))*K; % Estimate for high stock price
V(:,jMin)=0; % Worthless when stock is zero

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Matlab code – slide 3. Recurrence relation.
for i=iMax:-1:(iMin+1)
for j=(jMin+1):(jMax-1)
a = (0.5 * sigma^2 * S(j)^2 * dt)/(dS^2) + r*S(j)*dt/(2*dS);
b = 1 – sigma^2 * S(j)^2*dt/(dS^2) – r*dt;
c = (0.5 * sigma^2 * S(j)^2 * dt)/(dS^2) – r*S(j)*dt/(2*dS);
V(i-1,j) = a*V(i,j+1) + b*V(i,j) + c*V(i,j-1);
end end

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Final touches
% We want to extract the actual price at S0, so use
% polynomial interpolation since S0 may not fall on a grid point
s0Index = S0/dS+jMin;
price = linearInterpolate(V(iMin,:),s0Index);
end

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Result
120
100
80
60
40
20
0 0.5
V
0.4
0.3
200
0.2
T
0.1
50
100
S
00
150

FMO6
Finite Di􏺈erence Methods
The Explicit Method
Numerical Results
Parameter choices σ = 0.3
S0 = 108 T = 0.5 K = 110 r = 0.05
Black􏺋Scholes Price
9.455
Finite di􏺈erence with M = 50, N − 500, Smax = 2S0
9.457
Finite di􏺈erence with M = 150, N − 500, Smax = 2S0
−5.8 × 10162
Something has gone terribly wrong. This is called instability.

FMO6
The Heat Equation
The Heat Equation

FMO6
The Heat Equation
Heat Equation – Motivation
The Black􏺋Scholes PDE is so complex because we’ve made a poor choice of variables.
Clearly life would be easier if eliminated r from the equations. We can do this by working in real terms
W =e−rtV S ̃ = e−rtS
We also know that by working with x ̃ = log S ̃ instead of S ̃ everything should be easier mathematically.
W =e−rtV, x ̃=−rt+log(S) In fact we can make things even easier by taking:
W =e−rtV, x=−(r−1σ2)t+log(S) 2
because x then follows driftless Brownian motion

FMO6
The Heat Equation
Change of coordinates
Lemma
Under the change of coordinates
W = exp−rt V
x = −(r − 1σ2)t + log S 2
τ = −t
The Black􏺋Scholes PDE transforms to the heat equation
∂W 1 ∂2W = σ2
∂τ 2 ∂x2

FMO6
The Heat Equation
Proof – step 1
The Black􏺋Scholes PDE is
∂V 1 ∂2V ∂V
+ σ2S2 +rS −rV =0
∂t 2 ∂S2 ∂S Writing V = exprt W we get:
∂W 1 ∂2W ∂W ert + rertW + σ2S2ert + rSert
− rertW = 0
∂t 2 ∂S2 ∂S Cancelling the ert terms:
∂W 1 ∂2W ∂W
+ σ2S2 +rS =0 (1)
∂t 2 ∂S2 ∂S

FMO6
The Heat Equation
Proof – step 2
∂W ∂W∂τ ∂W∂x ∂W 􏰔 1 􏰕∂W = + =−−r−σ2
∂t∂τ∂t∂x∂t∂τ 2∂x Note there is a potential trap here because partial di􏺈erentiation notation is not that great. It would be better to write
∂W ∂1W ∂t =: ∂0S∂1t
to emphasize that we are holding S 􏺉xed. And to write ∂W ∂1W
∂τ =: ∂0x∂1τ
to emphasize that we are now holding x 􏺉xed.
So even though τ = −t
∂W ̸=−∂W
∂t ∂τ

FMO6
The Heat Equation
Proof – step 2, continued
∂W ∂W∂τ ∂W∂x ∂W 􏰔 1 􏰕∂W = + =−−r−σ2
∂t∂τ∂t∂x∂t∂τ 2∂x
∂W = ∂W ∂τ + ∂W ∂x = 1 ∂W
∂S ∂τ ∂S ∂x ∂S S ∂x
∂2W 1 ∂W 1 ∂ 􏰔∂W􏰕 1 ∂W 1 ∂2W ∂S2 =−S2 ∂x +S∂S ∂x =−S2 ∂x +S2 ∂x2
So equation (1) two slides ago becomes:
∂W 􏰔 1 􏰕∂W 1 ∂2W 1 ∂W ∂W
− −r−σ2 +σ2 −σ2 +r =0
∂τ 2 ∂x 2 ∂x2 2 ∂x ∂x which simpli􏺉es to:
∂W 1 ∂2W = σ2
∂τ 2 ∂x2

FMO6
The Heat Equation
What have we gained?
The advantages of the heat equation are:
The Heat equation has constant coe􏺍cients which makes it much easier to understand. This is the main purpose of the change.
There is a huge literature on the heat equation which we can exploit
The coordinates are 􏺆better􏺊 because they scale correctly. For larger stock values, we should use larger grid sizes. A one dollar step size is a large step size for a one dollar stock, but a small step size for a one hundred dollar stock. Taking logs automatically scales things.
Against this:
The boundary conditions are a little more awkward
For pricing barrier options, we have transformed constant barriers (easy) to curved barriers (harder)

FMO6
The Heat Equation
Slightly di􏺈erent coordinates
Lemma
Under the change of coordinates
W = exp−rt V
x = −(r − 1σ2)t + log S 2
The Black􏺋Scholes PDE transforms to the heat equation
∂W 1∂2W =− σ2
∂t 2 ∂x2

FMO6
The Heat Equation
Hazard Warning
If you try to prove this directly you will almost certainly make the mistake of thinking
∂1W ∂1W ∂0S∂1t = ∂0x∂1t
because in the ambiguous conventional notation this becomes
∂W = ∂W ∂t ∂t
which looks plausible, but isn’t always true!

FMO6
The Heat Equation
Feynman􏺋Kac formula approach
There is an alternative, and I think much easier proof:
IfdSt =St(rdt+σdWt)
Then by Ito’s lemma xt = log(St ) − (r − 1 σ2)t follows 2
driftless Brownian motion
Black-Scholes PDE for V follows from Feynman􏺋Kac for the 􏺉rst of these equations
Heat equation for W follows from Feynman􏺋Kac for the second of these equations (once one swaps the time direction)
We deduce that the Black􏺋Scholes PDE transforms to the heat equation under the change of coordinates.
8 EXERCISE: Flesh out the details of this argument

FMO6
The Heat Equation
Boundary conditions in new coordinates
Old boundary conditions for call option V(t,S) ≈ 0 for small S V(t,S)≈S−e−r(T−t)K forlargeS V (T , S ) = max{S − K , 0}
W =e−rtV, S =e(r−1σ2)t+x 2
Boundary conditions for call option W(t,xmin) ≈ 0
−1σ2t+xmax −rT W(t,xmax)≈e 2 −e K
−1σ2T+x −rT W(T,x)=max{e 2 −e K,0}

FMO6
The Heat Equation
Di􏺈erence equation
PDE is
∂W 1∂2W =− σ2
∂t 2 ∂x2
Di􏺈erence equation is:
Wi,j − Wi−1,j 1 􏰔Wi,j+1 − 2Wi,j + Wi,j−1 􏰕 = σ2
δt 2 δx2 Simpli􏺉es to:
where
Wi−1,j = λWi,j+1 + (1 − 2λ)Wi,j + λWi,j−1
λ=1σ2 δt 2 δx2
Noticeably simpler than the di􏺈erence equation for Black-Scholes equation

FMO6
The Heat Equation
Observation
Equation is
Wi−1,j = λWi,j+1 + (1 − 2λ)Wi,j + λWi,j−1
This is a weighted average of Wi,j+1, (1 − 2λ)Wi,j and λWi,j−1 solongas(1−2λ)>0.
Physically temperature after a small time is a weighted average of nearby temperatures.

FMO6
The Heat Equation
Financially
In terms of x
Each time period δt, x moves up δx with Q-probability λ x moves down with Q-probability λ
x stays the same with probability 1 − 2λ
or in terms of S
Stock moves up by a factor e 2
(r−1σ2)δt+δx (r−1σ2)δt
with Q-probability λ Moves up by a factor e 2 with Q-probability 1 − 2λ
(r−1σ2)δt−δx
Moves down by a factor e 2 with Q-probability λ
Prices are discounted risk neutral expectations

FMO6
The Heat Equation
Con􏺉rmation of the interpretation
De􏺉ne a process x ̃
x ̃ = t+δt
Variance
 x ̃t + δx with probability λ x ̃ with probability 1 − 2λ
Expectation E(x ̃
t+δt t
t
 x ̃ − δx t
with probability λ
) = E(x )
2λ(δx)2 = 2
= σ2δt
σ2 δt 2 δx2
δx2
So in the limit as δt → 0 this is Brownian motion with drift 0 and volatility σ.
x ̃ in the limit follows same process as x

FMO6
The Heat Equation
Points used
Not all the points on the boundary are used in the calculation. White circles represent data that is not needed to calculate price at black points.

FMO6
The Heat Equation
Trinomial Tree
Pricing using a trinomial tree with risk neutral probabilities λ, 1 − 2λ, λ is equivalent to a heat equation method.
Easier to program because there is no need for boundary conditions at top and bottom. This is at the expense of unnecessary computations at unlikely points.

FMO6
The Heat Equation
Non-convergence
Note that if you keep
δx
δt
as a constant c as you re􏺉ne the grid, all data used comes
from a 􏺉xed triangle
Therefore the 􏺉nite di􏺈erence method cannot possibly converge as δt tends to 0 with c 􏺉xed. This is because you need to consider payo􏺈s at T outside the triangle to compute the expectation correctly.

FMO6
Stability
Stability

FMO6
Stability
Stability
We showed earlier that 􏺉nite di􏺈erences for the Blsack􏺋Scholes PDE only works if you choose good values of N and M (the step sizes in each direction).
We have just proved that it cannot converge if you make the seemingly obvious choice of increasing M and N at the same rate
Finite di􏺈erence equation for the heat equation is easiest to analyse. Recall it is:
where
Wi−1,j = λWi,j+1 + (1 − 2λ)Wi,j + λWi,j−1
λ=1σ2 δt 2 δx2
In fact the 􏺉nite di􏺈erence equation for the heat equation convergesifandonlyifwekeep(1−2λ)>0asδt→0. In other words it converges if and only if we can make the probabilisitic interpretation.

FMO6
Stability
Theorem
If we choose a 􏺉xed value for
λ=1σ2 δt
2 δx2
with 1 − 2λ > 0 and consider the sequence of approximate solutions given by letting δx → 0 in the explicit scheme for the heat equation. This will converge to a solution of the heat equation with the desired boundary conditions (we should add that we need some conditions such as that the boundary is compact and the boundary conditions are continuous).

FMO6
Stability
Components of proof
The proof is beyond the scope of this course.
Prove the problem is well-posed, i.e. there is a unique solution
depending continuously on the boundary conditions.
Prove the scheme is stable, i.e. if you start with a small values W at the 􏺉nal time, they will remain small as you move back in time. This means that if your solution is fairly accurate but has a small rounding ε then the e􏺈ects of that rounding error will remain small as you move back in time. (Note that the equation is linear, so to compute the e􏺈ects of the rounding error on the scheme we can simply apply the scheme to the rounding error.)
Apply the Lax Equivalence Theorem that says that for well posed problems, stability is equivalent to convergence.
Note that since our process takes weighted averages it will be numerically stable as the average of small things is still small.

FMO6
Stability
Remarks
Instability shows itself numerically as extreme sensitivity to rounding errors – i.e. numerical instability.
Our example of a calculation with bad choices of M and N illustrates the instability of the scheme vividly.

FMO6
Stability
Rate of Convergence
For given boundary conditions, the Explicit 􏺉nite di􏺈erence scheme for the heat equation using 􏺉xed
λ=1σ2 δt 2 δx2
with 1 − 2λ > 0 has an error of O(δt).

FMO6
Heat equation implementation
Implementation
Parameters
K, T, S0, r, σ, N, M, nSds. N = number of time steps M = number of x steps
nSds = number of standard deviations to include each side of x0 in the grid. 8 standard deviations would be plenty.

FMO6
Heat equation implementation
Initialization Code
x0 = log( S0 );
xMin = x0 – nSds*sqrt(T)*sigma;
xMax = x0 + nSds*sqrt(T)*sigma;
dt = T/N;
dx = (xMax-xMin)/M;
iMin = 1;
iMax = N+1;
jMin = 1;
jMax = M+1;
x = xMin:dx:xMax;
t = 0:dt:T;
lambda = 0.5*sigma^2 * dt/(dx)^2;

FMO6
Heat equation implementation
Looping Code
% Use boundary condition to create vector currW
currW=max(exp(-0.5*sigma^2*T + x) – exp(-(r*T))*K,0);
for i=iMax:-1:iMin+1
% Use recurrence for all points except jMin and jMax
currW(jMin+1:jMax-1)= lambda*currW((jMin):(jMax-2)) …
+(1-2*lambda)*currW((jMin+1):(jMax-1)) …
+ lambda*currW((jMin+2):(jMax));
% Use boundary conditions for jMin and jMax
currW(jMin)=0;
currW(jMax)=exp(-0.5*sigma^2 * t(i) + x(jMax))- exp(-r*T)*K;
end
price = currW(iMin,jMin+M/2);

FMO6
Heat equation implementation
Remarks
The code is written less naively
We use a single vector currW which holds the option price at the current time.
This saves a lot of memory
We have no loop across the space dimension. This code is vectorized.
This makes it much faster.

FMO6
Heat equation implementation
Convergence
1 10
0 10
−1 10
−2 10
−3 10
−4 10
Convergence of explicit method
−5 −4 −3 −2 −1 0 10 10 10 10 10 10
dt
Figure: Convergence of the explicit method (error against δt)
error

FMO6
Heat equation implementation
Remarks
Plot shows convergence to the Black􏺋Scholes price with nSds=8.
It has rate of convergence predicted by theory
(Note theory says it will converge to solution with our approximate boundary conditions rather than the true solution. Our boundary condition approximation is very accurate when nSds=8)

FMO6
Heat equation implementation
Practicalities
To price a European put or call use the Heat equation method
To price a Knock-out option, use Black Scholes PDE method. This is because this has a simpler boundary condition at the barrier.
To price a Knock-in option, use the fact that Knock Out + Knock In = No Barrier.

FMO6
Heat equation implementation
American Options
For an American option, suppose we’ve computed the price Vi,j at time point i.
Suppose we compute V ̃i−1,j by using the di􏺈erence equation for the Black􏺋Scholes PDE
This is the price at time i − 1 of an option you can only exercise from time i onwards.
Let Ei,j be the value obtained by exercising at time i Vi−1,j =max{V ̃i−1,j,Ei−1,j}

FMO6
Heat equation implementation
More explicitly
We have
V ̃ i − 1 , j = α j V i , j + 1 + β j V i , j + γ j V i , j − 1 where αj , βj and γj are as before.
Ei,j =(Sj −K)+ Vi−1,j = max{V ̃i,j,Ei,j}.
The same technique works for the heat equation and trinomial tree approaches.

FMO6
Heat equation implementation
Exercises
8 Prove that you can 􏺉nd a change of variables to change the Black􏺋Scholes pde into a time reverses heat equation using Feynman􏺋Kac and Itô’s lemma rather than the chain rule. (Repeat of question on earlier slides)
8 What are the boundary conditions for a put option? Value a put option using the Black􏺋Scholes PDE method. Test your answer.
8 Value a put option using the heat equation method.
8 Use the explicit 􏺉nite di􏺈erence method to price a knock out option. Test your answer.

FMO6
Heat equation implementation
Exercises cont
8 Use the explicit 􏺉nite di􏺈erence method to price a knock in option. Test your answer.
8 Use Matlab’s surf or mesh commands to reproduce the 3-d plot
8 Price an American put option. Test your answer using the Bloomberg terminals.
8 2015 – Questions 2 and 3