What Does a Matrix Condition Number Reveal About Sensitivity?
The condition number of a matrix measures how much the solution of a linear system can change in response to small perturbations in the input data. In classical computing, where numbers are stored with finite precision, it directly bounds the amplification of rounding errors during numerical computations. A small condition number indicates a well-conditioned problem that resists numerical noise, whereas a large condition number signals an ill-conditioned problem where tiny floating-point errors can lead to large inaccuracies in the computed solution.
Defining the Condition Number
Consider a system of linear equations written in matrix form as:
\[Ax = b\]
where \(A\) is an invertible \(n \times n\) matrix, \(b\) is a known vector, and \(x\) is the unknown solution vector. The condition number of \(A\), denoted \(\kappa(A)\), is defined with respect to a chosen matrix norm \(\|\cdot\|\) as:
\[\kappa(A) = \|A\| \|A^{-1}\|\]
By the properties of induced matrix norms, \(\kappa(A) \ge 1\) for any invertible matrix. For the identity matrix, \(\kappa(I) = 1\), representing the ideal case of zero error amplification. If \(A\) is singular (non-invertible), the condition number is conventionally taken to be \(\infty\).
Sensitivity to Input Perturbations
Suppose the right-hand side vector \(b\) is perturbed by a small amount \(\Delta b\), which might arise from measurement noise or from representing \(b\) in floating-point arithmetic. This perturbation causes a corresponding change \(\Delta x\) in the solution, satisfying:
\[A(x + \Delta x) = b + \Delta b \implies \Delta x = A^{-1} \Delta b\]
Taking norms and using the submultiplicative property \(\|A^{-1} \Delta b\| \le \|A^{-1}\| \|\Delta b\|\) alongside \(\|b\| = \|Ax\| \le \|A\| \|x\|\), we obtain the fundamental relative error bound:
\[\frac{\|\Delta x\|}{\|x\|} \le \kappa(A) \frac{\|\Delta b\|}{\|b\|}\]
This inequality shows that \(\kappa(A)\) acts as an amplification factor: the relative error in the solution \(x\) can be up to \(\kappa(A)\) times the relative error in \(b\). A similar bound holds when the matrix \(A\) itself is perturbed by \(\Delta A\).
Finite-Precision Rounding Errors in Classical Computing
In classical computers, real numbers are typically approximated using IEEE 754 floating-point arithmetic, which has a finite machine epsilon \(\epsilon_{\text{mach}}\) (roughly \(2.22 \times 10^{-16}\) for 64-bit double precision). Every arithmetic operation introduces rounding errors on the order of \(\epsilon_{\text{mach}}\).
When solving \(Ax = b\) with a numerically stable algorithm such as Gaussian elimination with partial pivoting, backward error analysis shows that the computed solution \(\hat{x}\) is the exact solution to a slightly perturbed system:
\[(A + \Delta A)\hat{x} = b\]
where the relative perturbation \(\|\Delta A\| / \|A\|\) is small, typically \(O(\epsilon_{\text{mach}})\). Combining this backward stability result with the condition number bound yields a forward error estimate:
\[\frac{\|\hat{x} - x\|}{\|x\|} \lesssim \kappa(A) \, \epsilon_{\text{mach}}\]
As a rule of thumb, if \(\kappa(A) \approx 10^k\), then solving the linear system in finite precision can lose up to \(k\) decimal digits of accuracy. In double-precision arithmetic (which provides about 16 decimal digits), a matrix with \(\kappa(A) \ge 10^{16}\) can produce a computed solution with no reliable digits at all.
Well-Conditioned vs. Ill-Conditioned Systems
- Well-conditioned (\(\kappa(A)\) close to \(1\)): Small rounding errors remain small in the final answer. Standard double-precision solvers produce highly accurate results.
- Ill-conditioned (\(\kappa(A) \gg 1\)): The matrix is nearly singular, meaning its columns are nearly linearly dependent. Even a backward-stable algorithm cannot guarantee an accurate solution in standard precision, because the problem itself is inherently sensitive to tiny perturbations.
To mitigate ill-conditioning in practice, engineers and scientists use techniques such as preconditioning (transforming the system into an equivalent one with a smaller condition number), iterative refinement, or switching to higher-precision arithmetic.