说明案例文件

PAGE

1

/50

FD

Lecture:FiniteDifferenceMethods

V1,2/3/2014

Readings:Hull,8thed.,Ch.20“FiniteDifferences”StevenGolbeck

AppliedMathematicsUniversityofWashington

FD

Outline

PAGE

2

/50

1

Finite-differencemethodsIntroduction

Explicitscheme

Crank-NicolsonSchemeEarlyExercise

FD

IntroExplicitImplicitEarly

Outline

PAGE

3

/50

1

Finite-differencemethodsIntroduction

Explicitscheme

Crank-NicolsonSchemeEarlyExercise

FD

IntroExplicitImplicitEarly

PAGE

4

/50

Finite-differencemethods

Muchofoptionpricingcanbereducedtosolvingapartialdifferentialequation,e.g.Black-Scholes.

However,closed-form, yticalsolutionsrarelyexist-thisisespeciallytruewhenearlyexerciseispossible.

Numericalmethods,suchasfinite-differencingapproximatethesolutiontothePDE+b.c.’s.

Highly-flexiblecomparedtothebinomialmodel,andgenerallysuperiorinspeedandaccuracytoMonteCarloforlow-dimensionalproblems.

Referencesonfinite-differencemethodsinfinance

“PaulWilmotton tativeFinance”,Volume3,Chapter77.

“TheMathematicsofFinancialDerivatives”,Wilmott,DeWynne&Howison

“PricingFinancialInstruments”,Tavella&Randall“ImplementingDerivativesModels”,Clewlow&Strickland

Finite-differencemethods

Black-ScholesPDEforaderivativefwithunderlyingSt:

rf=∂f

+(r

)S∂f+1

2S2∂2f

t

t

∂ −δt∂St 2σ t∂S2

plusboundaryconditions(b.c.’s).

Ingeneral,itisnotpossibletoobtainclosed-formsolutionstoPDEsinmathematicalfinance.

Numerical/approximationschemesarenecessary.

Ideaistodiscretizethe“space”(St)andtimedimensions,approximatederivativeswithfinitedifferences,andsolveasystemofequationsfortheoptionvaluesontheresultinggrid.

Thegrid

Wewillconsidera2-dgrid,consistingofaspace(assetvalue)andtimedimension:

δS:gridspacingfortheassetvalue;

δt:timestepsize

Thegridismadeupoftheassetvalues:

S=iδS, i=0,1,···,M

andtimes:

t=kδt, k=0,1,...N

TheoptionvalueatthegridpointcorrespondingtoassetvalueS=iδS

andtimet=kδtisdenotedby:

i

fk=f(iδS,kδt)

FD IntroExplicitImplicitEarly

Space-timegrid:

fki

S

i

k t

8/50

FD

IntroExplicitImplicitEarly

PAGE

10

/50

Derivativeapproximation

Supposeweknowtheoptionvalueateachofthegridpoints:

i

fk=f(iδS,kδt)

Onewaytodefinethetimederivativeisusingaforwarddifference:

∂f(S,t)=lim

f(S,t+δt)−f(S,t)

∂t δt→0 δt

Anaturalapproximationintermsoftheoptionvaluesonthegridisthen:

∂f

∂t

whereS=iδSandt=kδt.

fk+1−fk

(S,t)≈i i

δt

Taylor’sTheoremandbig-Onotation

Letk≥1beanintegerandletthefbektimesdifferentiableatthepointx∈R.ThenthereexistsapolynomialexpansionwithremainderRk,δx(x)suchthat

f(x+

x)=f(x)+fÍ(x)x+fÍÍ(x)

x2+

+f(k)(x)

xk+R

(x)

δ δ 2!δ

···

k! δ

k,δx

wheretheremaindertermis:

Rk,δx(x)=O(|δx|k+1)

Thebig-Onotationisequivalenttothemathematicalstatement:

δxk+1

limRk,δx(x)=C<+∞

δx→0

forsomepositiveconstantC.

- -

Mainpoint:givesusanunderstandingofthesizeoftheerrorforagivenapproximation.

Intermsofthegridpoints,S=iδS,and:

t=kδt, t+δt=(k+1)δt

Thenexpandinpowersofδt:

t

f(S,t+δt)=f(S,t)+δt∂f(S,t)+O(δt2)

∂

∂f(S,t)=f(S,t+δt)−f(S,t)+O(δt)

∂t δt

TheapproximationerrorisO(δt):

(S,t)=i i+O(δt)

∂f fk+1−fk

∂t δt

Derivativeapproximation

Wewillalsoemployabackwardsdifferenceforthetimederivative.

approximation

error

forwarddifference:

fk+1−fk

i i

δt

O(δt)

backwarddifference:

fk−fk−1

i i

δt

O(δt)

PAGE

13

/50

FD IntroExplicitImplicitEarly

SpatialDerivative

FD

IntroExplicitImplicitEarly

15/50

Derivativeapproximation

S

∆=∂f

∂

Wewilltypicallyemployacentraldifference:

approximation

error

forwarddifference:

fk−fk

i+1i

δS

O(δS)

backwarddifference:

fk−fk

i i−1

δS

O(δS)

centraldifference:

fk1−fk1

i+ i−

2δS

O(δS2)

FD

IntroExplicitImplicitEarly

PAGE

17

/50

Derivativeapproximation

Thecentraldifferencehoweverisproblematicwhencomputingthederivativeattheboundariesofthegrid.

fk −fk

i=M =⇒

M+1 M−1

2δS

fk−fk

i=0 =⇒

1 −1

2

δS

butthegridpointscorrespondingtoi=M+1andi=−1donotexist!

Onemethodistojustuseforwarddifferencewheni=0andbackwarddifferencewheni=M.

However,theerrorintheseschemesareO(δS)comparedtoO(δS2)

forthecentraldifference.

Thereareone-sideddifferenceschemeswheretheerrorisO(δS2).

Derivativeapproximation

One-sideddifferenceswillonlybeemployedattheboundary.

approximation

error

forwarddifference:

−3fk+4fk−fk

i i+1i+2

2δS

O(δS2)

backwarddifference:

3fk−4fk1+fk2

i i− i−

2δS

O(δS2)

Derivativeapproximation

OneotherapproximationweneedisthatoftheoptionΓ:

∂2f fk −2fk+fk

Γ=∂S2=

i+1

i

δS2

i−1+O(δS2)

Therearealsoone-sideddifferenceswithfirstandsecondordererrors,andthesecanbeusedatboundaries(i=0andi=M).

Fortheapplicationswewillconsider,we’llassumethattheoptionΓvanishesattheboundaries,sowewillnotconsiderthem.( invanillacall/putpayoffsareapproxima ylinearforunderlyingvaluesfarawayfromthestrikeprice)

Usecaution:ifyouthinktheremaybenon-linearityintheoptionvalueforextremevaluesofS,thenyoumayneedtouseone-sideddifferencesontheboundaries.

Wewillconsiderageneralformofthetwo-dimensionalPDEsthataretypicallyencounteredinoptionpricing:

∂f ∂2f ∂f

−∂t=a(S,t)∂S2+b(S,t)∂S+c(S,t)f

Forexample,theBlack-ScholesPDEcorrespondsto:

2

a(S,t)=1σ2S2

b(S,t)=(r−δ)Sc(S,t)=−r

Explicitscheme

Veryeasytoimplementandunderstand.

Meantasawarm-upexerciseforothermethods.However,practitionersdonotuseit:

Thefullyexplicitmethodshouldneverbeusedduetopoorconvergenceandstabilityissues,buthasneverthelessmanagedtosurviveinasurprisinglylargenumberoffinancetextsandpapers.

from“InterestRateModels”byAndersen(BoA)andPiterbarg(Barclay’s).

Explicitscheme

Backwarddifferenceforthetimederivative.Centraldifferencesforthespacederivatives.SizeofthetruncationerrorisO(δt,δS2).

∂f ∂2f ∂f

−∂t=A(S,t)∂S2+B(S,t)∂S+C(S,t)f

⇓

fk−fk−1

fk−2fk+fk

fk−fk

−i i +O(δt)=aki+1 i i−1+bki+1 i−1+ckfk+O(δS2)

δt i δS2 i 2δS ii

ak=1σ2(iδS)2

i 2

i

bk=(r−δ)(iδS)

i

ck=−r

FD

IntroExplicitImplicitEarly

i1

fk

i

fk

fk

i1

i

fk1

Solveforoptionvalueattimestepk-1,usingoptionvaluesattimestepk

S

i

k t

23/50

FD

IntroExplicitImplicitEarly

PAGE

24

/50

Explicitscheme

Optionvalueisknownattimestepk=N(t=T).

Letg(S,T)representtheboundaryconditionattheoption’smaturity.Initializetheoptionvaluesonthegrid:

fN=gN=g(iδS,T), i=0,1,···,M

i i

Setk=Nandfortheprevioustimestep,determinetheoptionvalueforthespatialpointsi=1,2,···,M−1accordingto:

fk−1=fk+δtak(fk

−2fk+fk

)+bkδt(fk

−fk)

i i δS2ii+1

i i−1

i2δSi+1

i−1

+δtckfk+O(δt2,δt·δS2)

ii

NotethatthesizeoftheerrorinourapproximationisO(δt2,δt·δS2)

Explicitscheme

Drop theerrorterm:

fk−1=Akfk

+(1+Bk)fk+Ckfk

i ii−1

ii ii+1

wherewehavedefinedthecoefficients:

Ak=ν1ak−1ν2bk

i i 2 i

Bk=−2ν1ak+δtck

i i i

Ck=ν1ak+1ν2bk

and:

i i 2 i

δt δt

ν1=δS2, ν2=δS

Explicitscheme

Forthespatialboundaries,i=0andi=M,asymptoticresultsareoftenused.

Foracalloptiondeepinthemoney,S>>K,iteffectivelyesthepayoffofforwardcontractwiththestrikepriceKastheforwardpriceF(0,T)asitwillalmostcertainlybein-the-money:

c(S,t)≈e−r(T−t)(F(t,T)−F(0,T))=e−r(T−t)(e(r−δ)(T−t)St−K)

Intermsofthegrid,wecanimplementthisas:

f

M

k=e−δ(N−k)δtMδS−e−r(N−k)δtK, Calloption

ForacalloptionwithunderlyingpriceofS=0,theoptionisworthless,sowecanset:

0

fk=0, CalloptionSimilarresultscanbederivedforputoptions.

Explicitscheme

ternativeapproachthatisfairlyrobustformanytypesofoptionsistosetthe2ndderivativeoftheoptionvaluew.r.t.Sequalto0atk=M.

Intuition:payoffiseffectivelylinearinS.

-

∂2f

∂S2S>>K

Solvingforfk:

k

f

=0=⇒M

kM−1

−2f

δS2

k

+f

M−2=0

f

=2f

M k k

M M−1

kM−2

−f

sowecanfirstsolvefortheinteriorsolutionsattimek,thenusethosetodeterminethesolutionati=M.

Explicitscheme

Importantpoint:theexplicitschemeisconditionallystable.

Issue:asmallerrorintroducedbyroundingerrorsmay ealargeerror,renderingthemethoduseless.

Itcanbeshown(seeanyofthereferences)thattheround-offerroriscontrolledprovidedthatthetimestepischosenaccordingto:

t 2a

δS2

δ≤ k

i

1

=

(iσ)2

Forthistoholdforallassetvaluesonthegrid(Si=iδS),take

i=Mandimposethecondition:

1

δt≤(σM)2

Thisisasevereconstraint.Forσ=0.30andM=100wehavethat

δt≤0.0011,or900timestepsperyear.

K=100,r=0.05,δ=0,σ=0.20,T=1,dt=0.00225,dS=2

100

Explicitfinitedifferenceoptionpricing

ExplicitmethodBlack−Scholes

60

80

ptonpce

0 50 100

S

Crank-Nicolsonscheme

Increasedaccuracyovertheexplicitmethod,aswellasbeingunconditionally-stable.

Forwarddifferenceforthetimederivativeattimestepk.Backwarddifferenceforthetimederivativeattimestepk+1.Centraldifferencesforthespacederivatives.

Takeaverageofthefinitedifferenceapproximationsatkandk+1,withtheresultanapproximationofthePDEattimet+δt/2.

SizeofthetruncationerrorisO(δt2,δS2).

fk+1−fk

1 fk −2fk+fk

fk −fk 1

−i i=aki+1 i i−1+

bki+1 i−1+

ckfk

δt 2i

δS2

i 2δS

2ii

f −2f +f

1

k+1 k+1 k+1

+ak+1i+1 i i−1+

k+1 k+1

f −f

1

bk+1i+1 i−1+

1ck+1fk+1

2i δS2

2i 2δS

2i i

Crank-Nicolsonscheme

Gatheralltermsattimestepkononeside,withk+1ontheother:

δt fk −2fk+fk

δt fk −fk δt

fk−

aki+1 i i−1−

bki+1 i−1−

ckfk

i 2i

δS2

2i 2δS

2ii

=fk+1+

k+1 k+1 k+1

f −2f +f

t

δak+1i+1 i i−1+

k+1 k+1

f −f

t

δbk+1i+1 i−1+

δtck+1fk+1

k 2i

δS2 2i

⇓

2δS

2i i

−Akfk

+#1−Bk$fk−Ckfk

=Ak+1fk+1+#1+Bk+1$fk+1+Ck+1fk+1

ii−1

i

i

i

i+1

i

i−1

i

i

i

i+1

withtheshorthand:

ν1=δt, ν2=δt, Ak=1ν1ak−1ν2bk,

δS2 δS

i 2 i 4 i

Bk=−ν1ak+1δtck, Ck=1ν1ak+1ν2bk

i i 2 i i 2 i 4 i

FD

IntroExplicitImplicitEarly

i1

fk1

i

fk1

i1

fk1

i1

fk

i

fk

i1

fk

Solveforoptionvaluesattimestepkusingoptionvaluesattimestepk+1

S

i

k t

32/50

FD

IntroExplicitImplicitEarly

PAGE

33

/50

ii−1

i

i

i

i+1

i

i−1

i

i

i

i+1

Crank-Nicolsonscheme

−Akfk

+#1−Bk$fk−Ckfk

=Ak+1fk+1+#1+Bk+1$fk+1+Ck+1fk+1

Unlikeexplicitscheme,attimestepktheoptionvaluesassociatedwithdifferentassetgridpoints(i−1,i,i+1)arecoupledtogether.Todeterminetheoptionvaluesatstepk,mustsolvealinearsystemofequations.

Thisis,ingeneral,averyburdensomecomputationaloperationasitinvolvesinvertinga(M−1)×(M−1)matrix.

Thematricesinthiscase,however,aretridiagonalandwecanutilizeveryefficientnumericalalgorithmstosolvethesystem.

ii−1

i

i

i

i+1

i

i−1

i

i

i

i+1

Crank-Nicolsonscheme

−Akfk

+#1−Bk$fk−Ckfk

=Ak+1fk+1+#1+Bk+1$fk+1+Ck+1fk+1

Thisholdsforalli=1,2,···,M−1=⇒M−1totalequations.Writetheentiresystemofequationsinmatrixform:

MLfk=MRfk+1

TermsontheRHSareknown(solveforoptionatstepkusingvaluesatstepk+1)

MLandMRare(M−1)×(M+1)matrices.

fkandfk+1areM+1dimensionalcolumnvectors.

FD

IntroExplicitImplicitEarly

PAGE

36

/50

−A

1

1

k 1−Bk

Ak

−Ck

1

−Bk

· · ·

· · ·

−2 2

M

=

· 0 · · · ·

−C

· · · · 1−BM−2 −CM−2 0

· · · 0 −Ak

kM−1

L

k k

C

M−1

1−B

kM−1

1

Ak+1

1+Bk+1

1

k

k+11

· · ·

2

0 A+1

1+Bk+1

· · ·

f

· · · · 1+BM−2 CM−2 0

2

M=· 0 · · · ·

R

C

· · · 0 Ak+1

k+1M−1

k+1

M−1

k+1

1+B

k+1M−1

f

k k+1

0 0

k k+1

f1 f1.

.

fk=., fk+1=

f. f.

k

f

f

M−1

kM

k+1

M−1

k+1M

Crank-Nicolsonscheme

CanreducethenumberofcolumnsinMLbyimposingconditionsattheboundaries.

Supposethatfkandfkareknown,wecanredefineMLandfk:

1−B

0 M

1

1

k −Ck

Ak 1−Bk

· · ·

· · ·

−2 2

10

M

=

0 · · · ·

M−1

· · · 1−BM−2 −CM−2

· · 0 −Ak

kM−1

L

k k

1−B

f

k

f

k

1

2

−Akfk

0

.

fk=., rk=

−CM−1fM

k. .

f

kM−1

fM−2

k0 k

Crank-Nicolsonscheme

MLfk+rk=MRfk+1MLfk=MRfk+1−rkMLfk=q

fkisa(M−1)dimensionalcolumnvector.MLis(M−1)×(M−1)andtridiagonal.qisa(M−1)dimensionalcolumnvector.

ThetridiagonalstructureofMLallowsforthesystemofequationstobesolvedusingLUposition.

LU position

poseMLintoaproductofmatricesLandUwhere:

1−B

1

1

k −Ck

Ak 1−Bk

· · ·

· · ·

−2 2

M

=

0 · · · ·

· · · 1−BM−2 −CM−2

· · 0 −Ak

kM−1

L

k k

M−1

1−B

l2 1 00 · · ·

0 d2 u2 0 · · ·

1 0 0 · · · 0d1 u1 0 · · · 0

=

· 0 · · · 0 ·

· 0 · · · 0 ·

0 l3 1 · · · · 0 0 d3 · · · ·

1 0 0 · · · · d u 0

· · · 0lM−2 1 0

· · · · 0 lM−1 1

· · · 0 0 dM−2 uM−2

· · · · 0 0 dM−1

· · · · M−3 M−3

LU

position

Algorithm:

Initialize:

1

workfromthetoprowtothebottomvia:

d1=1−Bk

ld

ii−

1=−

A,

k

i

u =−

i−

1

C

i−1

k

and:

di=1−B−lu

ki

ii−

1

for2≤i≤M−1.

LU position

Sowe’veperformedtheLU position...nowwhat?

MLfk=qLUfk=q

Solveforfkintwosteps.Firstfindwsuchthat:

Lw=q

Thenfindfksuchthat:

Ufk=w

Thiscanbedoneveryefficientlyduetothesparsestructureoftheposition.IfthecoefficientsAk,BkandCkareindependentofk,

i i

i.e.timehomogeneous,thentheLU positiononlyneedstobe

performedonce,leadingtofurtherefficiency.

Solvingforfattimestepk

Algorithm:

Computeq=MRfk+1−rk.Initialize:

w1=q1

andthensequentiallyfromi=2toi=M−1:

wi=qi−liwi−1, 2≤i≤M−1

f

Next,set:

kM−1

=wM−1

dM−1

thensequentiallyworkbackwardsfromi=M−2toi=1:

wi−uifk

i

d

fk=

i+1, M−2≥i≥1

i

K=100,r=0.05,δ=0,σ=0.20,T=1withdt=1/20anddS=5

100

Crank−Nicolsonfinitedifferenceoptionpricing

Crank−NicolsonBlack−Scholes

60

80

rice

0 50 100

S

Earlyexercise

Thefinitedifferencemethodiswell-suitedtoworkwithAmerican-styleoptions.

Fortheexplicitmethod,comparetheoptionvaluetothepayofffromearlyexercise:

i

i

i−1

i

i

i

i+1

i

fk−1=maxîAkfk +(1+Bk)fk+Ckfk,Payoffk−1ï

FortheCrank-Nicolsonscheme,itismoresubtleduetothecouplingtogetherofoptionvaluesatmultipleassetvaluesattheearlierstepk−1.

AmethodthataddressesthisisProjectedSuccessiveOver-Relaxation(PSOR).

ProjectedSuccessiveOver-Relaxation(PSOR)

Recalltheformofthelinearsystem:

MLfk=q

Mi1fk+Mi2fk+···+Mi(M−1)fk

=qi, i=1,2,···,M−1

1 2 M−1

Wehaveassumedthattheboundarysolutions,fkandfk,areknownand

0 M

canbeabsorbedintoq.

IdeabehindSuccessiveOver-Relaxationistosolvethesystemofequationsi tively.

PseudocodeforPSOR

%solutionfromprevioustimestepisinitialguessfold=f

whileA>tol

A=0

fori=1toM-1updatef[i]

A=A+(f[i]-fold[i])ˆ2fold[i]=f[i]

end

end

ProjectedSuccessiveOver-Relaxation(PSOR)

Dropthetimeste belkwiththeunderstandingthatweknowwhattimestepweareat.

i

Re cekbytheindexj,whichtrackshowmanyi tionswehavegonet