Condition number

related topics
{math, number, function}
{rate, high, increase}

In the field of numerical analysis, the condition number of a function with respect to an argument measures the asymptotically worst case of how much the function can change in proportion to small changes in the argument. The "function" is the solution of a problem and the "arguments" are the data in the problem. A problem with a low condition number is said to be well-conditioned, while a problem with a high condition number is said to be ill-conditioned. The condition number is a property of the problem. Paired with the problem are any number of algorithms that can be used to solve the problem, that is, to calculate the solution. Some algorithms have a property called backward stability. In general, a backward stable algorithm can be expected to accurately solve well-conditioned problems. Numerical analysis textbooks give formulas for the condition numbers of problems and identify the backward stable algorithms. As a general rule of thumb, if the condition number Îș(A) = 10k, then you lose k digits of accuracy on top of what would be lost to the numerical method due to loss of precision from arithmetic methods.[1]

Contents

Matrices

For example, the condition number associated with the linear equation Ax = b gives a bound on how inaccurate the solution x will be after approximate solution. Note that this is before the effects of round-off error are taken into account; conditioning is a property of the matrix, not the algorithm or floating point accuracy of the computer used to solve the corresponding system. In particular, one should think of the condition number as being (very roughly) the rate at which the solution, x, will change with respect to a change in b. Thus, if the condition number is large, even a small error in b may cause a large error in x. On the other hand, if the condition number is small then the error in x will not be much bigger than the error in b.

The condition number is defined more precisely to be the maximum ratio of the relative error in x divided by the relative error in b.

Let e be the error in b. Assuming that A is a square matrix, the error in the solution A−1b is A−1e. The ratio of the relative error in the solution to the relative error in b is

This is easily transformed to

The maximum value (for nonzero b and e) is easily seen to be the product of the two operator norms:

The same definition is used for any consistent norm. This number arises so often in numerical linear algebra that it is given a name, the condition number of a matrix.

Of course, this definition depends on the choice of norm.

Full article ▸

related documents
Dirichlet's theorem on arithmetic progressions
Infinite set
Most significant bit
Canonical LR parser
Linear prediction
Matrix addition
EXPTIME
Linear span
Constant term
Exponential time
Catalan's conjecture
Unification
Symmetric tensor
Rational root theorem
Sather
Interpreted language
Entire function
Commutative diagram
Single precision
Sum rule in integration
BQP
Atlas (topology)
Hyperplane
Euler number
Genus (mathematics)
Noetherian ring
Cauchy's integral theorem
Nilpotent group
NC (complexity)
Field of fractions