# A Simple Numerical Method for Pricing an American Put Option

Authors: Beom Jin Kim; Yong-Ki Ma; Hi Jun Choe
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We present a simple numerical method to find the optimal exercise boundary in an American put option. We formulate an intermediate function with the fixed free boundary that has Lipschitz character near optimal exercise boundary. Employing it, we can easily determine the optimal exercise boundary by solving a quadratic equation in time-recursive way. We also present several numerical results which illustrate a comparison to other methods.


---

## Body

## 1. Introduction

The owner of a put (call) option has the right but no obligation to sell (buy) an underlying asset at the exercise price. European options can be exercised only on the expiry date, while American options can be exercised at any time until the expiry date. Closed-form solutions for the European options are derived in papers by Black and Scholes [1] and Merton [2]. In the case of American options, because of the early exercise possibility, the pricing problem leads to complications for analytic calculation. McKean [3] and van Moerbeke [4] show that the valuation of American options constitutes a free boundary problem looking for a boundary changing in time to maturity, mostly called an optimal exercise boundary. Hence, finance researchers have studied methods to quickly and accurately find the optimal exercise boundary. These methods are basically of two types, that is, analytical approximations such as those developed by Geske and Johnson [5], MacMillan [6], Barone-Adesi and Whaley [7], and Ju [8] and numerical methods such as those of Brennan and Schwartz [9], Hull and White [10], and Longstaff and Schwartz [11]. Zhu [12] finds an exact and explicit solution of the Black-Scholes equation for the valuation of American put options using Taylor series with infinitely many terms. His work is an excellent result for the valuation of American put options; however, it seems difficult to perform his solution numerically. The infinite sum is likely to yield many computation errors. Zhao and Wong [13] study an extension of Zhu’s work [12] to price American options under general diffusion processes.The majority of numerical methods for pricing American options, such as the finite difference method of Brennan and Schwartz [9], the binomial method of Cox et al. [14], the Monte Carlo simulation method of Grant et al. [15], the least squares method of Longstaff and Schwartz [11], the integral-equation method of Ševčovič [16], and the Laplace transform method of Zhu [17], are time-recursive ways. Their idea is to discretize  the lifetime of an option and find its optimal exercise boundary  backward in time. Since time-recursive ways yield repeated calculations for every time step, they require fast computation times and small pricing errors. Also, front-fixing methods developed by Wu and Kwok [18] and Nielsen et al. [19] apply a nonlinear transformation to fix the boundary and solve the resulting nonlinear problem. A secant method developed by Zhu et al. [20] needs to solve a nonlinear problem, and a moving boundary approach developed by Muthuraman [21] converts the arising linear free boundary partial differential equation (PDE) problem into a sequence of linear fixed-boundary PDE problems. More recently, Zhu and Zhang [22] introduced a new predictor-corrector scheme to price American put options under the Black-Scholes model, and then Zhu and Chen [23] proposed an extension of Zhu and Zhang’s work [22] to solve for the valuation of American put options with stochastic volatility model.The main contribution of this paper is the development of a simple numerical method to find optimal exercise boundary in a time-recursive way. Our result is motivated by the necessity for better understanding of the solution surface near optimal exercise boundary. We adopt the front-fixing transformation [18] to change the unknown free boundary to a known and fixed boundary. We exploit an intermediate function with the fixed free boundary that has Lipschitz character which avoids the degeneracy of the solution surface near optimal exercise boundary as in Kim et al. [24]. Indeed, our function from the Black-Scholes equation and the boundary conditions transforms the surface above the exercise region onto a new Lipschitz surface which forms a sufficiently large angle with the hyperplane corresponding to the exercise region, thereby making the borderline more easily distinguishable (see Figure 2). We use implicit scheme in the continuation region and apply extrapolation near optimal exercise boundary. Thus we can determine the optimal exercise boundary by solving a quadratic equation in a time-recursive way. Our method also provides fast and accurate results for calculating the optimal exercise boundary and pricing American put options.The structure of the paper is as follows. Section2 presents the model formulation. The intermediate function with the fixed free boundary to calculate the optimal exercise boundary is presented in Section 3. Numerical results and comparative studies are presented in Section 4. Section 5 summarizes the paper.


## 2. Problem Formulation

In this section, we present a mathematical formula for pricing an American put option.Consider an American put option on an underlying asset (stock) with exercise priceK and expiration T. In risk-neutral probability, an underlying asset price S(t) is governed by the following stochastic differentiable equation:
(1)dS(t)=(r-δ)S(t)dt+σS(t)dW(t),
where r>0 represents the risk-free interest rate, δ≥0 represents the continuous dividend yield, σ>0 represents the volatility of the underlying asset price, and W(t) is the standard Brownian motion. The payoff function of the put option at T is defined as
(2)(K-S(T))+=max{K-S(T),0}.
The valuation of an American put option is denoted by P(τ,S), where τ(∶=T-t) is the time to expiration for τ∈[0,T] and S is the underlying asset price for S∈[0,∞).As seen in the previous article by McKean [3], the valuation of an American put option is considered the solution to a free boundary problem with a parabolic PDE. We suppose that the optimal exercise boundary β(τ) is continuously nonincreasing with β(0)=min{K,Kr/δ}. The region where it is optimal to hold, generally called the continuation region, is defined as Ωc=[0,T]×(β(τ),∞), and the region where it is optimal to exercise, generally called the exercise region, is defined as Ωe=[0,T]×[0,β(τ)]. Then, P(·,·) and β(·) uniquely solve
(3)ℒP-rP-Pτ=0inΩc,P(0,S)=(K-S)+,P(τ,β(τ))=K-β(τ),limS↑∞max0≤τ≤T|P(τ,S)|=0,limS↓β(τ)Ps(τ,S)=-1,P(τ,S)=K-SinΩe,P(τ,S)≥(K-S)+,
where ℒP=(1/2)σ2S2Pss+(r-δ)SPs and Ps,Pss, and Pτ are defined by the infinitesimal generator and partial derivatives, respectively. Here, we assume r>δ for using the Black-Scholes equation at τ=0. See, for example, Karatzas and Shreve [25] for general reference.Figure1 shows an illustration of an optimal exercise boundary with P. The two regions are separated by the optimal exercise boundary. From Figure 1 it is necessary that P must satisfy maxτ,S{ℒP-rP-Pτ,(K-S)+-P}=0. This condition is known as the Hamilton-Jacobi Bellman (HJB) equation. As Chockalingam and Muthuraman [26] point out, the continuation and exercise regions are determined by which term in the HJB equation is tight. Their method requires iterations till convergence of the boundaries. However, we emphasize that there is no iteration in our method using a square root transformation. Refer to Chockalingam and Muthuraman [26],  and Pham [27].Figure 1
Boundary conditions.Transformation from𝒫(τ,u) to Q(τ,u).
(a)
(b)A front-fixing method, proposed in Wu and Kwok [18], uses a change in variables to transform the free boundary problem into a nonlinear problem on a fixed domain. The following transformation of state variable serves for such a purpose:
(4)u=lnS-lnβ(τ).
They derive the equation and the boundary conditions with respect to u as follows:
(5)ℒ~𝒫-r𝒫-𝒫τ=0,u∈(0,∞),𝒫(0,u)=0,u∈(0,∞),𝒫(τ,0)=K-β(τ),𝒫u(τ,0)=-β(τ),𝒫(τ,∞)=0,
where ℒ~𝒫=(1/2)σ2𝒫uu+(r-δ-(σ2/2)+(β′(τ)/β(τ)))𝒫u and 𝒫u and 𝒫uu are defined by infinitesimal generator and partial derivatives, respectively. Note that β(τ) is a monotonically decreasing function of τ with a nontrivial asymptotic limit as follows:
(6)β(∞)=θθ-1K,
where
(7)θ=-(r-δ-(1/2)σ2)-(r-δ-(1/2)σ2)2+2σ2rσ2.
Namely, the optimal exercise boundary does not change with time. Especially, plugging δ=0 into (6), we have the asymptotically optimal exercise boundary as follows:
(8)β(∞)=γγ+1K,
where γ=2r/σ2. Note that transformation (4) is valid because β(τ)>0 holds for all τ≥0. Refer to Kim [28].


## 3. Intermediate Function with the Fixed Free Boundary

In this section, we present an intermediate function with the fixed free boundary and can determine the optimal exercise boundary by solving a quadratic equation in a time-recursive way.Under the assumption of the Black-Scholes model, the time for optimal exercise can be shown to be the first hitting time of a boundary, the optimal exercise boundary, in the plane consisting of pairs of the underlying asset price and the time to expiration. Namely, the price curve of an American put option touches the line representing the intrinsic value tangentially. With a careful examination of the solution surface near optimal exercise boundary, we find a Lipschitz surface which avoids the degeneracy of the solution surface near optimal exercise boundary. To find the optimal exercise boundary, we present an intermediate function with the fixed free boundary that has Lipschitz character near optimal exercise boundary as follows:(9)Q(τ,u)∶=𝒫(τ,u)-K+euβ(τ).
The transformed function Q(τ,u) provides that the solution surface in Ωe is a horizontal plane, and it is an inclined plain in Ωc. Namely, this function forms a sufficiently large angle with the hyperplane corresponding to the exercise region, thereby making the borderline more easily distinguishable. Q(τ,u) also has a Lipschitz character with nonsingularity in (0,∞) and a nondegeneracy property near optimal exercise boundary. Hence, we have
(10){Q(τ,u)=0ifu∈[lnβ(∞)-lnβ(τ),0],Q(τ,u)>0ifu∈(0,∞).Figure 2(a) shows that 𝒫(τ,u) is transformed to Q(τ,u), and Figure 2(b) is a magnified view of the optimal exercise boundary.We find the intermediate function with the fixed free boundary to decide the optimal exercise boundary by the Taylor series. From𝒫(τ,u)=Q2(τ,u)+K-euβ(τ), we obtain the following relations near optimal exercise boundary (u=0):
(11)𝒫uu=2Qu2-β,𝒫u=-β,𝒫=K-β,𝒫τ=-β′.
Plugging (11) into (5), we obtain
(12)12σ2(2Qu2-β)+(r-δ-12σ2+β′β)(-β)-r(K-β)+β′=0,
and then we get Qu2=(rK-δβ)/σ2. More precisely, we have
(13)Qu(τ,0)=rKσ,rσK<Qu(τ,0)<rKσeu*
with δ=0, where u*=lnβ(∞)-lnβ(τ)<0. Then, we have |𝒫-K+euβ(τ)|≤c|u-0|2 for some constant c because Q(τ,u) is Lipschitz and a natural candidate for computation in (0,∞). We obtain an angle between exercise surface (Q=0) and Q surface (Q>0) such that 0<λ0<∂Q/∂u<λ1 for some constants λ0 and λ1. We also calculate the partial derivative with respect to u in (5) as follows:
(14)12σ2𝒫uuu+(r-δ-12σ2+β′β)𝒫uu-r𝒫u-𝒫τu=0.
From 𝒫(τ,u)=Q2(τ,u)+K-euβ(τ), we obtain the following relations near optimal exercise boundary (u=0):
(15)𝒫uuu=6QuQuu-β,𝒫τu=-β′.
Hence, plugging (15) into (14), we get
(16)Quu=-2ξη3σ3-δβ3ση,
where ξ=r-δ-σ2/2+β′/β and η=rK-δβ. From (6) we easily show that ξ and η are bounded parameters such that c1≤ξ≤c2 for some negative constants c1 and c2 and (r-δ)K≤η≤rK, respectively.Using the similar arguments, we can obtain the following equations near optimal exercise boundary(u=0) as follows:
(17)12σ2𝒫uuuu+(r-δ-12σ2+β′β)𝒫uuu-r𝒫uu-𝒫τuu=0,(18)𝒫uuuu=6Quu2+8QuQuuu-β,𝒫τuu=-(2δσ2+1)β′.
Hence, plugging (18) into (17), we get
(19)Quuu=2ξ2η3σ5+ξδβ6σ3η-δ2β212ση3-δβ4ση+rη2σ3-δβ′2σ3η.Furthermore, we recognize that𝒫 is analytic up to the optimal exercise boundary and u is locally analytic. Hence, the approximation for Q(τ,u) at β(τ) can be written as
(20)Q(τ,u)=Q(τ,0)+Qu(τ,0)u+12!Quu(τ,0)u2+13!Quuu(τ,0)u3+𝒪(u4).
We introduce the equilibrium parameter u~>0 which enables us to adjust the location of optimal exercise boundary in a mesh size. So, plugging Qu(τ,0), Quu(τ,0), and Quuu(τ,0) into (20), we obtain Q(τ,u~) as follows:
(21)Q(τ,u~)=ησu~-12(2ξη3σ3+δβ3ση)u~2+16(2ξ2η3σ5+ξδβ6σ3η-δ2β212ση3-δβ4ση+rη2σ3-δβ′2σ3η)u~3.
We rewrite (21) with respect to ξ as follows:
(22)a~(β′)2+b~(β′)+c~=0,
where
(23)a~=ηu~39σ5β2,b~=-ηu~23σ3β+2ηνu~39σ5β+δu~336σ3η-δu~312σ3η,c~=-Q(τ,u~)+ηu~σ-13(ηνσ3+δβ2ση)u~2+16(2ην23σ5+δνβ6σ3η-δ2β212ση3-δβ4ση+rη2σ3)u~3,ξ=ν+β′β,ν=r-δ-σ22.
Combining (22) with β′<0, we have
(24)β′=-b~-b~2-4a~c~2a~.
For discretization (Δτ,Δu), we introduce a two-dimensional mesh in the first quadrant of the τ-u plane. From (24) we have
(25)βn+1-βnΔτ=-b^-b^2-4a^c^2a^,
where
(26)n=0,1,2,…,N,m=0,1,2,…,M,u^=ρΔu(ρ>0),QznisthenumericalapproximationtoQ(nΔτ,zΔu)(z=ρ,m),βnisthenumericalapproximationtoβ(nΔτ),a^=ηu^39σ5β2,b^=-ηu^23σ3β+2ηνu^39σ5β+δu^336σ3η-δu^312σ3η,c^=-Q(τ,u^)+ηu^σ-13(ηνσ3+δβ2ση)u^2+16(2ην23σ5+δνβ6σ3η-δ2β212ση3-δβ4ση+rη2σ3)u^3,
respectively. Hence, we rewrite (25) with respect to βn as follows:
(27)βn+1=βn+(-b^-b^2-4a^c^2a^)Δτ.
When the initial values are given by Qρ0 (transformed price of the American put option) and β0 (optimal exercise boundary) at τ=0, we can determine β1 (optimal exercise boundary) at Δτ using (27). More importantly, for updating the optimal exercise boundary our method dose not include iteration until sufficient accuracy is obtained. So, we repeat the previously mentioned process until NΔτ and obtain the optimal exercise boundary in a time-recursive way.


## 4. Numerical Examples

In this section, we provide numerical examples to illustrate our method. We also make runtimes and computation errors compared with the results obtained by other numerical methods such as the binomial method (Binomial) developed by Cox et al. [14], the front-fixing method (Front-fixing) developed by Wu and Kwok [18], and the finite difference implementation of the moving boundary method (MBM-FDM) developed by Muthuraman [21].All implementations are carried out using a C++ implementation with the a 2.66 Ghz Intel 4 Core CPU with 3 GB RAM. A finite difference method with Crank-Nicolson scheme is proposed for our method. The benchmark results are obtained using the Binomial with10,000 time steps, and we consider these results to be the exact values of the American put options. Here, root mean squared error (RMSE) is calculated by the values of the Binomial.The parameter values used to calculate the optimal exercise boundary and values of the American put options arer=0.05,  σ=0.20,  δ=0,  K=100,  T=1,  u∈[0,2], and a discrete mesh of 2000×300 nodes.In Figure3, we find a numerical optimization ρ=5.5702. Table 1 also shows the results of the optimal exercise boundary and the values of American put options with safety parameters. One can see from Table 1 that the optimal exercise boundary monotonically increases as the value of ρ increases, but the value of American put options monotonically decreases when ρ increases. They are so gradual that they are not very susceptible to change in the value of ρ.Table 1
Valuation of the American put options.
Safty parameterρ
RMSE
β
(
T
)
P
(
T
,
90
)
P
(
T
,
100
)
P
(
T
,
110
)
5.00
0.0005816
80.8760
11.4926
6.0911
2.9869
5.10
0.0005443
80.8761
11.4925
6.0911
2.9868
5.20
0.0005110
80.8762
11.4925
6.0910
2.9868
5.30
0.0004831
80.8764
11.4924
6.0909
2.9867
5.40
0.0004623
80.8765
11.4924
6.0908
2.9866
5.50
0.0004503
80.8767
11.4923
6.0907
2.9865
5.60
0.0004484
80.8769
11.8760
6.0906
2.9864
5.70
0.0004576
80.8771
11.8771
6.0906
2.9863
5.80
0.0004780
80.8773
11.4922
6.0905
2.9863
5.90
0.0005088
80.8776
11.4921
6.0904
2.9862
6.00
0.0005491
80.8779
11.4920
6.0903
2.9861
Maximum difference
0.0001336
0.0019
0.0006
0.0008
0.0008Figure 3
RMSE of the safety parameterρ.Table2 reports the values of the American put options for the specific parameter set associated with the table. In Figure 4 and Table 3, we take the parameter values used in Figure 3 except for the discrete mesh and plot runtimes and computational errors compared with various methods. Note that the discrete meshes of 125×25,  250×50,  500×100,  1000×200, and 2000×400 nodes are plotted in Figure 4 and Table 3.Table 2
Comparison of the values of the American put options.
(
S
,
T
,
r
,
σ
,
δ
)
Binomial
Front fixing
MBM-FDM
Our method
( 80, 0.5, 0.05, 0.20, 0.00)
20.0000
20.0000
20.0000
20.0000
( 90, 0.5, 0.05, 0.20, 0.00)
10.6661
10.6643
10.6680
10.6661
(100, 0.5, 0.05, 0.20, 0.00)
4.6556
4.6501
4.6504
4.6549
(110, 0.5, 0.05, 0.20, 0.00)
1.6681
1.6629
1.6631
1.6686
(120, 0.5, 0.05, 0.20, 0.00)
0.4976
0.4961
0.4993
0.4985
( 80, 0.5, 0.05, 0.20, 0.03)
20.0000
20.0000
20.0000
20.0000
( 90, 0.5, 0.05, 0.20, 0.03)
11.1551
11.1513
11.1526
11.1544
(100, 0.5, 0.05, 0.20, 0.03)
5.1496
5.1435
5.1444
5.1496
(110, 0.5, 0.05, 0.20, 0.03)
1.9491
1.9461
1.9455
1.9509
(120, 0.5, 0.05, 0.20, 0.03)
0.6132
0.6113
0.6155
0.6153
( 80, 1.0, 0.05, 0.20, 0.00)
20.0000
20.0000
20.0000
20.0000
( 90, 1.0, 0.05, 0.20, 0.00)
11.4928
11.4924
11.4857
11.4929
(100, 1.0, 0.05, 0.20, 0.00)
6.0903
6.0893
6.0829
6.0905
(110, 1.0, 0.05, 0.20, 0.00)
2.9866
2.9856
2.9854
2.9868
(120, 1.0, 0.05, 0.20, 0.00)
1.3672
1.3654
1.3643
1.3674
( 80, 1.0, 0.07, 0.40, 0.03)
24.0068
24.0054
23.9987
24.0057
( 90, 1.0, 0.07, 0.40, 0.03)
18.2760
18.2741
18.2697
18.2746
(100, 1.0, 0.07, 0.40, 0.03)
13.7886
13.7879
13.7852
13.7873
(110, 1.0, 0.07, 0.40, 0.03)
10.3317
10.3312
10.3235
10.3307
(120, 1.0, 0.07, 0.40, 0.03)
7.7027
7.7014
7.7016
7.7018
( 80, 3.0, 0.08, 0.20, 0.00)
20.0000
20.0000
20.0000
20.0000
( 90, 3.0, 0.08, 0.20, 0.00)
11.6974
11.9029
11.6892
11.6977
(100, 3.0, 0.08, 0.20, 0.00)
6.9320
7.2527
6.9221
6.9321
(110, 3.0, 0.08, 0.20, 0.00)
4.1550
4.4841
4.1443
4.1548
(120, 3.0, 0.08, 0.20, 0.00)
2.5102
2.7760
2.4997
2.5102
( 80, 3.0, 0.08, 0.20, 0.03)
20.1345
20.2396
20.1282
20.1349
( 90, 3.0, 0.08, 0.20, 0.03)
12.9694
13.1798
12.9611
12.9697
(100, 3.0, 0.08, 0.20, 0.03)
8.3791
8.5901
8.3690
8.3792
(110, 3.0, 0.08, 0.20, 0.03)
5.4152
5.5223
5.4041
5.4151
(120, 3.0, 0.08, 0.20, 0.03)
3.4981
3.5983
3.4879
3.4979Table 3
Comparison of RMSE and runtime.
Mesh size (N×M)
Front fixing (runtime, RMSE)
MBM-FDM (runtime, RMSE)
Our Method (runtime, RMSE)
125 × 25
(6.690, 3.10070)
(0.415, 0.04640)
(0.023, 0.10901)
250 × 50
(26.767, 2.76880)
(1.922, 0.02510)
(0.109, 0.01395)
500 × 100
(175.508, 3.61630)
(9.953, 0.01210)
(0.741, 0.00392)
1000 × 200
(1223.615, 2.49460)
(57.531, 0.00620)
(5.997, 0.00089)
2000 × 400
(7998.379, 2.41980)
(345.759, 0.00290)
(56.444, 0.00021)Figure 4
Comparison of RMSE and runtime.As is shown in Table2, Figure 4, and Table 3, although four different methods have similar values of the American put option, our method is computationally faster and more accurate than other methods. Especially, Figure 4 and Table 3 show the numerical convergence of our method. So our method is superior to the others in accuracy and computational efficiency.


## 5. Final Remarks

The front-fixing method suggested by Wu and Kwok [18] shows a degeneracy near optimal exercise boundary, while our method adopts a square root function to avoid the quadratic behavior of solution surface that causes degeneracy. Our method employing an intermediate function with the fixed free boundary solves a nonlinear problem on a fixed domain derived from a free boundary problem. Since the computation process depends on Lipschitz surface, we need to focus on the motion of the solution surface which would be simple to see the minute behavior of solution surface. The moving boundary approach developed by Mutheraman [21] requires iterations till the convergence of the boundaries. However, we emphasize that there is no iteration in our method. In such a rapidly changing environment, our straightforward method is a very powerful tool to understand financial market. Numerical study also shows that overall speed and accuracy comparisons have demonstrated the superiority of our method over other methods. Our method can be easily extended to other models under stochastic volatility and jump diffusion processes. These remain as topics for future research.



---

*Source: 128025-2013-02-28.xml*