Error, Chance and the Machine

Numerical Analysis, Inference and Stochastic Methods for Physics in 13 chapters — from “Rounding, backward error and the sensitivity of a computation” to “Partial differential equations: stability, convergence and solvers”.

Chapters

  1. Rounding, backward error and the sensitivity of a computation
    • Machine epsilon, twice defined, and the unit roundoff
    • Vector and matrix norms
    • Backward error and the residual
    • The forward error bound and backward stability
    • Summation error and the order of a sum
    • The unstable one-pass variance
    • Root sensitivity and Wilkinson's polynomial
    • Eigenvalue sensitivity and symmetry
    • What is settled and what is open
    • Problems
  2. Linear systems, least squares and the singular value decomposition
    • Elimination as LU factorisation
    • The growth factor and why pivoting works
    • Cholesky factorisation and the tridiagonal solver
    • The QR factorisation by reflections
    • Least squares by QR
    • The singular value decomposition
    • Tikhonov regularisation of an ill-posed problem
    • What is settled and what is open
    • Problems
  3. Iteration: nonlinear systems and eigenvalues
    • Fixed-point iteration and the contraction condition
    • Order of convergence, defined and measured
    • Newton's method for systems and the Lagrange points
    • The damped Newton step
    • Power iteration and its convergence ratio
    • Shifted inverse iteration and the Rayleigh quotient
    • The QR algorithm and Gershgorin's discs
    • Polynomial roots as eigenvalues
    • Iteration: what is settled and what stays open
    • Problems
  4. Approximating a function: interpolation and differentiation
    • Interpolation as a linear map on data
    • The Lebesgue constant
    • Chebyshev points
    • The barycentric formula
    • Spectral accuracy and the Bernstein ellipse
    • Finite-difference weights for any stencil
    • The complex-step derivative
    • Differentiating noisy data
    • Summary: what is settled and what is open
    • Problems
  5. Integration: error expansions, Gauss rules and adaptivity
    • Interpolatory quadrature and positive weights
    • The Euler-Maclaurin formula
    • The periodic trapezium rule
    • Romberg integration
    • Gauss rules from orthogonal polynomials
    • Clenshaw-Curtis quadrature
    • A posteriori error estimates and adaptivity
    • The Nyström method for integral equations
    • Summary
    • Problems
  6. Estimators and the information in data
    • Bias and consistency of estimators
    • The characteristic function
    • A proof of the central limit theorem
    • Fisher information and the Cramér-Rao bound
    • Asymptotic efficiency of maximum likelihood
    • The covariance matrix of fitted parameters
    • The Poisson likelihood fit for small counts
    • Summary
    • Problems
  7. Tests, intervals and Bayesian inference
    • The chi-squared distribution of a fit
    • The Neyman-Pearson lemma and statistical power
    • The likelihood-ratio test and Wilks' theorem
    • The Neyman construction and upper limits
    • Bayes' theorem and the posterior distribution
    • Prior dependence and Jeffreys' prior
    • Multiple testing and the look-elsewhere effect
    • Summary
    • Problems
  8. Random walks and Markov chains
    • The generating function of a walk
    • First-passage probability
    • Recurrence and transience by dimension
    • Absorbing walls and the gambler's ruin
    • The transition matrix and absorbing chains
    • The stationary distribution
    • Detailed balance and reversibility
    • The spectral gap and the autocorrelation time
    • Summary
    • Problems
  9. Random processes in continuous time
    • The Poisson process of counter clicks
    • The master equation
    • The stochastic simulation algorithm
    • The Wiener process
    • The Langevin equation and the Ornstein-Uhlenbeck process
    • The Fokker-Planck equation
    • Mean first-passage time
    • Summary
    • Problems
  10. Monte Carlo integration and variance reduction
    • Variance of a Monte Carlo estimator
    • Sampling correlated Gaussians
    • Importance sampling
    • Control variates and antithetic variates
    • Stratified sampling and quasi-Monte Carlo
    • Monte Carlo particle transport
    • Summary and scope
    • Problems
  11. Markov-chain Monte Carlo
    • Hard discs and sampling a Boltzmann distribution
    • The Metropolis-Hastings algorithm
    • Proposal tuning and the effective sample size
    • Batch means
    • Metastability and slow mixing
    • Gibbs sampling and Hamiltonian Monte Carlo
    • Convergence diagnostics
    • Summary
    • Problems
  12. Ordinary differential equations: order, stability and stiffness
    • Local truncation error and convergence
    • Runge-Kutta order conditions
    • The linear stability region
    • Stiffness
    • A-stability and the implicit step
    • Embedded error estimates and step control
    • Multistep methods and zero-stability
    • The shooting method for boundary-value problems
    • The Euler-Maruyama method
    • Summary
    • Problems
  13. Partial differential equations: stability, convergence and solvers
    • The method of lines for diffusion
    • Von Neumann stability analysis
    • Upwind differencing and the CFL condition
    • Numerical diffusion and the modified equation
    • The Lax equivalence theorem
    • The Crank-Nicolson scheme
    • Relaxation methods for the Poisson equation
    • The conjugate gradient method
    • Galerkin finite elements in one dimension
    • Summary
    • Problems