In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, the condition number of a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
measures how much the output value of the function can change for a small change in the input argument. This is used to measure how
sensitive a function is to changes or errors in the input, and how much error in the output results from an error in the input. Very frequently, one is solving the inverse problem: given
one is solving for ''x,'' and thus the condition number of the (local) inverse must be used. In
linear regression
In statistics, linear regression is a linear approach for modelling the relationship between a scalar response and one or more explanatory variables (also known as dependent and independent variables). The case of one explanatory variable is call ...
the condition number of the
moment matrix
In mathematics, a moment matrix is a special symmetric square matrix whose rows and columns are indexed by monomials. The entries of the matrix depend on the product of the indexing monomials only (cf. Hankel matrices.)
Moment matrices play an im ...
can be used as a diagnostic for
multicollinearity
In statistics, multicollinearity (also collinearity) is a phenomenon in which one predictor variable in a multiple regression model can be linearly predicted from the others with a substantial degree of accuracy. In this situation, the coeffic ...
.
The condition number is an application of the
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. F ...
, and is formally defined as the value of the asymptotic worst-case relative change in output for a relative change in input. The "function" is the solution of a problem and the "arguments" are the data in the problem. The condition number is frequently applied to questions in
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
, 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.
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. In non-mathematical terms, an ill-conditioned problem is one where, for a small change in the inputs (the
independent variables
Dependent and independent variables are variables in mathematical modeling, statistical modeling and experimental sciences. Dependent variables receive this name because, in an experiment, their values are studied under the supposition or deman ...
) there is a large change in the answer or
dependent variable
Dependent and independent variables are variables in mathematical modeling, statistical modeling and experimental sciences. Dependent variables receive this name because, in an experiment, their values are studied under the supposition or demand ...
. This means that the correct solution/answer to the equation becomes hard to find. 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 known backward stable algorithms.
As a rule of thumb, if the condition number
, then you may lose up to
digits of accuracy on top of what would be lost to the numerical method due to loss of precision from arithmetic methods.
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).
General definition in the context of error analysis
Given a problem
and an algorithm
with an input
and output
the ''error'' is
the
''absolute'' error is
and the
''relative'' error is
In this context, the ''absolute'' condition number of a problem
is
:
and the ''relative'' condition number is
:
Matrices
For example, the condition number associated with the
linear equation
In mathematics, a linear equation is an equation that may be put in the form
a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coefficien ...
''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
A roundoff error, also called rounding error, is the difference between the result produced by a given algorithm using exact arithmetic and the result produced by the same algorithm using finite-precision, rounded arithmetic. Rounding errors are d ...
are taken into account; conditioning is a property of the
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
, not the
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
or
floating-point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can b ...
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
The approximation error in a data value is the discrepancy between an exact value and some '' approximation'' to it. This error can be expressed as an absolute error (the numerical amount of the discrepancy) or as a relative error (the absolute e ...
in ''x'' to the relative error in ''b''.
Let ''e'' be the error in ''b''. Assuming that ''A'' is a
nonsingular
In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that
:\mathbf = \mathbf = \mathbf_n \
where denotes the -by- identity matrix and the multiplica ...
matrix, the error in the solution ''A''
−1''b'' is ''A''
−1''e''. 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 norm
In mathematics, the operator norm measures the "size" of certain linear operators by assigning each a real number called its . Formally, it is a norm defined on the space of bounded linear operators between two given normed vector spaces.
Introdu ...
s as follows:
:
The same definition is used for any consistent
norm
Naturally occurring radioactive materials (NORM) and technologically enhanced naturally occurring radioactive materials (TENORM) consist of materials, usually industrial wastes or by-products enriched with radioactive elements found in the envi ...
, 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.
The condition number may also be infinite, but this implies that the problem is
ill-posed
The mathematical term well-posed problem stems from a definition given by 20th-century French mathematician Jacques Hadamard. He believed that mathematical models of physical phenomena should have the properties that:
# a solution exists,
# the sol ...
(does not possess a unique, well-defined solution for each choice of data; that is, the matrix is not
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
), 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.
If
is the
matrix norm induced by the (vector) Euclidean norm (sometimes known as the ''L''
2 norm and typically denoted as
), then
:
where
and
are maximal and minimal
singular value In mathematics, in particular functional analysis, the singular values, or ''s''-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self ...
s of
respectively. Hence:
* If
is
normal Normal(s) or The Normal(s) may refer to:
Film and television
* ''Normal'' (2003 film), starring Jessica Lange and Tom Wilkinson
* ''Normal'' (2007 film), starring Carrie-Anne Moss, Kevin Zegers, Callum Keith Rennie, and Andrew Airlie
* ''Norma ...
, then
where
and
are maximal and minimal (by moduli)
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s of
respectively.
* If
is
unitary
Unitary may refer to:
Mathematics
* Unitary divisor
* Unitary element
* Unitary group
* Unitary matrix
* Unitary morphism
* Unitary operator
* Unitary transformation
* Unitary representation
* Unitarity (physics)
* ''E''-unitary inverse semigrou ...
, then
The condition number with respect to ''L''
2 arises so often in
numerical linear algebra
Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to questions in continuous mathematic ...
that it is given a name, the condition number of a matrix.
If
is the
matrix norm induced by the (vector) norm and
is
lower triangular
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
non-singular (i.e.
for all
), 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'', 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. If the condition number is very large, then the matrix is said to be ill-conditioned. 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 has condition number equal to infinity.
Nonlinear
Condition numbers can also be defined for nonlinear functions, and can be computed using
calculus
Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithm ...
. The condition number varies with the point; in some cases one can use the maximum (or
supremum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
) condition number over the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
of the function or domain of the question as an overall condition number, while in other cases the condition number at a particular point is of more interest.
One variable
The condition number of a
differentiable function
In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in its ...
in one variable as a function is
. Evaluated at a point
, this is
:
Most elegantly, this can be understood as (the
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
of) the ratio of the
logarithmic derivative
In mathematics, specifically in calculus and complex analysis, the logarithmic derivative of a function ''f'' is defined by the formula
\frac
where f' is the derivative of ''f''. Intuitively, this is the infinitesimal relative change in ''f'' ...
of
, which is
, and the logarithmic derivative of
, which is
, yielding a ratio of
. This is because the logarithmic derivative is the infinitesimal rate of relative change in a function: it is the derivative
scaled by the value of
. Note that if a function has a
zero
0 (zero) is a number representing an empty quantity. In place-value notation
Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or ...
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.
More directly, given a small change
in
, the relative change in
is
, while the relative change in
is
. Taking the ratio yields
:
The last term is the
difference quotient
In single-variable calculus, the difference quotient is usually the name for the expression
: \frac
which when taken to the limit as ''h'' approaches 0 gives the derivative of the function ''f''. The name of the expression stems from the fact ...
(the slope of the
secant line
Secant is a term in mathematics derived from the Latin ''secare'' ("to cut"). It may refer to:
* a secant line, in geometry
* the secant variety, in algebraic geometry
* secant (trigonometry) (Latin: secans), the multiplicative inverse (or recipr ...
), and taking the
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
yields the derivative.
Condition numbers of common
elementary function
In mathematics, an elementary function is a function of a single variable (typically real or complex) that is defined as taking sums, products, roots and compositions of finitely many polynomial, rational, trigonometric, hyperbolic, and exponen ...
s are particularly important in computing
significant figures
Significant figures (also known as the significant digits, ''precision'' or ''resolution'') of a number in positional notation are digits in the number that are reliable and necessary to indicate the quantity of something.
If a number expre ...
and can be computed immediately from the derivative; see
significance arithmetic of transcendental functions. A few important ones are given below:
Several variables
Condition numbers can be defined for any function
mapping its data from some
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
(e.g. an
-tuple of
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s
) into some
codomain
In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either the ...
(e.g. an
-tuple of real numbers
), where both the domain and codomain are
Banach space
In mathematics, more specifically in functional analysis, a Banach space (pronounced ) is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vector ...
s. They express how sensitive that function is to small changes (or small errors) in its arguments. This is crucial in assessing the sensitivity and potential accuracy difficulties of numerous computational problems, for example,
polynomial root finding or computing
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s.
The condition number of
at a point
(specifically, its relative condition number
) is then defined to be the maximum ratio of the fractional change in
to any fractional change in
, in the limit where the change
in
becomes infinitesimally small:
:
where
is a
norm
Naturally occurring radioactive materials (NORM) and technologically enhanced naturally occurring radioactive materials (TENORM) consist of materials, usually industrial wastes or by-products enriched with radioactive elements found in the envi ...
on the domain/codomain of
.
If
is differentiable, this is equivalent to:
:
where denotes the
Jacobian matrix
In vector calculus, the Jacobian matrix (, ) of a vector-valued function of several variables is the matrix of all its first-order partial derivatives. When this matrix is square, that is, when the function takes the same number of variables as ...
of
partial derivative
In mathematics, a partial derivative of a function of several variables is its derivative with respect to one of those variables, with the others held constant (as opposed to the total derivative, in which all variables are allowed to vary). Part ...
s of
at
, and
is the
induced norm on the matrix.
See also
*
Numerical methods for linear least squares
*
Hilbert matrix In linear algebra, a Hilbert matrix, introduced by , is a square matrix with entries being the unit fractions
: H_ = \frac.
For example, this is the 5 × 5 Hilbert matrix:
: H = \begin
1 & \frac & \frac & \frac & \frac \\
\frac & \frac & \f ...
*
Ill-posed problem
The mathematical term well-posed problem stems from a definition given by 20th-century French mathematician Jacques Hadamard. He believed that mathematical models of physical phenomena should have the properties that:
# a solution exists,
# the sol ...
*
Singular value In mathematics, in particular functional analysis, the singular values, or ''s''-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self ...
*
Wilson matrix Wilson matrix is the following 4\times 4 matrix having integers as elements:
::W = \begin5&7&6&5 \\ 7&10&8&7 \\ 6&8&10&9 \\ 5&7&9&10\end
This is the coefficient matrix of the following system of linear equations considered in a paper by J. Morris ...
References
Further reading
* {{cite book , first=James , last=Demmel , author-link=James Demmel , chapter=Nearest Defective Matrices and the Geometry of Ill-conditioning , pages=35–55 , title=Reliable Numerical Computation , editor-first=M. G. , editor-last=Cox , editor2-first=S. , editor2-last=Hammarling , location=Oxford , publisher=Clarendon Press , year=1990 , isbn=0-19-853564-3
External links
Condition Number of a Matrixat ''Holistic Numerical Methods Institute''
Condition number – Encyclopedia of MathematicsWho Invented the Matrix Condition Number? by Nick Higham
Numerical analysis
Matrices