M.8 Numerical Methods

Basic Prerequisites: Linear Algebra & Matrices, Multivariable Calculus & Optimization, and Probability & Measure Theory. (these are the folder-level prerequisites for pages 02–06; page 01 states its own, smaller, entry requirements)

1. Intuition & Practical Objective

Almost nothing closed-form survives contact with a real problem. The moment a model has a free boundary, a jump, a stochastic volatility, a non-linear constraint, or more than two state variables, the analytic solution disappears and the answer must be computed. Numerical methods are the discipline of computing those answers with a known, quantifiable error.

This folder is the general numerical-methods toolbox - the core techniques that any quantitative field needs, independent of the specific model. It is deliberately model-agnostic: the same finite-difference machinery solves the heat equation and the Black–Scholes PDE; the same Monte Carlo estimator prices an option and evaluates a risk integral; the same Newton iteration finds a root and minimises a loss.

Everything reduces to five primitive operations:

Approximate a derivative → divided differences → grid marching. → Finite-Difference Methods.
Approximate an integral / expectation → sampling → Monte Carlo. → Monte Carlo.
Find a root or a minimum → iteration → Newton/quasi-Newton. → Numerical Optimization.
Solve a linear system / eigenproblem → factorisation or iteration. → Numerical Linear Algebra.
Interpolate / approximate a function → basis expansion.

This page is the hub: it gives the fast error-order and cost lookup below and routes you to six sub-pages that build each primitive from first principles, quantify its error, and show the failure modes it violates.

The one-sentence essence. “Every numerical method trades work against error, and its quality is decided by two numbers - the order $p$ with which the error vanishes as the mesh/further refinement shrinks, and the conditioning $κ$ that amplifies the input noise - so know both before trusting a digit.”

2. Mathematical Ground Truth & Derivations

Lookup 1 - the three ways to approximate, and their error laws. Each family has exactly one error knob; knowing the order of the error is the whole discipline.

Family	Discretises	Error knob	Asymptotic error	Cost per unit accuracy
Divided difference / FDM	a derivative / a PDE on a mesh	mesh $h$ (space), $k$ (time)	$O (h^{p}) + O (k^{q})$ ; centred $p = 2$ , one-sided $p = 1$	cheap per point, but scales badly with dimension $d$ ( $O (N^{d})$ )
Monte Carlo	an integral / expectation	samples $n$	$O (n^{- 1/2})$ , independent of $d$	$4 \times$ work per halving of error
Deterministic quadrature	an integral	nodes $n$	trapezoid $O (n^{- 2})$ in 1-D, $O (n^{- 2/ d})$ in $d$	exact but cursed by dimension
Root / optimisation iteration	a zero / an extremum	iterations	bisection linear; Newton quadratic; GD linear rate $(κ - 1) / (κ + 1)$	one linear solve per Newton step

The single most important comparison in all of computational finance: Monte Carlo is $O (n^{- 1/2})$ in every dimension, whereas deterministic quadrature is $O (n^{- 2/ d})$ . For $d > 4$ the sampling route wins outright (Glasserman §1.1).

Lookup 2 - the finite-difference schemes. Writing the one-factor parabolic operator as $L u$ and the $θ$ -method weight on the new time level (Duffy eqs. 6.17–6.19, 7.4):

\frac{U ^{n + 1} - U ^{n}}{k} = θ L U^{n + 1} + (1 - θ) L U^{n}, θ \in [0, 1] .

Scheme	$θ$	Time order	Stability (heat / BS)	Solve per step
Explicit Euler	$0$	$O (k)$	conditional: $λ = ak / h^{2} \leq \frac{1}{2}$	none (matrix-free)
Implicit Euler	$1$	$O (k)$	unconditional	tridiagonal LU
Crank–Nicolson	$\frac{1}{2}$	$O (k^{2})$	unconditional, but $ρ < 0$ ⇒ ringing	tridiagonal LU
Extrapolated implicit Euler	-	$O (k^{2})$	unconditional, no ringing ( $2 U_{k /2} - U_{k}$ )	2 LU solves
Rannacher (2 implicit steps then CN)	mixed	$O (k^{2})$	unconditional, ringing suppressed	tridiagonal LU

Von Neumann amplification factor (Duffy eqs. 8.35, 8.38, 8.39), with $λ = ak / h^{2}$ and frequency $ξ$ :

ρ_{expl} (ξ) = 1 - 4 λ sin^{2} \frac{ξ}{2}, ρ_{impl} (ξ) = \frac{1}{1 + 4 λ sin ^{2} \frac{ξ}{2}}, ρ_{CN} (ξ) = \frac{1 - 2 λ sin ^{2} \frac{ξ}{2}}{1 + 2 λ sin ^{2} \frac{ξ}{2}} .

The triangle that governs everything (Duffy Defs. 8.1–8.4 + Thm 8.1): consistency (truncation error $\to 0$ ) $+$ stability ( $∥ Q^{n} ∥ \leq K$ ) $⟺$ convergence - the Lax equivalence theorem.

Lookup 3 - the Monte Carlo estimator and its error (Glasserman eqs. 1.1–1.8):

\overset{α}{^}_{n} = \frac{1}{n} i = 1 \sum n f (U_{i}), \overset{α}{^}_{n} - α \approx N (0, \frac{σ _{f}}{n}), s_{f} = \frac{1}{n - 1} i \sum (f (U_{i}) - \overset{α}{^}_{n})^{2} .

Variance-reduction method	Estimator / parameter	Variance factor
Control variate	$\overset{ˉ}{Y} - b (\overset{ˉ}{X} - E X)$ , $b^{*} = ρ_{X Y} σ_{Y} / σ_{X}$	$(1 - ρ_{X Y}^{2})$
Antithetic	$\frac{1}{2} (Y + \tilde{Y})$ ; works iff $Cov (Y, \tilde{Y}) < 0$	$(1 + ρ_{Y \tilde{Y}}) /2$
Stratified (proportional)	$n_{i} = n p_{i}$ ; Neyman $q_{i}^{*} \propto p_{i} σ_{i}$	never worse than plain MC
Latin hypercube	stratify each marginal into $K$ bins	$\leq σ^{2} / (K - 1)$ (Owen)
Importance sampling	$\overset{α}{^}_{g} = \frac{1}{n} \sum h (X_{i}) f (X_{i}) / g (X_{i})$	can be $0$ if $g\propto

Lookup 4 - the numerical linear-algebra and optimisation kernels.

Task	Method	Cost	Guarantee
Solve tridiagonal $A x = b$	Thomas (LU)	$O (n)$	exact in exact arithmetic
Solve dense $A x = b$	LU / Cholesky (SPD)	$O (n^{3})$	$∥ δ x ∥/∥ x ∥ \leq κ (A) ∥ δ b ∥/∥ b ∥$
Large sparse SPD $A x = b$	conjugate gradient	$O (n_{iter} \cdot cost (A))$	$\leq n$ steps exact; fast if $κ$ small
Dominant eigenvalue	power iteration	$O (n_{iter} \cdot n^{2})$	rate $
Root of $f (x) = 0$	Newton $x_{n + 1} = x_{n} - f / f^{'}$	quadratic, ~1 solve/step	quadratic convergence near a simple root
Minimise $f (x)$	gradient descent / Newton	GD linear rate $\frac{κ - 1}{κ + 1}$ ; Newton quadratic	GD needs $η < 2/ L$ ; Newton needs $\nabla^{2} f ≻ 0$

Lookup 5 - the discrete condition of a root/root-finding and the round-off floor. For any difference formula the total error is truncation $\sim h^{p}$ plus round-off $\sim ϵ / h^{m}$ ; the sum is minimised at $h^{*} \sim ϵ^{1/ (p + m)}$ (Conte & de Boor give $h \approx 0.0033$ for the second difference). Below that, shrinking the step makes the answer worse.

3. Computational Implementation - the three primitives on one screen

One script, stdlib only, showing the three things numerical methods actually do: solve a PDE, estimate an expectation, invert a non-linear function.

4. Failure Modes & First-Principles Breakdowns

Hub signposts - the full first-principles analysis lives on the sub-pages. In one line each:

Stability is a property of the discretisation, not the formula. The explicit heat scheme is correct and useless outside $λ \leq \frac{1}{2}$ : the same code that returns $0.371$ at $λ = 0.5$ returns $\approx - 2.7 \times 1 0^{2}$ at $λ = 0.597$ (page 02; sign is chaotic near blow-up).
Second-order accuracy is not the same as “well-behaved”. Crank–Nicolson is unconditionally stable, yet $ρ (ξ)$ goes negative at high frequencies, producing spurious oscillations near kinks/strikes (Duffy Ch 33).
Monte Carlo’s $n^{- 1/2}$ does not distinguish bias from variance. Discretising an SDE adds an $O (h^{β})$ bias on top of the sampling error; the fix is a better scheme or MSE balancing, not more paths (Glasserman §1.1.3, 6.3.3).
Conditioning, not the algorithm, sets the achievable digits. At $κ (A) = 4 \times 1 0^{6}$ , a $1 0^{- 6}$ perturbation to the right-hand side moves the solution by $71%$ - no factorisation can recover what the conditioning destroyed (page 05).
Round-off imposes a floor. The centred difference of $e^{x}$ at $0$ degrades from $1.2 \times 1 0^{- 11}$ at $h = 1 0^{- 5}$ back to $4.4 \times 1 0^{- 1}$ at $h = 1 0^{- 16}$ (page 01).

5. References

Duffy, Daniel J.: Finite Difference Methods in Financial Engineering (Wiley, 2006)
Glasserman, Paul: Monte Carlo Methods in Financial Engineering (Springer, 2004)
Tsay, Ruey S.: Analysis of Financial Time Series (3rd ed., 2010)
Golub, G. H. & Van Loan, C. F.: Matrix Computations
Nocedal, J. & Wright, S. J.: Numerical Optimization
Hull, John C.: Options, Futures, and Other Derivatives (11th ed.)

6. Connected Graph Bridges

Foundational base: Linear Algebra · Multivariable Calculus & Optimization · Probability & Measure Theory
Applied destination: Derivative-Pricing Numerical Methods - the pricing-specific application of exactly these tools
Sub-pages (in-folder): 01 From Zero · 02 Finite Differences · 03 Monte Carlo · 04 Numerical Optimization · 05 Numerical Linear Algebra · 06 Advanced Extensions

Beginner: start at 01 · Practitioner: start at 05

Kwant Atlas

Explorer

1. Intuition & Practical Objective

2. Mathematical Ground Truth & Derivations

3. Computational Implementation - the three primitives on one screen

4. Failure Modes & First-Principles Breakdowns

5. References

6. Connected Graph Bridges

M.8.1 Numerical Methods from Zero

M.8.2 Finite-Difference Methods

M.8.3 Monte Carlo

M.8.4 Numerical Optimization & Root-Finding

M.8.5 Numerical Linear Algebra

M.8.6 Advanced Extensions