Fundamentals of Numerical Computation

FNC cover

This textbook is designed to introduce undergraduates in math, computer science, engineering, and related fields to the principles and practice of numerical computation. Our approach emphasizes linear algebra and approximation. The text presents mathematical underpinnings and analysis, complemented with 45 functions and over 160 examples coded in MATLAB, all available for download. Previous experience in MATLAB is not required. The functions and examples have also been implemented in Julia and Python.

The text is organized to be useful for either a one-semester introduction or two-semester sequence, with the most advanced techniques and concepts held back for the second half of the book.

Please note the known errata.

Resources

The book’s functions and example scripts can be downloaded as a MATLAB toolbox and installed by double-clicking the file. Alternatively, you can visit the Github page that has the needed files, as well as suggested in-class labs and projects, slides for instructors, and links to some (slightly outdated) videos linked to the text.

There are also Julia versions and Python versions of the function and example files.

Contents

  1. Numbers, problems, and algorithms
    1. Floating point numbers
    2. Problems and conditioning
    3. Stability of algorithms
  2. Square linear systems
    1. Polynomial interpolation
    2. Computing with matrices
    3. Linear systems
    4. LU factorization
    5. Efficiency of matrix computations
    6. Row pivoting
    7. Vector and matrix norms
    8. Conditioning of linear systems
    9. Exploiting matrix structure
  3. Overdetermined linear systems
    1. Fitting functions to data
    2. The normal equations
    3. The QR factorization
    4. Computing QR factorizations
  4. Roots of nonlinear equations
    1. The rootfinding problem
    2. Fixed point iteration
    3. Newton’s method in one variable
    4. Interpolation-based methods
    5. Newton for nonlinear systems
    6. Quasi-Newton methods
    7. Nonlinear least squares
  5. Piecewise interpolation and calculus
    1. The interpolation problem
    2. Piecewise linear interpolation
    3. Cubic splines
    4. Finite differences
    5. Convergence of finite differences
    6. Numerical integration
    7. Adaptive integration
  6. Initial-value problems for ODEs
    1. Basics of IVPs
    2. Euler’s method
    3. Systems of differential equations
    4. Runge-Kutta methods
    5. Adaptive Runge-Kutta
    6. Multistep methods
    7. Implementation of multistep methods
    8. Zero-stability of multistep methods
  7. Matrix analysis
    1. From matrix to insight
    2. Eigenvalue decomposition
    3. Singular value decomposition
    4. Symmetry and definiteness
    5. Dimension reduction
  8. Krylov methods in linear algebra
    1. Sparsity and structure
    2. Power iteration
    3. Inverse iteration
    4. Krylov subspaces
    5. GMRES
    6. MINRES and conjugate gradients
    7. Matrix-free iterations
    8. Preconditioning
  9. Global function approximation
    1. Polynomial interpolation
    2. The barycentric formula
    3. Stability of polynomial interpolation
    4. Orthogonal polynomials
    5. Trigonometric interpolation
    6. Spectrally accurate integration
    7. Improper integrals
  10. Boundary-value problems
    1. Shooting
    2. Differentiation matrices
    3. Collocation for linear problems
    4. Nonlinearity and boundary conditions
    5. The Galerkin method
  11. Diffusion equations
    1. Black-Scholes equation
    2. The method of lines
    3. Absolute stability
    4. Stiffness
    5. Method of lines for parabolic PDEs
  12. Advection equations
    1. Traffic flow
    2. Upwinding and stability
    3. Absolute stability for advection
    4. The wave equation
  13. Two-dimensional problems
    1. Tensor-product discretizations
    2. Two-dimensional diffusion and advection
    3. Laplace and Poisson equations
    4. Nonlinear elliptic PDEs