Numerical methods

6 lessons · 6 equations. Each lesson below gives its formulas and key rules; open the lesson for the full explanation.

Root finding, with implied volatility as the worked case

Newton–Raphson

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

Step to where the tangent line crosses zero. Near a simple root the error squares each iteration, which is why the digit count roughly doubles per step.

Orders of convergence

∣ek+1∣≈C ∣ek∣p,pbisection=1,psecant=1+52≈1.618,pNewton=2|e_{k+1}| \approx C\,|e_k|^{p}, \qquad p_{\text{bisection}} = 1,\quad p_{\text{secant}} = \tfrac{1 + \sqrt5}{2} \approx 1.618,\quad p_{\text{Newton}} = 2

The order pp says how the number of correct digits grows: bisection adds a fixed amount per step, Newton doubles it, the secant method multiplies it by the golden ratio — without needing a derivative.

Remember

  • Bisection is linear and safe; Newton is quadratic and unsafe; the production answer combines them.

Interpolation: splines, Runge and building a curve

Interpolate total implied variance

w(T)=σ(T)2T,w(T)=w1+T−T1T2−T1(w2−w1)w(T)=\sigma(T)^2T,\qquad w(T)=w_1+\frac{T-T_1}{T_2-T_1}(w_2-w_1)

Interpolate total variance across expiries, then recover volatility from σ(T)=w(T)/T\sigma(T)=\sqrt{w(T)/T}.

Remember

  • High-degree polynomials oscillate; many low-degree pieces do not.

Numerical integration: trapezoid, Simpson and Gauss

Why grids lose to Monte Carlo in high dimension

grid rule of order p in d dimensions: error∼N−p/d,Monte Carlo: N−1/2\text{grid rule of order } p \text{ in } d \text{ dimensions: error} \sim N^{-p/d}, \qquad \text{Monte Carlo: } N^{-1/2}

A tensor-product grid with NN points has only N1/dN^{1/d} per dimension. Monte Carlo’s rate does not depend on dd, so it wins once d>2pd > 2p — beyond eight dimensions for Simpson, four for the trapezoid rule.

Remember

  • Trapezoid is O(h2)O(h^2); Simpson is O(h4)O(h^4) and exact for cubics.

Linear algebra in practice: factorisations and conditioning

The condition number

κ(A)=∥A∥ ∥A−1∥=σmax⁡σmin⁡\kappa(A) = \|A\|\,\|A^{-1}\| = \frac{\sigma_{\max}}{\sigma_{\min}}

How much a relative error in the input can be amplified in the output. A condition number of 10k10^k means losing about kk digits of precision.

Remember

  • Cholesky for positive definite, QR for least squares, SVD when conditioning is bad.

ODE and PDE solvers: finite differences and stability

The explicit stability condition

Δt≤(Δx)2σ2\Delta t \le \frac{(\Delta x)^2}{\sigma^2}

Halving the space step requires quartering the time step. Refining the grid therefore costs eight times the work, not twice.

Remember

  • Work in ln⁡S\ln S and put a node on the strike.

Detailed formula cards