Condition Numbers and Error Analysis for Linear Systems

The sensitivity of $Ax = b$ to perturbations in $A$ and $b$ is governed by the condition number of $A$ . Understanding conditioning is crucial for assessing the reliability of computed solutions and designing stable algorithms.

Condition Number

Definition5.7Matrix Condition Number

The condition number of a nonsingular matrix $A$ with respect to a matrix norm $\|\cdot\|$ is $\kappa(A) = \|A\| \cdot \|A^{-1}\|$ . For the 2-norm, $\kappa_2(A) = \sigma_{\max}(A) / \sigma_{\min}(A)$ where $\sigma_{\max}$ and $\sigma_{\min}$ are the largest and smallest singular values. A matrix is well-conditioned if $\kappa(A)$ is small (close to 1) and ill-conditioned if $\kappa(A)$ is large. In floating-point arithmetic with machine epsilon $\varepsilon_{\text{mach}}$ , roughly $\log_{10}(\kappa(A))$ digits of accuracy are lost in solving $Ax = b$ .

ExampleThe Hilbert Matrix

The $n \times n$ Hilbert matrix $H_n$ with entries $h_{ij} = 1/(i + j - 1)$ is notoriously ill-conditioned. For $n = 5$ : $\kappa_2(H_5) \approx 4.8 \times 10^5$ . For $n = 10$ : $\kappa_2(H_{10}) \approx 1.6 \times 10^{13}$ . For $n = 15$ : $\kappa_2(H_{15}) \approx 10^{18}$ , exceeding $1/\varepsilon_{\text{mach}}$ in double precision. The condition number grows exponentially: $\kappa_2(H_n) \sim e^{3.5n}$ .

Perturbation Theory

Definition5.8Perturbation Bounds

If $Ax = b$ and $(A + \delta A)(x + \delta x) = b + \delta b$ , then $\frac{\|\delta x\|}{\|x\|} \leq \kappa(A) \left(\frac{\|\delta A\|}{\|A\|} + \frac{\|\delta b\|}{\|b\|}\right) + O(\|\delta A\|^2)$ . For perturbations in $b$ only: $\frac{\|\delta x\|}{\|x\|} \leq \kappa(A) \frac{\|\delta b\|}{\|b\|}$ . These bounds are sharp: there exist perturbations achieving equality (up to higher-order terms).

RemarkComponentwise Condition Numbers

The normwise condition number $\kappa(A)$ may overestimate the actual sensitivity. The componentwise condition number considers element-wise perturbations: $\mathrm{cond}(A, x) = \frac{\||A^{-1}| |A| |x|\|_\infty}{\|x\|_\infty}$ (where $|\cdot|$ denotes entrywise absolute value). This is relevant for sparse or structured systems where perturbations respect the sparsity pattern. Skeel's condition number $\kappa_S(A) = \||A^{-1}||A|\|_\infty$ provides a normwise upper bound.

Backward Error Analysis

Definition5.9Backward Error of a Computed Solution

The backward error of a computed solution $\hat{x}$ to $Ax = b$ is $\eta(\hat{x}) = \min\{\epsilon : (A + \delta A)\hat{x} = b + \delta b, \|\delta A\| \leq \epsilon\|A\|, \|\delta b\| \leq \epsilon\|b\|\}$ . Rigal-Gaches formula: $\eta(\hat{x}) = \frac{\|r\|}{\|A\|\|\hat{x}\| + \|b\|}$ where $r = b - A\hat{x}$ is the residual. A small backward error means $\hat{x}$ is the exact solution of a nearby problem. Combined with the condition number: $\frac{\|x - \hat{x}\|}{\|x\|} \lesssim \kappa(A) \cdot \eta(\hat{x})$ .

ExampleSmall Residual Does Not Imply Small Error

For the system $\begin{pmatrix} 1 & 1 \\ 1 & 1.0001 \end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix} = \begin{pmatrix}2\\2.0001\end{pmatrix}$ , the exact solution is $(1, 1)^T$ . The approximate solution $\hat{x} = (2, 0)^T$ gives residual $r = (0, -0.0001)^T$ with $\|r\|_\infty = 10^{-4}$ , but $\|x - \hat{x}\|_\infty = 1$ , a 100% relative error. The condition number $\kappa_\infty \approx 4 \times 10^4$ explains this amplification.