NationMaster - Encyclopedia: Condition number

In numerical analysis, the condition number associated with a numerical problem is a measure of that quantity's amenability to digital computation, that is, how well-posed the problem is. 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. Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ... The mathematical term well-posed problem stems from a definition given by Hadamard. ...

The condition number of a matrix

For example, the condition number associated with the linear equation $A x = b$ gives a bound on how inaccurate the solution $x$ will be after numerical solution.

The condition number also amplifies the error present in $b$ . The extent of this amplification can render a low condition number system (normally a good thing) inaccurate and a high condition number system (normally a bad thing) accurate, depending on how well the data in $b$ are known. For this problem, the condition number is defined by

$Vert A^{-1}Vert cdot Vert AVert$ ,

in any consistent norm. This number arises so often in numerical linear algebra that it is given a name, the condition number of a matrix: In mathematics, the term matrix norm can have two meanings: A vector norm on matrices, i. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear transformations, and systems of linear equations in finite dimensions. ...

$kappa (A) = Vert A^{-1}Vert cdot Vert AVert.$

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

If $|cdot|$ is $l 2$ norm then

$kappa(A) = frac{sigma_{max}(A)}{sigma_{min}(A)}$ where

σ m a x (A)

and

σ m i n (A)

are maximal and minimal singular values of

A

respectively. Hence

If $A$ is normal then

$kappa(A) = left|frac{lambda_{max}(A)}{lambda_{min}(A)}right|$ ( $lambda_{max}(A), lambda_{min}(A)$ are maximal and minimal (by moduli) eigenvalues of

A

respectively)

If $A$ is unitary then

κ(A) = 1

If $|cdot|$ is $l_{infty}$ norm and $A$ is lower triangular non-singular (i.e., $a_{ii} ne 0 ; forall i$ ) then

$kappa(A) geq frac{max_i(|a_{ii}|)}{min_i(|a_{ii}|)}$

In mathematics, the term matrix norm can have two meanings: A vector norm on matrices, i. ... In mathematics, in particular functional analysis, singular values, or s-numbers of an bounded operator T acting on a Hilbert space are defined as the eigenvalues of (T*T)1/2. ... A complex square matrix A is a normal matrix iff where A* is the conjugate transpose of A (if A is a real matrix, this is the same as the transpose of A). ... In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ... In mathematics, a unitary matrix is an n by n complex matrix U satisfying the condition where In is the identity matrix and U* is the conjugate transpose (also called the Hermitian adjoint) of U. Note this condition says that a matrix U is unitary if it has an inverse... In mathematics, the term matrix norm can have two meanings: A vector norm on matrices, i. ... In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero. ...

The condition number in other contexts

Condition numbers for singular-value decompositions, polynomial root finding, eigenvalue and many other problems may be defined. In linear algebra the singular value decomposition (SVD) is a factorization of a rectangular real or complex matrix analogous to the diagonalization of symmetric or Hermitian square matrices using a basis of eigenvectors (see spectral theorem). ... In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...

Generally, if a numerical problem is well-posed, it can be expressed as a function $f$ mapping its data, which is an $m$ -tuple of real numbers $x$ , into its solution, an $n$ -tuple of real numbers $y$ .

Its condition number is then defined to be the maximum value of the ratio of the relative errors in the solution to the relative error in the data, over the problem domain: In the mathematical subfield of numerical analysis the approximation error in some data is the discrepancy between an exact value and some approximation to it. ... In the mathematical subfield of numerical analysis the approximation error in some data is the difference between the exact value and the value used. ...

$max left{ left| frac{f(x) - f(x^*)}{f(x)} right| left/ left| frac{x - x^*}{x} right| right. : |x - x^*| < epsilon right}$

where $ε$ is some reasonably small value in the variation of data for the problem.

If $f$ is also differentiable, this is approximately

$left| frac{ f'(x) }{ f(x) } right|. left| x right|$ .

Category: Numerical analysis

Results from FactBites:

Condition number - Wikipedia, the free encyclopedia (349 words)
	In numerical analysis, the condition number associated with a numerical problem is a measure of that quantity's amenability to digital computation, that is, how well-posed the problem is. 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.
	Condition numbers for singular-value decompositions, polynomial root finding, eigenvalue and many other problems may be defined.
	Its condition number is then defined to be the maximum value of the ratio of the relative errors in the solution to the relative error in the data, over the problem domain:

PlanetMath: matrix condition number (160 words)
	The condition number is a measure of stability or sensitivity of a matrix (or the linear system it represents) to numerical operations.
	Matrices with condition numbers near 1 are said to be well-conditioned.
	This is version 5 of matrix condition number, born on 2002-09-28, modified 2005-08-29.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

The condition number of a matrix GA_googleFillSlot("encyclopedia_square");

The condition number in other contexts

The condition number of a matrix