Exact algebra asks whether a solution exists. Numerical linear algebra also asks how errors in data and arithmetic affect it.
Choose a method by structure
| Problem | Typical method | Why |
|---|---|---|
| General nonsingular square system | LU with partial pivoting | Factor once, then use triangular solves |
| Hermitian positive-definite system | Cholesky | Uses symmetry and positive definiteness |
| Full-column-rank least squares | Householder QR | Avoids forming normal equations |
| Rank-deficient least squares / minimum norm | SVD | Reveals small singular values and null directions |
| Real symmetric / complex Hermitian eigenproblem | Specialized symmetric/Hermitian eigensolver | Preserves spectral structure |
| General dense eigenproblem | Schur-based algorithms | Avoids relying on ill-conditioned eigenvector bases |
Sparse and very large systems need methods that exploit structure; direct dense factorizations may be impractical.
Conditioning versus stability
For invertible square $A$, $\kappa_2(A)=\sigma_{\max}/\sigma_{\min}$. Conditioning describes sensitivity of the problem. Backward stability describes whether a computed result solves a nearby problem. Neither a tiny residual nor a stable algorithm guarantees a small forward error for an ill-conditioned system.
For approximate $\hat x$, define $r=b-A\hat x$. Then $x-\hat x=A^{-1}r$, so a useful nonzero-$b$ bound is
$$\frac{\|x-\hat x\|}{\|x\|}\le\kappa(A)\frac{\|r\|}{\|b\|}.$$
The bound can be pessimistic, but explains why residual and condition estimates should be interpreted together.
Practical pitfalls
- Solve $Ax=b$ directly; do not compute $A^{-1}$ merely to multiply it by $b$.
- In full-column-rank least squares, $\kappa_2(A^*A)=\kappa_2(A)^2$. Normal equations can magnify sensitivity.
- Numerical rank depends on a tolerance relative to scale and uncertainty. Exact nonzero entries are not sufficient.
- Pivoting controls many elimination difficulties, but is not a cure for an ill-conditioned problem.
- An eigenvalue problem and a linear-system problem have different condition measures. Do not apply $\kappa(A)$ indiscriminately to every task.
- Repeated eigenvalues and Jordan form are especially sensitive to perturbations; Jordan form is chiefly a structural tool.
Related: conditioning, LU, Cholesky, QR, SVD, and least squares.
Parents
Like how this is organised?
Build your own knowledge tree on knowen.md: notes, decisions and tasks in one connected markdown graph, shared with your team and your AI agents.