converted into a set of difference equations, and the differenceequations are solved iteratively.
To illustrate the approach, we consider how it might be used to value an American put optiononanon-dividend-paying stock. The differential equation that the option must satisfy is from Chapter 12:
ae
262
Sas?
af aOF sh to
tsa rf (18.19)
Suppose that the life of the option is T. We divide this into N equally spaced intervals of length= T/N. A total of N+] times are therefore considered0, ot, 26t,...,T7
Suppose that S,,, is a stock price sufficiently high that, when it is reached, the put has virtually novalue. We define 6S = Syax/M and consider a total of M +1 equally spaced stock prices:
0, 88,285, -.., Smax
The level S,,ax is chosen so that one of these is the current stock price.
The time points and stock price points define a grid consisting of a total of (M +1) x (N+1)points as shown in Figure 18.15. The (i, /) point on the grid is the point that corresponds to time i dtand stock price j3S. We will use the variable f, ; to denote the value of the option at the (/, /) point.
Implicit Finite Difference Method
For an interior point (i, /) on the grid, 0//0S can be approximated as
of fi Ji,jtl fi Shi
8.2as 6S (18.20)
20 Sce D. Mintz, “Less is More,” RISK, July 1997, pp. 42-45.Numerical Procedures 419
{ Stock price, S
Simax e e e e ° ° e e e e4 e e e e e e ° ° eo et e e e e e ° e e e °¢ e ° e e ° ° ° ° x @
o—__0 —__-e _-e—eeeeeeeeee
rest ° ° e ° e e e e ° e
 
 
5S @ e e ° e e ° e e eTime, t
°s —e 2 o o—_ o ° ad o—-T
Figure 18.15 Grid for finite difference approach
or as
of _ fig fii Fij-t
6S
(18.21)
Equation (18.20) is known as the forward difference approximation; equation (18.21) is known asthe backward difference approximation. We use a more symmetrical approximation by averagingthe two:
Of fii — fig
as 288 (18.22)
For 0//dt, we will use a forward difference approximation, so that the value at time i 5t is related tothe value at time (i + 1) dt:OF fi i+] Sith i Sid —fi a
Gay (18.23)
The backward difference approximation for af/dS at the (7, f) point is given by equation (18.21).The backward difference at the (7, 7+ 1) point is
Figo ~ Sei5S420 CHAPTER 18
Hence a finite difference approximation for 47 /aS° at the (i, /) point is
OF _ (fia — fai fim Firga (A ‘= fists) Tos
oF _ Fuge + fij-1 — 23as? 5S?
or
(18.24)
Substituting equations (18.22), (18.23), and (18.24) into the differential equation (18.19) and notingthat S = jdS gives
itty 7 Fists fis rjdS igri — Figa 2 Fier t fini Fj
1.2.21 3S =it 2s 2° 582 hifor j=1,2,...,M@-—1landi=0,1,...,N—1. Rearranging terms, we obtainaj fii t Ofigt Cifiinr = fies (18.25)wherea; = }hrjst— Ley bt, b,=1l+o°f dt+rét, cj =—hrjst— 10°? ét
The value of the put at time 7 is max(K — S;, 0), where S; is the stock price at time T. Hence,fv,j = max(K — 76S, 0), j=O0.1,...,M (18.26)The value of the put option when the stock price is zero is K. Hence,fio=K, i=90,1,..., N (18.27)We assume that the put option is worth zero when S = Syax, so thatfim =9, i=0,1,...,N (18.28)
Equations (18.26), (18.27), and (18.28) define the value of the put option along the three edges ofthe grid in Figure 18.16, where $= 0, S = Sax, and t = T. It remains to use equation (18.25) toarrive at the value of f at all other points. First the points corresponding to time T — ét aretackled. Equation (18.25) with i = N — 1 gives
aj Fy—1j-1 + Oj fei + Cj fyi jet = fej (18.29)
for j= 1,2,...,M—1. The right-hand sides of these equations are known from equation (18.26).Furthermore, from equations (18.27) and (18.28),
v-10 = K (18.30)f—im =0 (18.31)
Equations (18.29) are therefore M — 1 simultaneous equations that can be solved for the M—1unknowns: fy11, fy—tas-++s fue After this has been done, each value of fy_),; is
2! ‘This does not involve inverting a matrix. The j = 1 equation in (18.29) can be used to express fy—12 in terms offy-1,1; the second equation can be used to express fy_),3 in terms of fy_,,); and so on. The final equation provides avalue for fy_i1, which can then be used to determine the other fy_, ;.Numerical Procedures
421
compared with K — jdS. If fy_1,; < K — jS, early exercise at time T — ét is optimal and fy_,;is set equal to K — j 6S. The nodes corresponding to time T — 2t are handled in a similar way,and so on. Eventually, foi, fo.2,---» fo.m—1 ate obtained. One of these is the option price of
interest.
The control variate technique can be used in conjunction with finite difference methods. Thesame grid is used to value an option that is similar to the one under consideration but for which ananalytic valuation is available. Equation (18.18) is then used.
Example 18.7 Table 18.1 shows the result of using the implicit finite difference method as justdescribed for pricing the American put option in Example 18.1. Values of 20, 10, and 5 were chosenfor M, N, and 8S, respectively. Thus, the option price is evaluated at $5 stock price intervals between$0 and $100 and at half-month time intervals throughout the life of the option. The option pricegiven by the grid is $4.07. The same grid gives the price of the corresponding European option as$3.91. The true European price given by the Black-Scholes formula is $4.08. The control variateestimate of the American price is therefore
Table 18.1Stackprice
(dollars) J100 0.0095 0.0290 0.0585 0.0980 0.1675 0.2770 0.4765 0.8260 1.4255 2.4350 4.0745 6.5840 10.1535 15.0030 20.0025 25.0020 30.0015 35.0010 40.005 45.00
0
50.00
4.07
4 4.08
301 ~ $474Sb = O42
Grid to value option in Example 18.1 using the implicit finite difference method
4.5
0.000.020.040.070.120.220.390.711.272.243.886.4410.1015.0020.0025.0030.0035.0040.0045.0050.00
diitie te
maturity (ronths}maturity (montis)
 
4 35 3 25 2 LS 1 0.5 00.00 0.00 90.00 0.00 0.00 0.00 0.00 0.00 0.000.01 0.01 0.00 0.00 0.00 0.00 0.00 0.00 0.000.03 002 0.01 0.01 0.00 0.00 0.00 0.00 0.000.05 0.03 0.02 0.01 0.01 0.00 0.00 0.00 0.000.09 0.07 0.04 0.03 0.02 0.01 0.00 §=©0.00 = =—0.000.17 0.13 0.09 006 003 0.02 0.01 0.00 0.000.32 0.25 0.18 0.13 0.08 0.04 0.02 0.00 0.000.60 0.49 0.38 0.28 0.19 O11 0.05 0.02 0.00Lu 0.95 0.78 0.62 045 030 0.16 0.05 0.002.05 1.83 1.61 1.36 1.09 0.81 0.51 0.22 0.003.67 3.45 3.19 2.91 2.57 2.17 1.66 0.99 0.006.29 6.13 5.96 5.77 5.57 5.36 5.17 5.02 5.0010.05 10.01 10.00 10.00 10.00 10.00 10.00 10.00 10.0015.00 15.00 15.00 15.00 15.00 15.00 15.00 15.00 15.0020.00 20.00 20.00 20.00 20.00 20.00 20.00 20.00 20.0025.00 25.00 25.00 25.00 25.00 25.00 25.00 25.00 25.0030.00 30.00 30.00 30.00 30.00 30.00 30.00 30.00 30.0035.00 35.00 35.00 35.00 35.00 35.00 35.00 35.00 35.0040.00 40.00 40.00 40.00 40.00 40.00 40.00 40.00 40.0045.00 45.00 45.00 45.00 45.00 45.00 45.00 45.00 45.0050.00 50.00 50.00 50.00 50.00 50.00 50.00 50.00 50.00422 CHAPTER 18
Explicit Finite Difference Method
The implicit finite difference method has the advantage of being very robust. It always converges tothe solution of the differential equation as 6S and ét approach zero.”” One of the disadvantages ofthe implicit finite difference method is that M — 1 simultaneous equations have to be solved inorder to calculate the J ;’s from the f;,,,;’s. The method can be simplified if the values of a f/aSand @f/aS? at point (i, j) on the grid are assumed to be the same as at point (i+ 1, j).Equations (18.22) and (18.24) then become
af fatjat — Fiat af _ Fistjai t Sieger 7 2 finsas 25S , as? 6S?
The difference equation is
 
fiat — Sij 4 rj8s Fist jut — Fist 2592 Fist gat + fiat j—1 — 2 fiat;
 
 
1 1,2it 28S raed 58? =rhorFigg = Fist jn FOF hint +h fia at (18.32)whereI . 2.2a; = Tyra sett tor jr 80)b= lo fattd + rat! oy 5)1cf = ——_(Lrjét + 40° f* 61)brroefij+i \ J Fisv jufij Sissy fij FisnyFij-1 Fisij-lImplicit finite Explicit finitedifference method difference method
Figure 18.16 Difference between implicit and explicit finite difference methods
> A general rule in finite difference methods is that 6S should be kept proportional to 8 as they approach zero.Numerical Procedures
ARP O64 te vastus ontinn in Examote 126.2 OUfid to vatue Option i CxaMpice 16
sine th-t using th
a$E
423
 
Time to maturity (months)
 
(dollars) 5 45 4 35 3 28 2 bs 1100 0.00 0.00 0.00 0.00 0.00 0,00 0.00 0.00 0.0095 0.06 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.009 0.11 0.05 0,00 0.00 0.00 0.00 0.00 0.00 0.00&5 0.28 —0.05 0.05 0.00 0.00 0.00 0.00 0.00 0.0080 0.13 0.20 0.00 0.05 0.00 0.00 0.00 0.00 0.0075 0.46 0.06 0.20 0.04 0.06 0.00 0.00 0.00 0.0010 032 046 023 025 0.10 0.09 0.00 0.00 0.0065 0.91 068 0.63 044 037 021 014 0.00 0.0060 148 137 LIT 102 081 0.65 042 0.27 0.0055 259 239 221 199 177 150 124 090 0.5950 426 4.08 3.89 3.68 344 348 287 253 2.0745 6.76 661 647 631 615 596 5.75 5.50 5.2440 —«*10.28---10.20 10.13 10.06 10.01 10.00 10.00 10.00 10.0035 «15.00 15.00 15.00 15.00 15.00 15.00 15.00 15.00 15.0030.20.00 20.00 20.00 20.00 20.00 20.00 20.00 20.00 20.0025 25.00 25.00 25.00 25.00 25.00 25.00 25.00 25.00 25.0020 «30.00» 30.00 30.00 30.00 30.00 30.00 30.00 30.00 30.0015 35.00 35.00 35.00 35.00 35.00 35.00 35.00 35.00 35.001049.00 40.00 40.00 40.00 40.00 40.00 40.00 40.00 40.005 45.00 45.00 45.00 45.00 45.00 45.00 45.00 45.00 45.0050.00 50.00 50.00 $0.00 50.00 $0.00 50.00 50.00 50.00
0.000.000.000.000.000.000.000.000.000.001.565.0010.0015.0020.0025.0030.0035.0040.0045.0050.00
 
This creates what is known as the explicit finite difference method.”? Figure 18.16 shows the differencebetween the implicit and explicit methods. The implicit method leads to equation (18.25), whichgives a relationship between three different values of the option at time i 8¢ (ie., fi, j1. Si,j. fi,j41) andone value of the option al time (¢ + 1) 6t (ie., fi41,;)- The explicit method leads to equation (18.32),which gives a relationship between one value of the option at time i: (i.e., f; ;) and three different
values of the option at time ((+ 1)8t (Le., fiatj-n fiaty Aortjit)-
Example 18.8 Table 18.2 shows the result of using the explicit version of the finite differencemethod for pricing the American put option in Example 18.1. As in Example 18.7, values of 20,10, and 5 were chosen for M, N, and 8S, respectively. The option price given by the grid
is 4.26.24
18 4.26.
3 We also obtain the explicit finite difference method if we use the backward difference approximation instead of theforward difference approximation for af/dt.
* The negative numbers and other inconsistencies in the top left-hand part of the grid will be explained later in the
chapter.424 CHAPTER 18
Change of Variable
It is computationally more efficient to use finite difference methods with In S rather than § as theunderlying variable. Define Z = In $. Equation (18.19) becomes
af af, 28 f
yt er? w/oa tio azz =rf
The grid then evaluates the derivative for equally spaced values of Z rather than for equally spacedvalues of §. The difference equation for the implicit method becomes
 
Finti ~ fii Fiist — Fig. 4 oi tiiti t fin = inTO CD + 10 5Z2 =SijorOF ja t+ Bhi + Vidiint = fiat (18.33)whereoa= 5yg-2 o°/2)— nee
pala ers
 
__ _ _ one sz o/2) 52°
The difference equation for the explicit method becomes
2 fistjait fia — 2 fie
 
fiat, J -hij L(r o?/2) fist get — Sis Jol
 
 
 
+ loit 28Z 20 3Z2 ahior3 fist jt Bi fag + Vi fia = fii (18.34)where1 ot 2 ot 4*- (2/2 18.i rrra( zaz" 0/2) + sie") (18.35)1 at[| 8.36Bi rosn( zn) (18.36)1 it 3 sgx (279 8.374 rasu(sez¢ 7 2)+ 5553") (18.37)
The change of variable approach has the Property that a;, Bj, and Vj, as well as or’, B%, and yj, areindependent of j. It can be shown that it is numerically most efficient to set 6Z = oV/3 8t.Relation to Trinomial Tree Approaches
The explicit finite difference method is equivalent to the trinomial tree approach.”* In theexpressions for a}, b}, and cj in equation (18.32), we can interpret terms as follows:
—1,j6t + 4077? dt: Probability of stock price decreasing from jéS to (j — 1) 8S in time 8t2 2 J
°5 Tt can also be shown that the implicit finite difference method is equivalent to a multinomial tree approach wherethere are M+! branches emanating from each node.Numerical Procedures 425
Arjdt+ 4077? 51Fivage
fisay
~drjdt+ $0777 1
 
fisaj-i
Figure 18.17 Interpretation of explicit finite difference method as a trinomial tree
1-0? P 6t: Probability of stock price remaining unchanged at jdS in time éthe jot+ le? 7’ ét: Probability of stock price increasing from 8S to (j + 1)6S in time dt
This interpretation is illustrated in Figure 18.17. The three probabilities sum to unity. They give theexpected increase in the stock price in time ét as rj 65S dt = rSét. This is the expected increase in arisk-neutral world. For small values of dt, they also give the variance of the change in the stockprice in time St as a7 j? 8S? St = 0” S? St. This corresponds to the stochastic process followed by S.The value of f at time i 6t is calculated as the expected value of f at time (i + 1) 6t in a risk-neutral
world discounted at une risk-free rate.For the explicit version of the finite difference method to work well, the three “probabilities”
—4rjot+ 40°}? de, 1-0} 6t, tr jdt + 40° 7 bt
should all be positive. In Example 18.8, | — 07° é¢ is negative when j > 13 (i.c., when S > 65),This explains the negative option prices and other inconsistencies in the top left- hand part ofTable 18.2. This example illustrates the main problem associated with the explicit finite differencemethod. Because the probabilities in the associated tree may be negative, it does not necessarilyproduce results that converge to the solution of the differential equation.”
When the change-of-variable approach is used (see equations (18.34) to (18.37)), the probabilitiesthat Z = In S will decrease by 5Z, stay the same, and increase by 5Z are, respectively,
 
Hz" — 0/2) + 590"st1-9
2 o
aa #2) 555
% J, Hull and A. White, “Valuing Derivative Securities Using the Explicit Finite Difference Method” Journal ofFinancial and Quantitative Analysis, 25 (March 1990), 87-100, show how this problem can be overcome. In thesituation considered here, it is sufficient to construct the grid in In $ rather than $ to ensure convergence.426 CHAPTER 18
These movements in Z correspond to the stock price changing from S to Se~”, S, and Se’,respeclively. If we set 6Z = oV36t, the tree and the probabilities are identical to those for thetrinomial tree approach discussed in Section 18.5.
Other Finite Difference Methods
Many of the other finite difference methods that have been proposed have some of the features ofthe explicit finite difference method and some features of the implicit finite difference method.
In what is known as the hopscotch method, we alternate between the explicit and implicitcalculations as we move from node to node. This is illustrated in Figure 18.18. At each time, wefirst do all the calculations at the ‘‘explicit nodes” in the usual way. We can then deal with the“implicit nodes” without solving a set of simultaneous equations because the values at the adjacentnodes have already been calculated.
The Crank-—Nicolson scheme is an average of the explicit and implicit methods. For the implicitmethod equation (18.25) gives
Fig = Aj fir jai + Oya + cj fi-1j41For the explicit method, equation (18.32) givesfing = GH j- TOS A Fi iaThe Crank—Nicolson method averages these two equations to give
Sig t Finny = Sinn + fing + Sint + Sip + OFA G + fi jalPutting915 = Fig — Fiji ~ OF Sig — fii
 
 
 
& AssetpriceBoundary—o— o— e—__—_—_el @E er @E elo@E el eE el er ¥ael @:E or @E elLL. — o—_—_ -—_e— >Boundary Time
Figure 18.18 The hopscotch method: I indicates node at which implicit calculations are done;E indicates node at which explicit calculations are doneNumerical Procedures 427
 
we obtain
G19 = Fiji + Oy fing + Cif > fin;
This shows that implementing the Crank—Nicolson method is similar to implementing the implicitfinite difference method. The advantage of the Crank-Nicolson method is that it has fastercotivergence than eliher the explicit or implicit meihod.
Applications of Finite Difference Methods
Finite difference methods can be used for the same types of derivative pricing problems as treeapproaches. They can handle American-style as well as European-style derivatives, but they cannoteasily be used in situations where the payoff from a derivative depends on the past history of theunderlying variable. Finite difference methods can, at the expense of a considerable increase incomputer time, be used when there are several state variables. The grid in Figure 18.15 thenbecomes multidimensional.
The method for calculating Greek letters is similar to that used for trees. Delta, gamma, andtheta can be calculated directly from the /;,; values on the grid. For vega, it is necessary to make asmall change to volatility and recalculate the value of the derivative using the same grid.
18.9 ANALYTIC APPROXIMATION TO AMERICANOPTION PRICES
 
As an alternative to the numerical procedures described thus far, a number of analytic approxima-tions to the valuation of American options have been suggested. The best known of these is aquadratic approximation approach originally suggested by MacMillan and extended by Barone-Adesi and Whaley.”” It can be used to value American calls and puts on stocks, stock indices,currencies, and futures contracts. It involves estimating the difference, v, between the Europeanoption price and the American option price. Because both the European and American optionsatisfy the same differential equation, v must also satisfy the differential equation. When anapproximation is made, the differential equation can be solved using standard methods. Moredetails on the approach are presented in Appendix 18A.
SUMMARY
 
We have presented three different numerical procedures for valuing derivatives when no analyticsolution is available. These involve the use of trees, Monte Carlo simulation, and finite differencemethods.
Binomial! trees assume that in each short interval of time, dt, a stock price either moves up by apercentage amount « or moves down by a percentage amount d. The sizes of w and d and theirassociated probabilities are chosen so that the change in the stock price has the correct mean andstandard deviation in a risk-neutral world. Derivative prices are calculated by starting at the end of
27 See L. W. MacMillan, “Analytic Approximation for the American Put Option,” Advances in Futures and OptionsResearch, | (1986). 119-39; G. Barone-Adesi and R. E. Whaley, “Efficient Analytic Approximation of AmericanOption Values.” Journal of Finance, 42 (June 1987), 301-20.428 CHAPTER 18
the tree and working backwards. For an American option, the value at a node is the greater of thevalue if it is exercised immediately and the discounted expected value if it is held for a furtherperiod of time 6t.
Monte Carlo simulation involves using random numbers to sample many different paths that thevariables underlying the derivative could follow in a risk-neutral world. For each path, the payoff iscalculated and discounted at the risk-free interest rate. The arithmetic average of the discountedpayoffs is the estimated value of the derivative.
Finite difference methods solve the underlying differential equation by converting it to adifference equation. They are similar to tree approaches in that the computations work back fromthe end of the life of the derivative to the beginning. The explicit method is functionally the sameas using a trinomial tree. The implicit finite difference method is more complicated but has theadvantage that the user does not have to take any special precautions to ensure convergence.
In practice, the method that is chosen is likely to depend on the characteristics of the derivativebeing evaluated and the accuracy required. Monte Carlo simulation works forward from thebeginning to the end of the life of a derivative. It can be used for European-style derivatives andcan cope with a great deal of complexity as far as the payoffs are concerned. It becomes relativelymore efficient as the number of underlying variables increases. Tree approaches and finitedifference methods work from the end of the life of a security to the beginning and canaccommodate American-