Condition number of a matrix

For square matrices we can measure the sensitivity of the solution of the linear algebraic system
Ax=b with respect to changes in vector b and in matrix A by using the notion of the
condition number of matrix A.

Condition number is defined as the product of the norm of A and the norm of A-inverse.
(for the norm of A see below)


If we use the usual Euclidean norm on vectors and the associated matrix norm, then the condition number is the ratio of the largest singular value of matrix A to the smallest. (Singular values are computed by process called SVD - Singular Value Decomposition and in Matlab the calculation is simply invoked by command svd). Matlab computes the condition number corresponding to the Euclidean norm.

Condition number depends on the underlying norm. However, regardless of the norm, it is always greater or equal to 1. If it is close to one, the matrix is well conditioned which means its inverse can be computed with good accuracy. If the condition number is large, then the matrix is said to be ill-conditioned. Practically, such a matrix is almost singular, and the computation of its inverse, or solution of a linear system of equations is prone to large numerical errors. A matrix that is not invertible has the condition number equal to infinity.

In Matlab, condition number is computed for the Euclidean norm. However, for manual calculations it is easier to use other matrix norms.

Example given below shows how to compute the condition number for a simple matrix and the so-called 1-norm of the matrix (see Matlab command 'norm'). Consider the following matrix


where denotes a small parameter. Matrix of this type is nearly singular, since its determinant is equal to . Geometrically, the vectors represented by columns of A are almost aligned. We calculate the inverse


and we calculate the norms and the condition number


This shows that the condition number grows unbounded as parameter goes to zero. Large condition number tells us that the matrix is poorly invertible and the accuracy of solution of a linear system may be bad.

Once we have the condition number we can estimate the sensitivity of solution of a linear algebraic system to variations of parameters in matrix A and in vector b.

Consider the equation system with perturbations in matrix A and :

The relative error in the solution caused by perturbations of parameters can be estimated by the following inequality:

Therefore, the relative error in solution x can be as large as condition number times the relative error in A and b.

In signal processing, condition number of the correlation matrix will tell us what may be the expected accuracy of solution of optimal taps in the filter, and will determine the speed of convergence of any gradient-based algorithm seeking the minimum of the quadratic error function.
 


web-posted on Feb 3, 1998