The Condition Number of a Matrix

[Namir]

I have heard of the Condition Number of a Matrix in the past and have not paid much attention to this matrix property, until recently. I have been playing with a search algorithm that solves iteratively systems of linear equations. After the basic testing, I moved to more involved testing that uses random matrices. I began to notice that the number of iterations (for a fixed number of equations) varied widely!! I wrote my Matlab and Excel VBA code such that I can watch the progress of conversion to the solution. I noticed that in some cases the solution converged faster than other cases, where the iteration seem to struggle. I first looked at the value of the determinant of the matrix as a possible indicator for how easy or difficult to work with a articular matrix. I then came across internet articles that talked about the condition number of a matrix as being a good indicator for the ease or difficulty of solving linear equations with a matrix [bold]regardless of the algorithm used and the precision of the computation[/bold]. I find this to be somewhat of a revelation since most numerical analysis books rarely mention the condition number of a matrix as an indicator for the level of ease to solve linear equations.

Namir

Edited: 8 Feb 2012, 9:50 a.m.

[Jeff Kearns]

Condition Number
is defined as the product of the norm of A and the norm of A-inverse.

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).

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.

[Namir]

Right on Jeff!!!