In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument.
[1][2] The condition number is derived from the theory of propagation of uncertainty, and is formally defined as the value of the asymptotic worst-case relative change in output for a relative change in input.
The condition number is frequently applied to questions in linear algebra, in which case the derivative is straightforward but the error could be in many different directions, and is thus computed from the geometry of the matrix.
More generally, condition numbers can be defined for non-linear functions in several variables.
In non-mathematical terms, an ill-conditioned problem is one where, for a small change in the inputs (the independent variables) there is a large change in the answer or dependent variable.
This means that the correct solution/answer to the equation becomes hard to find.
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 known backward stable algorithms.
[3] However, the condition number does not give the exact value of the maximum inaccuracy that may occur in the algorithm.
It generally just bounds it with an estimate (whose computed value depends on the choice of the norm to measure the inaccuracy).
is[clarification needed] and the relative condition number is[clarification needed] For example, the condition number associated with the linear equation Ax = b gives a bound on how inaccurate the solution x will be after approximation.
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.
The ratio of the relative error in the solution to the relative error in b is The maximum value (for nonzero b and e) is then seen to be the product of the two operator norms as follows: The same definition is used for any consistent norm, i.e. one that satisfies When the condition number is exactly one (which can only happen if A is a scalar multiple of a linear isometry), then a solution algorithm can find (in principle, meaning if the algorithm introduces no errors of its own) an approximation of the solution whose precision is no worse than that of the data.
However, it does not mean that the algorithm will converge rapidly to this solution, just that it will not diverge arbitrarily because of inaccuracy on the source data (backward error), provided that the forward error introduced by the algorithm does not diverge as well because of accumulating intermediate rounding errors.
[clarification needed] The condition number may also be infinite, but this implies that the problem is ill-posed (does not possess a unique, well-defined solution for each choice of data; that is, the matrix is not invertible), and no algorithm can be expected to reliably find a solution.
The definition of the condition number depends on the choice of norm, as can be illustrated by two examples.
), then recalling that the eigenvalues of any triangular matrix are simply the diagonal entries.
The condition number computed with this norm is generally larger than the condition number computed relative to the Euclidean norm, but it can be evaluated more easily (and this is often the only practicably computable condition number, when the problem to solve involves a non-linear algebra[clarification needed], for example when approximating irrational and transcendental functions or numbers with numerical methods).
If the condition number is not significantly larger than one, the matrix is well-conditioned, which means that its inverse can be computed with good accuracy.
Practically, such a matrix is almost singular, and the computation of its inverse, or solution of a linear system of equations is prone to large numerical errors.
A matrix that is not invertible is often said to have a condition number equal to infinity.
For square matrices, this unfortunately makes the condition number discontinuous, but it is a useful definition for rectangular matrices, which are never invertible but are still used to define systems of equations.
Condition numbers can also be defined for nonlinear functions, and can be computed using calculus.
in one variable is the absolute value of the derivative of the function: The relative condition number of
, this is Note that this is the absolute value of the elasticity of a function in economics.
Most elegantly, this can be understood as (the absolute value of) the ratio of the logarithmic derivative of
Note that if a function has a zero at a point, its condition number at the point is infinite, as infinitesimal changes in the input can change the output from zero to positive or negative, yielding a ratio with zero in the denominator, hence infinite relative change.
Taking the ratio yields The last term is the difference quotient (the slope of the secant line), and taking the limit yields the derivative.
This is crucial in assessing the sensitivity and potential accuracy difficulties of numerous computational problems, for example, polynomial root finding or computing eigenvalues.
(specifically, its relative condition number[4]) is then defined to be the maximum ratio of the fractional change in