Condition number
In the numerical analysis with the condition to describe the dependence of the solution of a problem of the perturbation of the input data. The condition number is a measure for this dependency; It describes the factor, by which the input error is amplified in the worst case. It is independent of specific solution methods, but depending on the mathematical problem.
- 4.1 multiplication
- 4.2 addition
Introduction
In the numerical analysis, a distinction between the three variables of a process: condition, stability and consistency, which are mutually closely related. The relationship between the condition of a problem and stability can be modeled as follows:
The mathematical problem it is a function of the input, and it is the numerical algorithm, and the disturbed input data. So one would like to estimate the following error:
By the triangle inequality holds:
This is denoted by the condition of the problem and with stability. One then speaks of the condition property of the problem and stability is the property of the algorithm.
Absolute condition
The absolute condition is defined as
So the absolute condition is exactly the smallest number for which:
Relative condition
The relative condition number is defined as the smallest number with the property: there is a such that for all with the inequality
Applies.
It is the relative change of the feature value and the relative change of the input data. This definition can also be written as
So it follows for a differentiable function in
Derivation of the relative condition number of the Taylor series
Allowed for a function in the Taylor series of higher order terms ignored, the result is
Consequently
This represents the absolute error in the output dar. Dividing by yields immediately the relative output error:
In order to make the relative error in the input on the right side visible, is now even with expanded:
Thus, alone can be seen from the Taylor series, the error amplification by
A good approximation ( higher-order terms have been neglected! ) is described.
Condition of linear maps
The condition of linear mappings can be derived by using the relative condition. If, in the above definition for the function, then:
Thus, the condition of matrices is estimated by the maximum distortion of the unit sphere:
Is the core of the matrix is not trivial, that is it is the zero vector different vectors that are mapped to the zero vector, then. Conversely, one can show that for regular matrices is considered using the natural matrix norm:
Also, can the condition of normal matrices with respect to the spectral norm of the ratio of the largest to the smallest eigenvalue calculate the matrix:
Interpretation and outlook
If the condition number is significantly greater than 1, one speaks of an ill-conditioned problem, otherwise by a well-conditioned problem and is the condition number is infinite, then it is an ill-posed problem.
The importance of the condition is evident when the difference between the real input data ( for example real numbers ) and the actual input data in the form of machine numbers clearly makes itself. There are so a computer program always already corrupted data before. The computer program should now provide a useful result. But if the problem is already ill-conditioned, can not be expected that the algorithm provides useful results it.
If a given problem a bad condition, so it is possible in some cases to rephrase it. How to reach with matrices by skillful row interchange better overall conditions ( this is the condition of the matrix itself is not changed ). The equivalent reformulation of a problem with the aim of improving the condition is called preconditioning. To test numerical methods on matrices with particularly poor condition, the Hilbert matrices are suitable.
In physical problems, the condition is often improved by the fact that the incoming numerical values normalized to readily processable numerical values (ie scaled).
Examples
Multiplication
Multiplication:
The multiplication is given a figure by
The partial derivatives with respect to lead to. This results in the condition of multiplication according to the above formula in the 2- norm
If the sign of is known, you can supplement with a quadratic expression in the form
Bring, from which one can see the magnitude of the condition: Applies, so the multiplication is well-conditioned. At different orders of magnitude of and the condition may, however, be very large: for example, and results.
Addition
Addition:
Addition is given a figure by
For this, we have:
The addition and subtraction is therefore small denominator very ill-conditioned. In this case one speaks of extinction. This occurs with the addition of two approximately equal-sized numbers with different signs - if you want to understand this as a subtraction, then this means the subtraction for numbers of the same sign and approximately the same size.