Condition Numbers and Stability for Linear Systems - Introduction to Scientific Computing

Recap: Forward and Backward Error¶

We introduced forward and backward error earlier. The golden rule connects them:

\text{relative forward error} \lesssim \kappa \times \text{relative backward error}

(1)

The key questions for linear systems:

What is the condition number $\kappa(A)$ ?
When is a system ill-conditioned?
Which algorithms achieve small backward error?

Sensitivity of Linear Systems¶

How sensitive is the solution $\mathbf{x}$ to perturbations in $A$ and $\mathbf{b}$ ?

For a function $f(x)$ , we perturbed the input $x$ . But a linear system $A\mathbf{x} = \mathbf{b}$ has two inputs: the matrix $A$ and the vector $\mathbf{b}$ . Both are subject to errors:

$\mathbf{b}$ comes from measurements — always has some noise
$A$ comes from a model — coefficients may be uncertain, or stored with roundoff error

So we must understand how errors in both $A$ and $\mathbf{b}$ propagate to errors in $\mathbf{x}$ .

Theorem 1 (Sensitivity of Linear Systems)

For the linear system $A\mathbf{x} = \mathbf{b}$ :

\frac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|} \lesssim \kappa(A) \left(\frac{\|\delta A\|}{\|A\|} + \frac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|}\right)

(2)

The quantity $\kappa(A) = \|A\| \|A^{-1}\|$ is the amplification factor from relative input perturbation to relative output error.

The Condition Number¶

The sensitivity theorem motivates the following definition:

Rule of thumb: Expect to lose $\log_{10}\kappa(A)$ digits of accuracy.

Condition Number	Digits Lost
$\kappa \approx 10^k$	~ $k$ digits
$\kappa \gtrsim 1/\varepsilon_{\text{mach}} \approx 10^{16}$	All digits

But what does it mean for a matrix to be ill-conditioned? The next section provides the key insight.

The Deep Insight: Numerically Singular Matrices¶

Extension: When Ill-Conditioned Means Singular (Demmel)

A matrix with $\kappa(A) \gtrsim 1/\varepsilon_{\text{mach}}$ is numerically indistinguishable from a singular matrix.

Residuals and Backward Error¶

For linear systems, backward error has a simple form:

Residual: $\mathbf{r} = \mathbf{b} - A\hat{\mathbf{x}}$

The computed solution $\hat{\mathbf{x}}$ exactly solves $A\hat{\mathbf{x}} = \mathbf{b} - \mathbf{r}$ . The relative backward error is $\|\mathbf{r}\|/\|\mathbf{b}\|$ .

Practical Guideline: Always Check the Condition Number¶

Since the forward error satisfies

\frac{\|\hat{\mathbf{x}} - \mathbf{x}\|}{\|\mathbf{x}\|} \lesssim \kappa(A) \cdot \varepsilon_{\text{mach}}

(10)

we should always estimate $\kappa(A)$ before trusting the solution. But how?

The Challenge¶

Computing $\kappa(A) = \|A\| \|A^{-1}\|$ exactly requires $A^{-1}$ , which costs $O(n^3)$ operations—as expensive as solving the system! We need a cheaper approach.

Hager’s Algorithm: A Clever Trick¶

The key insight (Hager, 1984; refined by Higham) is that we can estimate $\|A^{-1}\|$ using only a few solves with the already-factored matrix.

Cost: Each iteration requires two triangular solves. Typically converges in 2–5 iterations, so total cost is $O(n^2)$ —much cheaper than the $O(n^3)$ factorization.

See the Condition Number Estimation notebook for a Python implementation.

What LAPACK Does¶

LAPACK’s routines (e.g., dgecon) implement this estimation automatically. When you call np.linalg.cond(A) or use SciPy’s linear solvers with condition estimation, this is what happens behind the scenes.

Stability of Algorithms: A Preview¶

An algorithm is backward stable if it produces a solution with backward error $\sim \varepsilon_{\text{mach}}$ . Combined with the golden rule:

\text{forward error} \lesssim \kappa(A) \cdot \varepsilon_{\text{mach}}

(11)

This is the best we can hope for—any algorithm must contend with the condition number.

Coming up: We’ll see that:

Householder QR is backward stable (the gold standard)
LU with partial pivoting is backward stable in practice (with caveats)
Classical Gram-Schmidt is not stable—orthogonality loss scales with $\kappa(A)$