Numerical Linear Algebra

Citation

Trefethen, L. N., & Bau, D., III. (2022). Numerical Linear Algebra (25th anniversary ed.). SIAM.

Chapter Summary

The book is organised as forty short lectures, each built around one or two central ideas, grouped into six parts and followed by an appendix, notes and a bibliography. The original 1997 text runs to about 360 pages.

Part I, Fundamentals (Lectures 1–5): Matrix-Vector Multiplication; Orthogonal Vectors and Matrices; Norms; The Singular Value Decomposition; More on the SVD

The opening lectures re-read familiar linear algebra with computation in mind. Lecture 1 treats a matrix-vector product as a linear combination of the columns, extends the idea to matrix-matrix products, and covers range, nullspace and the inverse. Orthogonality and norms follow, and the part ends with the singular value decomposition, which the later parts keep returning to.

Part II, QR Factorization and Least Squares (Lectures 6–11): Projectors; QR Factorization; Gram-Schmidt Orthogonalization; MATLAB; Householder Triangularization; Least Squares Problems

Projectors lead to the reduced and full QR factorizations, computed first by Gram-Schmidt orthogonalization and then by Householder triangularization. Lecture 9 is a short MATLAB lecture, and the part closes with the use of these factorizations to solve least squares problems.

Part III, Conditioning and Stability (Lectures 12–19): Conditioning and Condition Numbers; Floating Point Arithmetic; Stability; More on Stability; Stability of Householder Triangularization; Stability of Back Substitution; Conditioning of Least Squares Problems; Stability of Least Squares Algorithms

This part supplies the vocabulary for judging algorithms: how sensitive a problem is, how floating point arithmetic behaves, and what it means for an algorithm to be stable. The ideas are then applied to the algorithms of Part II and to back substitution, so that the earlier methods are analysed rather than merely stated.

Part IV, Systems of Equations (Lectures 20–23): Gaussian Elimination; Pivoting; Stability of Gaussian Elimination; Cholesky Factorization

Gaussian elimination appears here, after QR, together with pivoting and an analysis of its stability. Cholesky factorization for symmetric positive definite matrices completes the part.

Part V, Eigenvalues (Lectures 24–31): Eigenvalue Problems; Overview of Eigenvalue Algorithms; Reduction to Hessenberg or Tridiagonal Form; Rayleigh Quotient, Inverse Iteration; QR Algorithm without Shifts; QR Algorithm with Shifts; Other Eigenvalue Algorithms; Computing the SVD

The eight lectures lay out the problem, reduce matrices to Hessenberg or tridiagonal form, study Rayleigh quotient and inverse iteration, and develop the QR algorithm without and with shifts. They close with other eigenvalue algorithms and the computation of the SVD.

Part VI, Iterative Methods (Lectures 32–40): Overview of Iterative Methods; The Arnoldi Iteration; How Arnoldi Locates Eigenvalues; GMRES; The Lanczos Iteration; From Lanczos to Gauss Quadrature; Conjugate Gradients; Biorthogonalization Methods; Preconditioning

Krylov subspace methods are built up through Arnoldi and Lanczos and applied to eigenvalue problems and to linear systems through GMRES, conjugate gradients and biorthogonalization methods, with preconditioning last.

Appendix and back matter

The appendix, "The Definition of Numerical Analysis", is followed by Notes that give sources and further reading, a bibliography and an index. Each lecture ends with exercises.

Key Concepts

Parts I–II

• Matrix-vector product as a combination of columns: the viewpoint introduced in Lecture 1 and used throughout.
• Singular value decomposition: a factorization introduced in Lecture 4 and revisited in Lecture 5 and Lecture 31.
• QR factorization: computed by Gram-Schmidt or Householder triangularization and applied to least squares.

Part III

• Condition number: a measure of how sensitive a problem is to perturbation.
• Floating point arithmetic and stability: the framework for judging whether an algorithm's answers are trustworthy.

Parts IV–VI

• Gaussian elimination with pivoting and Cholesky factorization: direct methods for linear systems.
• QR algorithm: the main eigenvalue method, developed with and without shifts.
• Krylov methods: Arnoldi, Lanczos, GMRES, conjugate gradients and preconditioning.

Critical Analysis

Strengths

• A clear stated design. The preface presents the book as a one-semester text scaled to a university course, built from forty lectures that each concentrate on one or two ideas and avoid getting lost in detail.
• QR before Gaussian elimination. The authors deliberately depart from the usual order, explaining that Gaussian elimination is atypical of the subject and hard to analyse, whereas QR factorization is the thread connecting least squares, eigenvalue, singular value and iterative methods.
• Conditioning and stability get a full part. Eight lectures treat these themes before any system-solving algorithm is analysed, and the stability analyses of later parts rely on them.
• A usable structure. Short lectures with exercises suit a course taught lecture by lecture, and the six-part layout makes it easy to see which lectures belong together.

Limitations

• Deliberately not a reference. The authors state that the book does not try to duplicate the encyclopedic Golub and Van Loan treatment; it is scaled to one semester, and they expect readers to consult Golub and Van Loan, and the books by Higham and Demmel described in the Notes, for further detail and additional topics.
• Compact exposition. With forty lectures of roughly eight pages each, derivations are brief, and readers need comfort with linear algebra in complex vector spaces, which the book adopts as its default setting.

Where It Fits in the Course

This is the specialised linear algebra text in the numerical analysis course. It does not replace a general numerical analysis book; it goes deeper on one thread. Burden, Faires and Burden's Numerical Analysis and Süli and Mayers' An Introduction to Numerical Analysis are broader introductions, the second more concerned with proofs of convergence, and either can come first. Stoer and Bulirsch's Introduction to Numerical Analysis is a comprehensive graduate text that covers more ground and overlaps with this book on linear systems and eigenvalues.

For readers who want to program before they analyse, Moler's Numerical Computing with MATLAB and the Python-based book on numerical methods are gentler and more hands-on starting points. Trefethen and Bau then supply the geometric and stability-based understanding behind routines such as the ones those books call.

How to Use This Book

The book suits first-year graduate students and advanced undergraduates in applied mathematics, scientific computing and engineering, and anyone who uses matrix algorithms and wants to know why they work. A good undergraduate linear algebra course is the main prerequisite, and some programming practice in MATLAB, Python or Julia is useful for the computational exercises.

A practical plan:

• Core: read Parts I–III in order. Lectures 1–5 on the SVD, Lectures 6–11 on QR and Lectures 12–15 on conditioning and stability carry most of the concepts that the rest of the book assumes.
• Next: Part V on eigenvalues and Part VI on iterative methods, each of which can be read as a unit once the SVD, QR and stability are familiar. Part IV can be read earlier if Gaussian elimination is the immediate need.
• Alongside: implement the algorithms as they appear, work the lecture exercises, and read the Notes for sources and further reading. Keep a larger reference at hand for topics beyond the forty lectures.