Numerical Linear Algebra
Numerical linear algebra develops algorithms for solving linear systems, least-squares problems, and eigenvalue problems on a computer, with explicit attention to accuracy, stability, and cost in finite-precision arithmetic.
Definition
Numerical linear algebra is the study of algorithms for performing linear-algebra computations — chiefly the solution of linear systems and eigenvalue/singular-value problems — together with the analysis of their accuracy, stability, and efficiency in finite-precision arithmetic.
Scope
This area covers the computational core that underlies most of scientific computing: solving Ax = b, computing matrix factorizations (LU, QR, Cholesky, SVD), finding eigenvalues and singular values, and analysing how rounding error and problem conditioning affect the computed result. It spans both dense and structured matrices and treats the floating-point behaviour of algorithms as a first-class concern.
Sub-topics
Core questions
- How can a linear system Ax = b be solved accurately and efficiently, and when is the answer trustworthy?
- Which matrix factorizations expose the structure needed for solving, least-squares, and eigenvalue problems?
- How do conditioning of the problem and stability of the algorithm jointly determine the error in finite-precision arithmetic?
- How can eigenvalues and singular values be computed without forming ill-conditioned intermediate quantities?
Key theories
- Backward error analysis
- A computed solution is interpreted as the exact solution of a slightly perturbed problem; an algorithm is backward stable if that perturbation is of the order of unit roundoff, which separates the algorithm's stability from the problem's conditioning.
- Conditioning and the condition number
- The sensitivity of a linear-algebra problem to perturbations is quantified by a condition number; for linear systems the relative error is bounded by the condition number of the matrix times the relative perturbation, independent of the algorithm used.
- Matrix factorization paradigm
- Most algorithms reduce a problem to a product of simpler (triangular, orthogonal, diagonal) factors; LU, QR, Cholesky, and the SVD provide canonical factorizations from which solutions, least-squares fits, and spectra are read off.
Clinical relevance
Numerical linear algebra is the computational substrate for virtually every quantitative discipline: discretized differential equations, optimization, statistics and regression, machine learning, signal and image processing, and network analysis all reduce to large linear systems, least-squares problems, or eigenvalue computations whose reliability depends on stable matrix algorithms.
History
The field was shaped in the mid-twentieth century by the advent of digital computers and by James H. Wilkinson's backward error analysis, which explained why Gaussian elimination with pivoting is reliable. Subsequent decades produced the QR algorithm for eigenvalues, systematic study of the singular value decomposition, and the high-quality libraries (LINPACK, LAPACK) that codified stable algorithms for general use.
Key figures
- James H. Wilkinson
- Gene H. Golub
- Lloyd N. Trefethen
- Nicholas J. Higham
Related topics
Seminal works
- trefethen1997
- golub2013
- higham2002
Frequently asked questions
- What is the difference between conditioning and stability?
- Conditioning is a property of the problem — how much the exact solution changes under perturbations of the data — while stability is a property of the algorithm — how much extra error it introduces in finite-precision arithmetic. A stable algorithm applied to an ill-conditioned problem can still produce a large error.
- Why are orthogonal transformations preferred in numerical linear algebra?
- Orthogonal (and unitary) transformations preserve the 2-norm and do not amplify rounding errors, so factorizations built from them — such as QR via Householder reflections — tend to be backward stable.