Calculus How To

Ill-Conditioned & Condition Number

Share on

Calculus Definitions >

A mathematical problem or series of equations is ill-conditioned if a small change in input (e.g. the independent variable X, input vector or regression input) leads to a large change in the output (e.g.the dependent variable, solution vector or regression estimates).

This can lead to several issues with computations. 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.

Condition Numbers and Ill-Conditioned

The condition number of a function can help to make the concept of ill-conditioning a little more concrete.

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 function 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

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

CITE THIS AS:
Stephanie Glen. "Ill-Conditioned & Condition Number" From CalculusHowTo.com: Calculus for the rest of us! https://www.calculushowto.com/ill-conditioned/
------------------------------------------------------------------------------

Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!