Fitness (mathematics)

from Wikipedia, the free encyclopedia

In numerical mathematics , the condition describes the dependence of the solution to a problem on the disturbance of the input data. The condition number is a measure of 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 depends on the mathematical problem.

introduction

In numerics, a distinction is made between the three parameters of a procedure: condition, stability and consistency , which are closely related to each other. The relationship between the condition of a problem and the consistency of the algorithm can be modeled as follows:

Let it be the mathematical problem as a function of the input , and it is the numerical algorithm and the perturbed input data. So one would like to estimate the following error - also known as convergence:

.

With the triangle inequality :

Here, one denotes the condition of the problem and the consistency of the algorithm.

Absolute fitness

The absolute condition of  at the point  is defined as

So the absolute condition is exactly the smallest number for which the following applies:

Relative condition

The relative condition of  at the point  is defined as the smallest number with the property: There is a , so that for all with the inequality

applies.

Here is the relative change in the function value and the relative change in the input data. This definition can also be written as

. If it is differentiable at this point , then it follows
.

It is the Jacobian matrix of at the location and the standard one used with the vector norm acceptable matrix norm .

Derivation of the relative condition number from the Taylor series

If one disregards terms of higher order for a function in the Taylor series , the result is

,

consequently

Here represents the absolute error in the output. Division by immediately results in the relative output error :

In order to make the relative error in the input visible on the right side, it is now extended with :

It can thus be seen from the Taylor series alone that the error amplification by

is described in good approximation (terms of higher order were neglected!).

Condition of linear mappings and systems of linear equations

Linear systems of equations often appear in numerics and therefore one would like to be able to determine the condition of these well. Different special cases can be considered individually.

Invertible matrix

For invertible the (relative) condition is defined as:

wherein the condition of the selected matrix norm is dependent, thus: .

Disorder in the right side

Let be the exact solution of and an approximate solution for a disturbed right side , so:

Now you can define the error and the error in the image space ( residual ) :

The following bounds can now be given for the relative error :

Malfunction in the matrix

Let be the exact solution of and an approximate solution for a perturbed coefficient matrix , thus:

Now one can only develop the relative error according to the orders in . The estimate is:

Full rank matrix

For with and full rank :

so one defines the condition as:

This can be deduced from the following consideration: if one enters the above definition of the relative condition of the function , then the following applies:

.

Thus the condition of matrices is the greatest possible distortion of the unit sphere .

In addition, the condition of normal matrices with regard to the spectral norm can be calculated from the ratio of the absolute largest to the smallest eigenvalue of the matrix:

Any matrix

For any with one defines the condition by means of the pseudo inverse as:

Note: Frequently determining the pseudoinverse means of the singular value decomposition of , as: . The definition of can be found in the calculation of the pseudo inverse .

Examples

An example often given for a badly conditioned matrix is ​​the Hilbert matrix . Your condition grows strongly with the dimension:

One cannot therefore expect that the linear system of equations can be solved well for (for large).

Interpretation and outlook

If the condition number is significantly greater than 1, one speaks of a badly conditioned problem , otherwise it is a well-conditioned problem , and if the condition number is infinite, then it is a badly posed problem .

The meaning of the condition becomes clear when one realizes the difference between the real input values ​​(for example real numbers) and the actual input data in the form of machine numbers. A computer program therefore always has falsified values ​​as data. The computer program should now provide a usable result. However, if the problem is already ill-conditioned, one cannot expect the algorithm to produce useful results.

If a given problem is in poor condition, it is possible in some cases to rephrase it. In this way, a better overall condition can be achieved with matrices by cleverly interchanging lines (the condition of the matrix itself is not changed here). The equivalent reformulation of a problem with the aim of improving condition is called preconditioning . The Hilbert matrices are suitable for testing numerical methods on matrices with particularly poor condition .

In the case of physical problems, the condition is often improved by the fact that the incoming numerical values ​​are normalized ( i.e. scaled ) to easily processable numerical values .

Examples

multiplication

Multiplication :

The multiplication is given by a map

.

The partial derivatives after , lead to . This results in the condition of the multiplication according to the above formula in the Euclidean norm

If the sign of is known, you can add a square to the expression in the form

from which one can read off the order of magnitude of the condition: If it is true , the multiplication is well conditioned. With different orders of magnitude of and , however, the condition can become very great: For example, for and results . This effect results from the use of the standard for measuring the disturbances, because a small relative disturbance of can correspond to a large relative disturbance of the very small value . A component-wise condition analysis, however, shows that the multiplication is always well conditioned.

addition

Addition :

The addition is given by a map

.

For this, the sum standard results in :

The addition, like the subtraction, is therefore very poorly conditioned for small denominators . In this case one speaks of extinction . This occurs when adding two numbers of roughly the same size with different signs - if you want to understand this as subtraction, then this means the subtraction of numbers with the same sign and roughly the same size.

literature

Individual evidence

  1. ^ Peter Deuflhard, Andreas Hohmann: Numerical Mathematics 1 . 4th edition. Walter de Gruyter, Berlin 2008, ISBN 978-3-11-020354-7 , p. 39 .