Numerical Recipes: The Art of Scientific Computing

Citation

Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press.

Chapter Summary

The third edition has 22 chapters with the index starting on page 1195, and C++ code throughout. Chapter 1 sets up the conventions; Chapters 2 to 13 cover the classical core of scientific computing; Chapters 14 to 16 turn to data, modelling and inference; Chapters 17 to 20 treat differential and integral equations; and Chapters 21 and 22 add computational geometry and non-numerical algorithms. Each chapter begins with a section numbered 0 that introduces the topic, then proceeds through numbered methods.

Chapter 1: Preliminaries

Introduction, error, accuracy and stability, C family syntax, objects, classes and inheritance, vector and matrix objects, and some further conventions. The preface directs readers to Sections 1.3 to 1.5 for the object-oriented style the book adopts.

Chapter 2: Solution of Linear Algebraic Equations

Gauss–Jordan and Gaussian elimination, LU decomposition, tridiagonal and band-diagonal systems, iterative improvement, singular value decomposition, sparse systems, Vandermonde and Toeplitz matrices, Cholesky and QR decomposition, and a closing section asking whether matrix inversion is an N³ process.

Chapters 3–5: Interpolation and Extrapolation; Integration of Functions; Evaluation of Functions

Searching ordered tables, polynomial, spline and rational interpolation, interpolation on grids and on scattered data, and Laplace interpolation (Chapter 3). Classical quadrature formulas, Romberg integration, improper integrals, variable transformation, Gaussian quadratures, adaptive quadrature and multidimensional integrals (Chapter 4). Polynomials, continued fractions, series and their convergence, recurrence relations, numerical derivatives, Chebyshev approximation, Padé approximants and rational Chebyshev approximation (Chapter 5).

Chapter 6: Special Functions

Gamma, beta and error functions, exponential integrals, Bessel and Airy functions, spherical harmonics, Fresnel integrals, Dawson's integral, Fermi–Dirac integrals, elliptic integrals, hypergeometric functions and statistical functions.

Chapter 7: Random Numbers

Uniform deviates, deviates from other distributions, multivariate normal deviates, linear feedback shift registers, hash tables and hash memories, simple Monte Carlo integration, quasi-random sequences, and adaptive and recursive Monte Carlo methods.

Chapters 8–10: Sorting and Selection; Root Finding and Nonlinear Sets of Equations; Minimization or Maximization of Functions

Sorting, ranking and selection algorithms (Chapter 8). Bracketing, bisection, the secant and Brent methods, Newton–Raphson, roots of polynomials, and nonlinear systems (Chapter 9). One-dimensional and multidimensional minimization (golden section, Brent, downhill simplex, Powell's, conjugate gradient and quasi-Newton methods), linear programming by the simplex and interior-point methods, simulated annealing and dynamic programming (Chapter 10).

Chapter 11: Eigensystems

Jacobi transformations, tridiagonal reduction by Givens and Householder methods, eigenvalues of symmetric, Hermitian and real nonsymmetric matrices, the QR algorithm and inverse iteration.

Chapters 12–13: Fast Fourier Transform; Fourier and Spectral Applications

Fourier transforms of sampled data, the FFT and its variants for real data, sine and cosine transforms and higher dimensions (Chapter 12). Convolution, correlation, Wiener filtering, power spectrum estimation, digital filtering, linear prediction, maximum entropy spectra, unevenly sampled data, Fourier integrals, wavelet transforms and the sampling theorem (Chapter 13).

Chapters 14–16: Statistical Description of Data; Modeling of Data; Classification and Inference

Moments, tests of whether distributions differ, contingency tables, correlation, information-theoretic properties and Savitzky–Golay smoothing (Chapter 14). Least squares as maximum likelihood, straight-line and general linear fits, nonlinear models, confidence limits, robust estimation, Markov chain Monte Carlo and Gaussian process regression (Chapter 15). Gaussian mixture models and k-means, Viterbi decoding, hidden Markov models, hierarchical clustering and support vector machines (Chapter 16).

Chapters 17–20: Integration of Ordinary Differential Equations; Two-Point Boundary Value Problems; Integral Equations and Inverse Theory; Partial Differential Equations

Runge–Kutta, adaptive step size, Bulirsch–Stoer, stiff systems, multistep methods and stochastic simulation of chemical reaction networks (Chapter 17). Shooting and relaxation methods, with spheroidal harmonics as a worked example (Chapter 18). Fredholm and Volterra equations, singular kernels, regularization, the Backus–Gilbert method and maximum entropy image restoration (Chapter 19). Flux-conservative and diffusive initial value problems, Fourier, cyclic reduction, relaxation, multigrid and spectral methods (Chapter 20).

Chapters 21–22: Computational Geometry; Less-Numerical Algorithms

Points and boxes, KD trees, triangles, polygons, Delaunay triangulation and quadtrees (Chapter 21). Plotting simple graphs, machine parameters, Gray codes, checksums, Huffman and arithmetic coding, and arbitrary-precision arithmetic (Chapter 22).

Key Concepts

Chapters 1–5: Foundations

• Error, accuracy and stability: why algorithms that look equivalent behave differently on a computer.
• Matrix decompositions: LU, Cholesky, QR and singular value decomposition as the basis for linear algebra.
• Quadrature and interpolation: choosing among classical formulas, Gaussian quadrature and splines.

Chapters 6–11: Core numerical methods

• Random deviates and Monte Carlo integration: generating samples and using them for integrals.
• Root finding and minimization: bracketing, Newton-type iteration and multidimensional search.
• Eigensystems: reduction to tridiagonal form and the QR algorithm.

Chapters 12–16: Signals, data and inference

• FFT and spectral estimation: sampling, convolution, filtering and power spectra.
• Least squares and maximum likelihood: fitting models with confidence limits.
• Markov chain Monte Carlo: sampling a posterior distribution.

Chapters 17–22: Equations and algorithms

• Adaptive step size and stiffness: the central issues in integrating ODEs.
• Relaxation and multigrid methods: solving boundary value problems.
• Delaunay triangulation and KD trees: geometric data structures.

Critical Analysis

Strengths

• Explanation with working code. The preface says the second edition came to be valued for its text explanations, concise derivations, critical judgments and advice, and that the authors kept the code so that readers could judge whether the advice is honest, implementable and practical. Each topic therefore combines discussion with a routine.
• Wide scope in one volume. The contents run from linear algebra and special functions through spectral analysis, statistics, differential equations and computational geometry, so one book serves as a first stop for many different tasks.
• A substantially revised edition. The preface lists several hundred pages of new material, including the chapters on classification and inference and on computational geometry, expanded random-number and distribution sections, interior-point linear programming, dynamic programming, Markov chain Monte Carlo and Gaussian process regression.
• Opinionated, practical voice. The preface to the second edition describes the aim as an informal, editorial, useful book; the third-edition preface adds that it is written for readers who already know that code for most algorithms can be found and want to understand how it works and whether it is any good.

Limitations

• A reference, not a sequential course. The contents are organized by family of methods rather than as a single progression, so the book is better suited to looking up a topic than to learning numerical analysis step by step.
• Tied to its own C++ style. The code uses the authors' object-oriented conventions, which Chapter 1 explains, and which readers working in Python or another language will have to translate or avoid.
• Licensing. The book opens with a License and Legal Information section covering the code; read it before reusing routines in your own projects.
• Breadth limits depth. Many methods occupy only a few pages, so for a specialist topic such as partial differential equations or optimization a dedicated text will go further.

Where It Fits in the Course

Within this computational-physics list, Numerical Recipes is the broad method reference. Newman's Computational Physics and Landau, Páez and Bordeianu's Computational Physics: Problem Solving with Python are textbooks that teach numerical methods through worked physics problems in Python; they are the better choice for a first course, and Kinder and Nelson's A Student's Guide to Python for Physical Modeling gives the language background. Taylor's An Introduction to Error Analysis covers the treatment of uncertainty in experimental measurements, a different subject from numerical error. Thijssen's Computational Physics is a graduate account of research methods in condensed matter physics.

Use Numerical Recipes alongside a course text: when a method named in a textbook needs a fuller explanation or a robust implementation to compare against, the relevant chapter here is a good place to look.

How to Use This Book

The book suits students and researchers who can program (the code is C++) and have calculus, linear algebra and some probability, and who need to choose, understand and implement numerical methods.

A practical plan:

• Start with: Chapter 1 for the error and stability discussion and the coding conventions, and Chapter 2 for linear algebra.
• Look up as needed: Chapters 3 to 5 for interpolation, integration and function evaluation, Chapters 9 and 10 for roots and optimization, Chapter 11 for eigenvalues, Chapter 17 for ODEs.
• For data work: Chapters 7, 14, 15 and 16 on random numbers, statistics, modelling and inference; for signals, Chapters 12 and 13.
• Specialist chapters: Chapters 18 to 22 when a project calls for boundary value problems, inverse problems, partial differential equations, geometry or coding algorithms.
• Method: read the introductory section 0 of a chapter before choosing a method, then compare the recommended routine with your own implementation on a test problem.