說明案例文件

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