Ill-Conditioned & Condition Number

A mathematical problem or series of equations is ill-conditioned if a small change in input leads to a large change in the output. This can lead to several issues with calculations. For example, if you have an ill-conditioned system of equations, the solution might exist, but it can be difficult to find.

Well-conditioning is one of the requirements for well-posed problems. Therefore, an ill-conditioned problem is defined as ill-posed.

Examples of Ill-Conditioned Problems

One example of an ill-conditioned function is a high-order polynomial function like:

f(x) = (x – 1)(x – 2)…(x – 20) = x20 – 210x19 + … + 20!.

This particular polynomial is called the Wilkinson Polynomial, after Wilkinson who studied it in 1959. On first glance it looks simple, and it is easy to solve. But it’s still  ill conditioned. We can see this best by expanding the polynomial, or multiplying out all twenty terms.

Multiplied out, Wilkinson’s polynomial becomes

f(x)= x20 – 210x19 + 20,615x18 – 1,256,850x17 + 53,327,946x16 – 1,672,280,820x15 + 40,171,771,630x14 – 756,111,184,500x13 + 11,310,276,995,381x12 – 135,585,182,899,530x11 + 1,307,535,010,540,395x10 – 10,142,299,865,511,450x9 + 63,030,812,099,294,896x8 – 311,333,643,161,390,640x7 + 1,206,647,803,780,373,360x6 – 3,599,979,517,947,607,200x5 + 8,037,811,822,645,051,776x4 – 12,870,931,245,150,988,800x3 + 13,803,759,753,640,704,000x2 – 8,752,948,036,761,600,000x1 + 2,432,902,008,176,640,000 = 0.

In the above expansion, the coefficient of x19 is 210. If we change this coefficient by a very small amount—say, 2-23, or 0.00000000000000000000002—the value of the polynomial f(20) will change by a very large amount. Evaluated at 20, it was 0. With the tiny change in our x19 coefficient—a change that is much smaller than any significant figures we’d have been using in our measurements—it’ll become -6.25 x 1017, or -625000000000000000.

So Wilkinson’s polynomial is ill-conditioned. The condition number has actually been calculated out to be around 5.1 x 1013.

Condition Numbers and Ill-Conditioned

If a problem is ill conditioned, then the condition number—a function itself— is large. There isn’t a simple definition of what counts as ‘small’ and ‘large’, although in matrix algebra too large is if log(c) ≳ the precision of matrix entries. Additionally, systems with infinite condition numbers are singular.

We can’t always calculate the condition number directly, but it can be defined relatively simply. The condition number is the ratio of the change in output for a change in input in the ‘worst-case’—that is to say, at the point when the change in output is largest per given change in input.

If a function is differentiable and in just one variable, the condition number can be calculated from the derivative and is given by (xf′)/f. So the condition number of ex will be x, and can be as large as the range of x. The condition number of ln(x) for every point x is 1/ln(x).

All the condition number tells us is how much precision or accuracy is lost (by arithmetic methods) when we calculate values based on the function. If a function has condition number x, the loss of accuracy is bounded by approximately log10x.

If the loss of accuracy represented by the condition number is high enough to mess up calculations, a problem is ill-conditioned. This might be the point at which you lose so many significant digits your problem is no longer worth doing.

FNC 1.2: Condition numbers

Other forms of Condition Numbers

The condition number is found in many places including computer science, matrix algebra, and calculus. The definitions for the different condition numbers are very situation specific. For example, a common form of a condition number is found in matrix algebra, where it describes a matrix associated with a system of linear equations. In this case, the coefficient matrix describes the condition number.

On the other hand, the condition number for roots based on a derivative is defined by the equation:
1/f′(x0.
According to Gentle (2010), this “must be used with care, because—used incorrectly—it can be misleading”; This particular definition describes Wilkinson’s polynomial as well-conditioned, which is clearly not the case.

References

Baum, C. et al. (2006). An Introduction to Modern Econometrics Using Stata. Stata Press.
Ueberhuber, C. (1997). Numerical Computation 1: Methods, Software, and Analysis. Springer Science & Business Media.
Computational Statistics
Stability and Conditioning


Comments? Need to post a correction? Please Contact Us.