Editing Condition number (section)

== Matrices ==<!-- This section is linked from [[Invertible matrix]] -->

For example, the condition number associated with the [[linear equation]]
''Ax''&nbsp;=&nbsp;''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 (mathematics)|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'' to the relative error in ''b''.

Let ''e'' be the error in ''b''. Assuming that ''A'' is a [[nonsingular matrix|nonsingular]] matrix, the error in the solution ''A''<sup>−1</sup>''b'' is ''A''<sup>−1</sup>''e''. The ratio of the relative error in the solution to the relative error in ''b'' is

: <math>{\frac{\left\|A^{-1} e\right\|}{\left\|A^{-1} b\right\|}}/{\frac{\|e\|}{\|b\|}} = \frac{\left\|A^{-1} e\right\|}{\|e\|} \frac{\|b\|}{\left\|A^{-1} b\right\|}.</math>

The maximum value (for nonzero ''b'' and ''e'') is then seen to be the product of the two [[operator norm]]s as follows:

:<math>\begin{align}
  \max_{e,b \neq 0} \left\{ \frac{\left\| A^{-1}e \right\|}{\| e \|} \frac{\| b \|}{\left\| A^{-1}b \right\|} \right\}
    &= \max_{e \neq 0} \left\{\frac{\left\| A^{-1}e\right\| }{\| e\|} \right\} \, \max_{b \neq 0} \left\{ \frac {\| b \|}{\left\| A^{-1}b \right\|} \right\} \\
    &= \max_{e \neq 0} \left\{\frac{\left\| A^{-1}e\right\|}{\| e \|}\right\} \, \max_{x \neq 0} \left \{\frac {\| Ax \| }{\| x \|} \right\} \\
    &= \left\| A^{-1} \right \| \, \|A\|.
\end{align}</math>

The same definition is used for any consistent [[matrix norm|norm]], i.e. one that satisfies

: <math>\kappa(A) = \left\| A^{-1} \right\| \, \left\| A \right\| \ge \left\| A^{-1} A \right\| = 1.</math>

When the condition number is exactly one (which can only happen if ''A'' is a scalar multiple of a [[Isometry#Linear isometry|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.{{clarify|date=October 2014}}

The condition number may also be infinite, but this implies that the problem is [[well-posed problem|ill-posed]] (does not possess a unique, well-defined solution for each choice of data; that is, the matrix is not [[invertible matrix|invertible]]), and no algorithm can be expected to reliably find a solution.

The definition of the condition number depends on the choice of [[Norm (mathematics)|norm]], as can be illustrated by two examples.

If <math>\|\cdot\|</math> is the [[Matrix norm#Matrix norms induced by vector norms|matrix norm induced by the (vector) Euclidean norm]] (sometimes known as the ''L''<sup>2</sup> norm and typically denoted as <math>\|\cdot\|_2</math>), then

: <math>\kappa(A) = \frac{\sigma_\text{max}(A)}{\sigma_\text{min}(A)},</math>

where <math>\sigma_\text{max}(A)</math> and <math>\sigma_\text{min}(A)</math> are maximal and minimal [[singular value]]s of <math>A</math> respectively. Hence:

* If <math>A</math> is [[normal matrix|normal]], then <math display="block">\kappa(A) = \frac{\max\{\left|\lambda(A)\right|\}}{\min\{\left|\lambda(A)\right|\}},</math> where <math>\lambda_\text{max}(A)</math> and <math>\lambda_\text{min}(A) </math> are maximal and minimal (by moduli) [[eigenvalue]]s of <math>A</math> respectively.
* If <math>A</math> is [[unitary matrix|unitary]], then <math>\kappa(A) = 1.</math>

The condition number with respect to ''L''<sup>2</sup> arises so often in [[numerical linear algebra]] that it is given a name, the '''condition number of a matrix'''.

If <math>\|\cdot\|</math> is the [[Matrix norm#Matrix norms induced by vector norms|matrix norm induced by the  <math>L^\infty</math> (vector) norm]] and <math>A</math> is [[triangular matrix|lower triangular]] non-singular (i.e. <math>a_{ii} \ne 0</math> for all <math>i</math>), then

: <math>\kappa(A) \geq \frac{\max_i\big(|a_{ii}|\big)}{\min_i\big(|a_{ii}|\big)}</math>

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''{{what?|date=October 2014}}, for example when approximating irrational and [[transcendental function|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 is often said to have a condition number equal to infinity.  Alternatively, it can be defined as <math>\kappa(A) = \|A\| \|A^\dagger\|</math>, where <math>A^\dagger</math> is the Moore-Penrose [[pseudoinverse]].  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.