# Ill-Conditioned

A mathematical problem or series of equations is ill-conditioned if a small change in the independent variable (input) leads to a large change in the dependent variable (output). This can lead to computational problems. For example, if a system of equations is ill-conditioned, the solution exists, but it if very difficult to find.

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

## Condition Numbers and Ill Conditioning

To make the concept of ill-conditioning concrete we can look at the condition number of a function. A function is simply the relationship between variables. It’s a way to map from one set of data (the input, or independent variable) to another (the output, or dependent variable). For the relationship to be considered a function, every bit of input data gets exactly one output.

Imagine your function graphed, with the independent variable on one axis and the dependent variable on the other. The condition number tells us how steep the slope of a function is at its steepest point.

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

## Quantifying Ill-Condition

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

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.

## Examples of Ill-Conditioned Problems

One example of an ill-conditioned function is a high-order polynomial like f(x)= (x-1)(x-2)…(x-20)= x20-210x19+…+20!. This 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.

## Other forms of Condition Numbers

The condition number is found in many places including computational 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.

## Sources

Ill-conditioning and multicollinearity

Ill Conditioned Systems

Computational Statistics

Stability and Conditioning

------------------------------------------------------------------------------

If you prefer an online interactive environment to learn R and statistics, this free R Tutorial by Datacamp is a great way to get started. If you're are somewhat comfortable with R and are interested in going deeper into Statistics, try this Statistics with R track.