Who Invented the Matrix Condition Number?

matlab_cond.jpg

The condition number of a matrix is a well known measure of ill conditioning that has been in use for many years. For an n\times n matrix A it is \kappa(A) = \|A\| \|A^{-1}\|, where \|\cdot\| is any matrix norm. If A is singular we usually regard the condition number as infinite.

The first occurrences of the term “condition number” and of the formula \kappa(A) = \|A\| \|A^{-1}\| that I am aware of are in Turing’s 1948 paper Rounding-Off Errors in Matrix Processes. He defines the M-condition number n\|A\|_M \|A^{-1}\|_M and the N-condition number n^{-1}\|A\|_F \|A^{-1}\|_F, where \|A\|_M = \max_{i,j}|a_{ij}| and \|A\|_N = (\sum_{i,j}|a_{ij}|^2)^{1/2}, the latter N-norm being what we now call the Frobenius norm. He suggests using these condition numbers to measure the ill conditioning of a matrix with respect to linear systems, using a statistical argument to make the connection. He also notes that “the best conditioned matrices are the orthogonal ones”.

In his 1963 book Rounding Errors in Algebraic Processes, Wilkinson credits the first use of “condition number” to Turing and notes that “the term `ill-condition’ had been in common use among numerical analysts for some considerable time before this”. An early mention of linear equations being ill conditioned is in the 1933 paper An Electrical Calculating Machine by Mallock. According to Croarken, Mallock’s machine “could not adequately deal with ill conditioned equations, letting out a very sharp whistle when equilibrium could not be reached”.

As noted by Todd (The Condition of a Certain Matrix, 1950), von Neumann and Goldstine (in their monumental 1947 paper Numerical Inverting of Matrices of High Order) and Wittmeyer (1936) used the ratio of largest to smallest eigenvalue of a positive definite matrix in their analyses, which amounts to the 2-norm condition number \kappa_2(A) = \|A\|_2 \|A^{-1}\|_2, though this formula is not used by these authors. Todd called this the P condition number. None of the M, N or P names have stuck.

Nowadays we know that \kappa(A) can be thought of both as a measure of the sensitivity of the solution of a linear system to perturbations in the data and as a measure of the sensitivity of the matrix inverse to perturbations in the matrix (see, for example, Condition Numbers and Their Condition Numbers by D. J. Higham). How to formulate the definition of condition number for a wide class of problems was worked out by John Rice in his 1966 paper A Theory of Condition.

This entry was posted in matrix computations. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s