The Condition Number

A measure of how much a matrix can amplify errors, deciding whether a linear system can be solved accurately.

What it measures

The condition number of a matrix quantifies how sensitive the solution of Ax = b is to small changes in A or b. For the 2-norm it equals the ratio of the largest to the smallest singular value. A condition number near 1 means the problem is well conditioned; a very large value means it is ill conditioned, and tiny input errors can produce large output errors.

The error bound

If the data has a relative error, the relative error in the computed solution can be as large as the condition number times that data error. As a rule of thumb, a condition number of 10^k costs about k digits of accuracy. With about 16 digits in double precision, a condition number of 10^16 can destroy all accuracy.

It is a property of the problem

Ill conditioning is a property of the matrix, not of the algorithm. No solver, however clever, can recover accuracy that the conditioning has already lost; a stable algorithm merely avoids adding further error. The remedy is to reformulate the problem, rescale the variables, or add regularization to improve the conditioning itself.

Regularization

When a matrix is nearly singular, adding a small positive multiple of the identity, as in ridge regression, raises the smallest singular values and lowers the condition number, trading a small bias for far greater numerical stability. The SVD makes this trade explicit by exposing the small singular values directly.

import numpy as np
A = np.array([[1.0, 1.0], [1.0, 1.0001]])
print(np.linalg.cond(A))   # very large: nearly singular

In simulations of stiff physical systems, operators can be badly conditioned across widely separated scales, so preconditioning to compress the singular-value spread is often what makes a solve feasible at all.