digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

In the field of numerical analysis, the condition number of a function with respect to an argument 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 $f(x) = y,$ one is solving for x, and thus the condition number of the (local) inverse must be used.

The condition number is an application of the derivative, and is formally defined as the absolute 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, 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. 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 $\kappa(A) = 10^k$, then you may lose up to $k$ digits of accuracy on top of what would be lost to the numerical method due to loss of precision from arithmetic methods.[1] 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).

## 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 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. 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

$\frac{ \left\Vert A^{-1} e \right\Vert / \left\Vert A^{-1} b \right\Vert }{ \left\Vert e \right\Vert / \left\Vert b \right\Vert } .$

This is easily transformed to

$\left( \left\Vert A^{-1} e \right\Vert / \left\Vert e \right\Vert \right) \cdot \left( \left\Vert b \right\Vert / \left\Vert A^{-1} b \right\Vert \right) .$

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

$\kappa(A) = \left\Vert A^{-1} \right\Vert \cdot \left\Vert A \right\Vert .$

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

$\kappa(A) \ge 1 .\,$

When the condition number is exactly one, then the algorithm may find an approximation of the solution with an arbitrary precision. However it does not mean that the algorithm will converge rapidly to this solution, just that it won't 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, in which case the algorithm will not reliably find a solution to the problem, not even a weak approximation of it (and not even its order of magnitude) with any reasonable and provable accuracy.

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

• If $\left\| \cdot \right\|$ is the norm (usually noted as $\left\| \cdot \right\|_2$) defined in the square-summable sequence space 2 (which also matches the usual distance in a continuous and isotropic cartesian space), then
$\kappa(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} ,$
where $\sigma_{\max}(A)$ and $\sigma_{\min}(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| ,$
where $\lambda_{\max}(A)$ and $\lambda_{\min}(A)$ are maximal and minimal (by moduli) eigenvalues of $A$ respectively.
• If $A$ is unitary then
$\kappa(A) = 1 .\,$
This number arises so often in numerical linear algebra that it is given a name, the condition number of a matrix.
• If $\left\| \cdot \right\|$ is the norm (usually noted as $\left\| \cdot \right\|_\infty$) defined in the sequence space of all bounded sequences (which also matches the non-linear distance measured as the maximum of distances measured on projections into the base subspaces, without requiring the space to be isotropic or even just linear, but only continuous, such norm being definable on all Banach spaces), and $A$ is lower triangular non-singular (i.e., $\forall i, a_{ii} \ne 0 \,$) then
$\kappa(A) \geq \frac{\max_i(|a_{ii}|)}{\min_i(|a_{ii}|)} .$
The condition number computed with this norm is generally larger than the condition number computed with square-summable sequences, but it can be evaluated more easily (and this is often the only measurable 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 close to one, the matrix is well conditioned which means its inverse can be computed with good accuracy. If the condition number is 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 the condition number equal to infinity.

## Non-linear

Condition numbers can also defined for nonlinear functions, and can be computed using calculus. The condition number varies with the point; in some cases one can use the maximum (or supremum) condition number over the domain 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 f in one variable as a function is $\left|xf'/f\right|.$ Evaluated at a point x this is:

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

Most elegantly, this can be understood as (the absolute value of) the ratio of the logarithmic derivative of f, which is $(\log f)' = f'/f$ and the logarithmic derivative of x, which is $(\log x)' = x'/x = 1/x,$ yielding a ratio of $xf'/f.$ This is because the logarithmic derivative is the infinitesimal rate of relative change in a function: it is the derivative $f'$ scaled by the value of f. 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.

More directly, given a small change $\Delta x$ in x, the relative change in x is $[(x + \Delta x) - x]/x = (\Delta x)/x,$ while the relative change in $f(x)$ is $[f(x + \Delta x) - f(x)]/f(x).$ Taking the ratio yields:

$\frac{[f(x + \Delta x) - f(x)]/f(x)}{(\Delta x)/x} = \frac{x}{f(x)}\frac{f(x + \Delta x) - f(x)}{(x + \Delta x) - x}.$

The last term is the difference quotient (the slope of the secant line), and taking the limit yields the derivative.

Condition numbers of common elementary functions are particularly important in computing significant figures, and can be computed immediately from the derivative; see significance arithmetic of transcendental functions. A few important ones are given below:

• Exponential function $e^x$: $x$
• Natural logarithm function $\ln(x)$: $\frac{1}{\ln(x)}$
• Sine function $\sin(x)$: $x\cot(x)$
• Cosine function $\cos(x)$: $x\tan(x)$
• Tangent function $\tan(x)$: $x(\tan(x)+\cot(x))$
• Inverse sine function $\arcsin(x)$: $\frac{x}{\sqrt{1-x^2}\arcsin(x)}$
• Inverse cosine function $\arccos(x)$: $\frac{x}{\sqrt{1-x^2}\arccos(x)}$
• Inverse tangent function $\arctan(x)$: $\frac{x}{(1+x^2)\arctan(x)}$

### Several variables

Condition numbers can be defined for any function ƒ mapping its data from some domain (e.g. an m-tuple of real numbers x) into some codomain [e.g. an n-tuple of real numbers ƒ(x)], where both the domain and codomain are Banach spaces. 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 eigenvalues.

The condition number of ƒ at a point x (specifically, its relative condition number[2]) is then defined to be the maximum ratio of the fractional change in ƒ(x) to any fractional change in x, in the limit where the change δx in x becomes infinitesimally small:[2]

$\lim_{ \varepsilon \to 0^+ } \sup_{ \Vert \delta x \Vert \leq \varepsilon } \left[ \frac{ \left\Vert f(x + \delta x) - f(x)\right\Vert }{ \Vert f(x) \Vert } / \frac{ \Vert \delta x \Vert }{ \Vert x \Vert } \right],$

where $\Vert \cdots \Vert$ is a norm on the domain/codomain of ƒ(x).

If ƒ is differentiable, this is equivalent to:[2]

$\frac{\Vert J \Vert}{ \Vert f(x) \Vert / \Vert x \Vert},$

where J denotes the Jacobian matrix of partial derivatives of ƒ and $\Vert J \Vert$ is the induced norm on the matrix.

## References

1. ^
2. ^ a b c L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM, 1997).
 1000000 videos foundNext >
 matrix norm and condition number Conversations on Matlab - Chapter 7 - Matrix condition number 1/2Visit http://matlabstart.publonpress.com/ to see all the videos in the right order. This video: A physical problem translated into a matrix in which a specia... Unconstrained Minimization: Theoretical Anlysis- Stopping Criterion & Condition NumberSANJEEV SHARMA: 2nd Dec 2010. CCO-10/11: P-001, Section-2: Unconstrained Minimization: Theoretical Analysis of Stopping Criterion & Condition Number. http://... Extreme Condition - Number OneFourth song of the Extreme EP. Download here: http://www.facebook.com/pages/Extreme-Condition/170242656346503?sk=app_2405167945 Please share too. Conversations on Matlab - Chapter 7 - Matrix condition number 2/2Visit http://matlabstart.publonpress.com/ to see all the videos in the right order. This video: A physical problem translated into a matrix in which a specia... Extreme Condition - Number One (Old Recording)Lyrics: You see the sun Rise in the east I see the dark Consume all light We go together and we'll fight 'till the end of our lives So Ref. What are you wait... Tales Runner Help: Invalid Condition NumberHere is a guide on how to fix the Invalid Condition Error. ---- Go to my info, My missions, select all your missions/quest and press stop. It's that easy! Not really a hard problem. :) The Human Condition & Number 18By JJ Nash and Zack Frey. Victory Condition Series: Number 88: Gimmick Puppet - Destiny Leo (March 12 Format)This video is about Rainycats' destiny leo vc deck, narrated by Faith and RainyCats! Take out one hieratic seal of convocation and it will be sept 12 legal :... Vets baffled by 'robotic cat' condition affecting growing number of petsAnimals take on a rigid 'robot-like' appearance and behave in a confusing way.
 1000000 videos foundNext >
 2 news items
 Report sought on idols made of plaster of Paris Times of India Sun, 19 May 2013 16:33:25 -0700 The NGT observed that the Gujarat government over-stepped its jurisdiction by imposing a total ban on the use of PoP for idol-making (condition number one). The tribunal upheld that the CPCB had only issued guidelines and had not directed the ... FERC Issues Order to Transcontinental Gas Pipe Line Company, LLC Northeast ... Utility Products Fri, 03 May 2013 20:20:11 -0700 In considering this notice to proceed, we have determined that Transco's requests, as supplemented, includes the information necessary to meet Environmental Condition Number 5 of the Commission's November 2, 2012 Order Issuing Certificate (Order).
 Limit to books that you can completely read online Include partial books (book previews) .gsc-branding { display:block; }

Oops, we seem to be having trouble contacting Twitter