Phase 18 - Lesson 18.1

Capstone 1 - Mathematical and Numerical Foundations

Build and validate a small numerical toolkit - differentiation, integration, linear solves, least squares, decomposition, optimization - each checked against theory.

⏱ 120 min● Advanced🔗 Prereqs: Phases 2, 3, 4, 5, 10

↖ Phase 18 hub

Builds on: Integrates Calculus (Phases 2–3), Linear Algebra (Phase 4), Numerical LA (Phase 5), and Optimization (Phase 10).
Leads to: The routines you validate here are reused by every later capstone (pricing grids, regressions, calibration).

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Implement finite-difference differentiation and verify the error scales at the predicted order.
Implement numerical integration and compare its convergence to the analytic value.
Solve a linear system and a least-squares problem and validate against the normal equations / QR.
Compute a matrix decomposition (Cholesky/QR) and verify the defining identity.
Minimize a convex function numerically and check first-order optimality.

Key Vocabulary

Finite difference: Approximating a derivative by a difference quotient; central differences have \(O(h^2)\) truncation error.

Quadrature: Numerical integration, e.g. the trapezoidal or Simpson rule, approximating \(\int f\) by weighted samples.

Least squares: Finding \(x\) minimizing \(\|Ax-b\|_2^2\); solved stably by QR, not by forming \(A^\top A\) blindly.

Cholesky decomposition: Factoring a symmetric positive-definite \(\Sigma=LL^\top\) with \(L\) lower-triangular; used for correlated draws.

Condition number: How much a solution amplifies input error; large \(\kappa\) warns of numerical instability.

First-order optimality: At a minimum of a smooth convex \(f\), the gradient vanishes: \(\nabla f(x^\star)=0\).

Intuition & Motivation

Intuition

Every pricing model, regression, and calibration you will ever run rests on a handful of numerical primitives: take a derivative, take an integral, solve \(Ax=b\), fit a least-squares line, factor a covariance, minimize a loss. This capstone makes you build those primitives and, crucially, validate each against what theory predicts - the error order, the analytic integral, the defining matrix identity, the optimality condition.

The theme is honesty: a numerical routine is not ‘done’ when it returns a number; it is done when you have checked the number against an independent truth. That habit - from Phase 17’s testing discipline - is what separates a toolkit you can trust from a pile of functions that happen to run.

The brief

Assemble a validated micro-library numkit with five routines, each accompanied by a test that checks it against theory. Deliverable: the code plus a one-page validation table (routine, what was checked, observed vs. predicted).

Required theory recap

Differentiation (Phase 2): central difference \(f'(x)\approx\frac{f(x+h)-f(x-h)}{2h}\) with error \(O(h^2)\).
Integration (Phase 2): trapezoid rule error \(O(h^2)\); Simpson \(O(h^4)\).
Linear systems & least squares (Phases 4–5): \(Ax=b\) via LU; \(\min\|Ax-b\|_2\) via QR; normal equations \(A^\top Ax=A^\top b\).
Decomposition (Phase 5): Cholesky \(\Sigma=LL^\top\) for SPD matrices.
Optimization (Phase 10): for smooth convex \(f\), solve \(\nabla f=0\); check with a gradient-descent or Newton step.

Convergence-order test: the heart of validation

A central difference has truncation error \(\propto h^2\). So halving \(h\) should cut the error by ~4. Measuring that ratio is how you prove your derivative code is correct at the claimed order:

\[\text{err}(h)=|f'_{\text{approx}}(x;h)-f'(x)|=C h^2+o(h^2)\ \Rightarrow\ \frac{\text{err}(h)}{\text{err}(h/2)}\to 4.\] (18.1)

Worked Example - A reference validation for the derivative routine

Test function with known derivative: \(f(x)=\sin x,\ f'(x)=\cos x\), evaluate at \(x=1\).

Compute err(h) for \(h=10^{-2}\) and err(h/2) for \(h=5\times10^{-3}\).

Central difference is \(O(h^2)\), so the ratio err(h)/err(h/2) should be near 4 (not 2, which would be first-order).

If the ratio is ~2, you have a one-sided difference or a sign bug; if it plateaus, you hit round-off (h too small - catastrophic cancellation).

Report: predicted ratio 4, observed ≈ 4.0 - the routine is validated at second order.

Least squares: solve it the stable way

Given \(A\in\R^{m\times n}\), \(b\in\R^m\), \(m\gt n\), the least-squares solution minimizes \(\|Ax-b\|_2^2\). The normal equations \(A^\top Ax=A^\top b\) are correct but square the condition number; QR is the stable route. Validate by checking the residual is orthogonal to the column space: \(A^\top(Ax^\star-b)=0\).

\[x^\star=\arg\min_x\|Ax-b\|_2^2\quad\Longleftrightarrow\quad A^\top(Ax^\star-b)=\mathbf 0.\] (18.2)

Decomposition and optimization checks

Cholesky: factor an SPD \(\Sigma\), then verify \(LL^\top=\Sigma\) with allclose. A non-SPD input must be rejected (the factorization fails) - test that too.
Optimization: minimize \(f(x)=\tfrac12 x^\top Qx - c^\top x\) with SPD \(Q\); the analytic minimizer is \(x^\star=Q^{-1}c\). Validate that your solver’s answer satisfies \(\|\nabla f(x^\star)\|=\|Qx^\star-c\|\approx0\).

▶ Reference architecture for numkit

Five pure functions, each with a paired test, wired through a single validation harness:

numkit/diff.py -> central_diff(f,x,h); test_diff -> order ~2 numkit/quad.py -> trapezoid(f,a,b,n); test_quad -> err vs analytic numkit/solve.py -> lstsq_qr(A,b); test_solve-> A^T(Ax-b)=0 numkit/decomp.py -> chol(Sigma); test_chol -> LL^T=Sigma numkit/opt.py -> min_quadratic(Q,c); test_opt -> grad ~ 0 numkit/validate.py -> runs all, prints table (routine, predicted, observed)

Every routine is DRY and orthogonal (17.4): no test imports another routine’s internals, and the tolerance for each is chosen from that method’s error, not arbitrarily (17.2).

Common Mistakes to Avoid

Claiming a routine works because it ‘returns a number’ - without checking the error order or an analytic value.
Shrinking \(h\) indefinitely in finite differences; below \(\sqrt{\epsilon_{\text{mach}}}\) round-off dominates and error grows again.
Forming \(A^\top A\) for an ill-conditioned least-squares problem, squaring the condition number and losing accuracy.
Running Cholesky on a matrix that isn’t positive-definite and not handling the failure.
Using a tolerance unrelated to the method’s accuracy (e.g. 1e-12 for a trapezoid rule with n=50).
Reporting the optimizer’s answer without checking \(\nabla f\approx0\) (it may have stopped early).

Quant Practitioner Tips

Validate every numerical routine against an independent truth: analytic value, error order, or a defining identity.
For finite differences, sweep \(h\) and plot error vs \(h\) on log–log axes; the slope is the order.
Prefer QR/SVD over normal equations for least squares; check \(A^\top r=0\) on the residual.
After any decomposition, assert the defining identity (\(LL^\top=\Sigma\), \(QR=A\)) holds.
Reuse these validated primitives in later capstones instead of re-deriving them - single source of truth (17.4).

Interactive: validate a differentiation and a least-squares routine

Implement the two routines and their theory checks; the tests encode the convergence-order and orthogonality conditions.

Knowledge Check

Q1 Medium

You halve \(h\) in a central-difference derivative and the error drops by a factor of ~4. This confirms:

First-order accuracy

\(O(h^2)\) second-order accuracy

Round-off error

A bug

Q2 Medium

For an ill-conditioned least-squares problem, why prefer QR over the normal equations?

QR is always faster

Forming \(A^\top A\) squares the condition number, amplifying error; QR avoids that

Normal equations are wrong

QR needs less memory

Q3 Easy

After computing a Cholesky factor \(L\) of \(\Sigma\), the validation you must run is:

Check \(L\) is symmetric

Check \(LL^\top=\Sigma\) to tolerance

Check \(L\) is orthogonal

No check needed

Practical Exercise

Design the validation table for your numkit. For each of the five routines (differentiation, integration, linear solve/least squares, Cholesky, quadratic minimization), state exactly (a) the test function or matrix, (b) the independent truth you compare against, and (c) the tolerance and why it is appropriate for that method’s error.

▶ Show full solution

A defensible validation table (numbers illustrative):

Routine	Test input	Independent truth	Tolerance & rationale
Central diff	\(f=\sin,\ x=1\)	\(\cos 1\); ratio → 4	ratio within 0.3 of 4 (order test)
Trapezoid	\(\int_0^1 x^2=1/3\)	analytic \(1/3\)	\(O(h^2)\): \(n=100\Rightarrow\) atol \(10^{-3}\)
Least squares	random \(A_{20\times3},b\)	\(A^\top(Ax-b)=0\)	\(10^{-9}\): QR near machine-precise
Cholesky	SPD \(\Sigma=BB^\top\)	\(LL^\top=\Sigma\)	\(10^{-10}\): exact up to round-off
Min quadratic	SPD \(Q\), vector \(c\)	\(x^\star=Q^{-1}c,\ \nabla f=0\)	\(\\|\nabla f\\|\lt 10^{-8}\)

The pattern is uniform: an independent truth (analytic value, error order, or defining identity) and a tolerance chosen from the method’s known accuracy (17.2), never an arbitrary constant.

After the reveal, answer for yourself: Which routine’s tolerance was hardest to justify, and what does that say about the method’s accuracy?

Lesson Summary

This capstone builds and, more importantly, validates the numerical primitives underlying all quant work: finite-difference differentiation (checked by its \(O(h^2)\) error order), quadrature (checked against analytic integrals), stable least squares via QR (checked by residual orthogonality \(A^\top r=0\)), Cholesky (checked by \(LL^\top=\Sigma\)), and convex minimization (checked by \(\nabla f=0\)). Trust comes from checking each routine against an independent truth with a method-appropriate tolerance.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: How do you prove a central-difference derivative is second-order accurate?
A: Measure the error against a known derivative at \(h\) and \(h/2\); the ratio should approach \(2^2=4\), confirming error \(\propto h^2\).

Q: What single identity validates a least-squares solution, and why prefer QR?
A: The residual must be orthogonal to the columns of \(A\): \(A^\top(Ax^\star-b)=0\). Prefer QR because the normal equations square the condition number \(\kappa(A^\top A)=\kappa(A)^2\).

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lec. 7-19 - QR, least squares, conditioning, and stable numerical linear algebra used in the validation.
Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. 3-5 - Differentiation and integration whose analytic values serve as the convergence oracles.
Additional Exercises for Convex Optimization (Boyd & Vandenberghe, 2016) current - Ch. 9 - Convex quadratic minimization and first-order optimality as the optimization check.

← 17.6 Next: 18.2 →