American Option Pricing - Mathematical Finance Flowcharts

1. Mathematical Finance Problem Formulation

The Black-Scholes PDE

For an option with value \(V(S, \tau)\) where \(\tau = T - t\) is time to maturity:

\[\frac{\partial V}{\partial \tau} = \frac{1}{2}\sigma^2 S^2 \frac{\partial^2 V}{\partial S^2} + (r-q)S\frac{\partial V}{\partial S} - rV\]

Parameters:

\(S\) - Current stock price
\(\sigma\) - Volatility
\(r\) - Risk-free interest rate
\(q\) - Continuous dividend yield
\(\tau\) - Time to maturity

European vs American Options

European Option

Can only be exercised at maturity \(T\).

Constraint: \(V \geq 0\)

American Option

Can be exercised at any time \(t \in [0, T]\).

Constraint: \(V(S, \tau) \geq h(S)\)

Payoff Function \(h(S)\):

Call: \(h(S) = \max(S - K, 0)\)

Put: \(h(S) = \max(K - S, 0)\)

Linear Complementarity Problem (LCP)

The American option pricing problem can be formulated as finding \(V(S, \tau)\) such that:

\[LV - \frac{\partial V}{\partial \tau} \geq 0\] \[V - h(S) \geq 0\] \[\left(LV - \frac{\partial V}{\partial \tau}\right) \cdot \left(V - h(S)\right) = 0\]

Where \(L\) is the spatial differential operator: \[LV = \frac{1}{2}\sigma^2 S^2 \frac{\partial^2 V}{\partial S^2} + (r-q)S\frac{\partial V}{\partial S} - rV\]

Interpretation: At each point in space-time, either:

The PDE is satisfied (continuation region), OR
The option is at its intrinsic value (exercise region)

2. Finite Difference Discretization

Spatial-Temporal Grid Setup

\[S \in [0, S_{max}], \quad \tau \in [0, T]\] \[\Delta S = \frac{S_{max}}{M}, \quad \Delta\tau = \frac{T}{N}\] \[S_i = i \cdot \Delta S, \quad \tau_n = n \cdot \Delta\tau\]

Grid points: \(i = 0, 1, 2, \ldots, M\) and \(n = 0, 1, 2, \ldots, N\)

Note: \(S_{max}\) should be chosen sufficiently large (e.g., 2-4×K) to capture the option's behavior near the upper boundary.

Central Difference Approximations

First derivative (gradient):

\[\frac{\partial V}{\partial S} \approx \frac{V_{i+1} - V_{i-1}}{2\Delta S}\]

Second derivative (curvature):

\[\frac{\partial^2 V}{\partial S^2} \approx \frac{V_{i+1} - 2V_i + V_{i-1}}{\Delta S^2}\]

Time derivative:

\[\frac{\partial V}{\partial \tau} \approx \frac{V^{n+1} - V^n}{\Delta\tau}\]

Crank-Nicolson Scheme

The Crank-Nicolson scheme averages the explicit and implicit steps for second-order accuracy:

\[\frac{V^{n+1} - V^n}{\Delta\tau} = \frac{1}{2}\left[LV^{n+1} + LV^n\right]\]

This yields a tridiagonal linear system at each time step:

\[\alpha_i V_{i-1}^{n+1} + \beta_i V_i^{n+1} + \gamma_i V_{i+1}^{n+1} = rhs_i^n\]

                    Key Properties:
                    Unconditionally stable - no time step restriction
Second-order accurate in both space and time
Requires solving a tridiagonal system at each time step

                

3. Discretized Coefficient Derivation

Sub-diagonal Coefficient \(\alpha_i\)

Coefficient for \(V_{i-1}\) (left neighbor):

\[\alpha_i = \frac{\Delta\tau}{2}\left[\frac{\sigma^2 i^2}{\Delta S^2} - \frac{(r-q)i}{2\Delta S}\right]\]

Main Diagonal Coefficient \(\beta_i\)

Coefficient for \(V_i\) (center):

\[\beta_i = -\frac{\Delta\tau}{2}\left[\frac{\sigma^2 i^2}{\Delta S^2} + r\right] - 1\]

Note: The "-1" term comes from the time derivative discretization: \[-\frac{\Delta\tau}{2} \cdot (-r) - 1 = \frac{r\Delta\tau}{2} - 1\]

Super-diagonal Coefficient \(\gamma_i\)

Coefficient for \(V_{i+1}\) (right neighbor):

\[\gamma_i = \frac{\Delta\tau}{2}\left[\frac{\sigma^2 i^2}{\Delta S^2} + \frac{(r-q)i}{2\Delta S}\right]\]

Boundary Conditions

Lower Boundary (\(S \to 0\))

Call: \(V(0, \tau) = 0\)

(Stock worthless, call expires worthless)

Put: \(V(0, \tau) = Ke^{-r\tau}\)

(Should receive K if exercised immediately)

Upper Boundary (\(S \to S_{max}\))

Call:

\(V(S_{max}, \tau) = S_{max}e^{-q\tau} - Ke^{-r\tau}\)

Put: \(V(S_{max}, \tau) = 0\)

(Far out-of-the-money, no early exercise value)

Important: With dividend yield \(q > 0\), the call upper boundary becomes time-dependent, which affects the accuracy of the numerical scheme.

Terminal Condition (Payoff)

At maturity (\(\tau = 0\) or \(t = T\)):

Call: \(V(S, 0) = \max(S - K, 0)\)

Put: \(V(S, 0) = \max(K - S, 0)\)

This serves as the initial condition for backward induction from \(\tau = 0\) to \(\tau = T\).

4. SOR (Successive Over-Relaxation) Algorithm

Why SOR?

The Crank-Nicolson scheme requires solving a tridiagonal linear system at each time step:

\[\alpha_i V_{i-1} + \beta_i V_i + \gamma_i V_{i+1} = rhs_i\]

While the system is tridiagonal (which would allow direct Thomas algorithm), the American option's early exercise constraint makes it a nonlinear complementarity problem. SOR provides an iterative approach that naturally incorporates the constraint.

Standard Gauss-Seidel Iteration

For a tridiagonal system, Gauss-Seidel updates each variable sequentially:

\[x_i^{(k+1)} = \frac{b_i - \alpha_i x_{i-1}^{(k+1)} - \gamma_i x_{i+1}^{(k)}}{-\beta_i}\]

Key observation: When updating \(x_i\), the left neighbor \(x_{i-1}\) already has the updated value \((k+1)\), while the right neighbor \(x_{i+1}\) still has the old value \((k)\).

SOR with Acceleration Factor

SOR adds an acceleration parameter \(\omega\) to speed up convergence:

\[x_i^{(k+1)} = x_i^{(k)} + \omega\left(x_i^{GS} - x_i^{(k)}\right)\]

Which expands to:

\[V_i^{new} = (1-\omega)V_i^{old} + \frac{\omega}{-\beta_i}\left[rhs_i - \alpha_i V_{i-1}^{new} - \gamma_i V_{i+1}^{old}\right]\]

Relaxation Parameter \(\omega\)

\(\omega < 1\): Under-relaxation (slower convergence)
\(\omega = 1\): Standard Gauss-Seidel
\(1 < \omega < 2\): Over-relaxation (accelerated convergence)
\(\omega \geq 2\): Diverges!

Empirical range: \(\omega \in [1.1, 1.3]\) works well for option pricing problems.

Theoretical Optimal \(\omega\)

The optimal relaxation parameter depends on the spectral properties of the system:

\[\omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho(J)^2}}\]

Where \(\rho(J)\) is the spectral radius of the Jacobi iteration matrix. In practice, this is difficult to compute exactly, hence the empirical approach.

SOR Algorithm for American Options

For each time step \(n = N-1, N-2, \ldots, 0\):

1

Initialize: \(V^0 = V^{n+1}\) (values from next time step)

2

Compute RHS: \(rhs = M \times V^{n+1} + boundary\_correction\)

3

Iterate until convergence:
For \(i = 1\) to \(M-1\):

# Gauss-Seidel estimate
gs = (rhs[i] - α[i] × V_new[i-1] - γ[i] × V_old[i+1]) / (-β[i])

# SOR update
V_temp = V_old[i] + ω × (gs - V_old[i])

# Early exercise constraint
V_new[i] = max(V_temp, payoff[i])
                            

4

Check convergence: \(\|V^{new} - V^{old}\|_2 < tol\)

5

Update: \(V^{n} = V^{converged}\) and proceed to next time step

5. Early Exercise Constraint

The Critical Constraint

After computing \(V_i^{new}\) from the SOR update, we enforce the American option constraint:

\[V_i^{new} = \max\left(V_i^{new}, h(S_i)\right)\]

where \(h(S_i)\) is the intrinsic value at grid point \(S_i\).

Economic Interpretation

Continue Holding

If \(V_i^{new} > h(S_i)\):

Time value exceeds intrinsic value
PDE is satisfied in this region
Optimal to wait

Exercise Immediately

If \(V_i^{new} < h(S_i)\):

Intrinsic value exceeds continuation value
Early exercise boundary reached
Set \(V =\) intrinsic value

\[V(S, \tau) = \begin{cases} h(S) & \text{in exercise region} \\ \text{solution of PDE} & \text{in continuation region} \end{cases}\]

Free Boundary Problem

The early exercise constraint creates a free boundary \(S^*(\tau)\) that must be determined as part of the solution:

\[V(S^*(\tau), \tau) = h(S^*(\tau)) \quad \text{(value matching)}\]

Smooth pasting condition (for optimal stopping):

\[\frac{\partial V}{\partial S}\bigg|_{S = S^*(\tau)} = \frac{\partial h}{\partial S}\bigg|_{S = S^*(\tau)}\]

American Put

\(S^*(\tau) < K\) for all \(\tau > 0\)

Early exercise more likely when deep in-the-money

American Call (with dividends)

\(S^*(\tau) > K\) when \(q > 0\)

Early exercise possible when dividend yield is high

Effect of Dividend Yield \(q\)

For American Call Options:

Drift term changes from \(r\) to \((r-q)\)
Upper boundary becomes time-dependent: \(S_{max}e^{-q\tau} - Ke^{-r\tau}\)
Early exercise becomes optimal when holding the stock yields dividends

\[\text{Exercise if: } q \cdot S > r \cdot K \cdot e^{-r\tau}\]

For American Put Options:

Dividend yield has minimal effect on optimal exercise
Early exercise always possible when deep in-the-money
Main driver is interest earned by receiving strike price early

Key insight: The max constraint automatically captures the optimal early exercise decision. No explicit boundary tracking is needed - it emerges naturally from the numerical scheme.

Convergence Near the Exercise Boundary

The early exercise constraint can slow SOR convergence, especially near the exercise boundary where:

The solution transitions from PDE-satisfying to constraint-active
Gradients can be steep
Small changes in parameters can shift the boundary

Practical Tips
Use tighter tolerance \(tol\) near maturity
Consider adaptive \(\omega\) that increases when error reduction slows
Adaptive grid refinement near the expected exercise boundary

6. Complete Pricing Algorithm

Computational Complexity

Metric	Formula	Description
Time Complexity	\(O(M^2 \times N \times k)\)	M = stock price grid points N = time grid points k = SOR iterations per time step (typically 5-50)
Space Complexity	\(O(M)\)	Coefficient arrays (α, β, γ) RHS vector Solution vector V

Summary: Key Steps

1

Discretize the Black-Scholes PDE using Crank-Nicolson scheme

2

Apply boundary conditions and terminal payoff

3

March backward in time from maturity to present

4

Solve the system at each time step using SOR with early exercise constraint

5

Interpolate to obtain the option price at the spot price S₀