Rate of convergence

Under convergence speed (even convergence order ) is the speed with which the members of a convergent sequence () x are approaching the limit. The term is used in particular in numerical mathematics. It is immediately visible that an iterative numerical method is better when it generates a sequence that against the solution of the given problem converges faster than a method that slowly generates a sequence converging to the solution.

Order of convergence at iteration

We distinguish between linear, super -linear and p-th order convergence.

Linear speed of convergence is present if < 1, a 0 < c, so that

It is superlinear convergence if the sequence converges faster than linear. This occurs, for example, if the above inequality is not only true with a constant c, but even with a zero convergent sequence ( ).

Convergence of order p with p> 1 means that a c > 0 such that

For p = 2 is called quadratic convergence.

The term is especially important in numerical analysis, where an approximation of the limit of an iteration usually done by computing a small number of sequence elements. Convergence of order p then means that in each iteration the number of exact decimal ver - be kindled, so for example, doubled in square convergence.

The faster convergence of higher-order methods are usually paid at a greater expense per iteration, in many cases with worse stability properties.

Examples

Newton's method converges at a simple zero of the second order. Simplified variants of Newton's method converge more slowly, partly superlinear, some with first order.

Fixed point method, for example splitting procedure, have a linear convergence rate. In comparison to the Newton method is an iterative step but much cheaper.

The secant method has a broken order of convergence p = ½ (1 √ 5), it converges superlinearly.

General definition of convergence speed

To describe the convergence speed of a sequence ( ) x converges to the limit, we compare the rate of convergence of the zero sequence with certain other zero sequences for which convergence speed you feel good, such as, for, for 0 < q < 1 or.

It is said that a null sequence () converges at least as fast as a null sequence () if true.

A sequence ( ) is falling rapidly, faster than when each sequence the type (), k is a natural number, falls, that is, for each k ( an example is the result. )

Of particular interest, therefore, the description of the order of convergence of numerical methods in normed spaces, ie where the followers have the shape.

For the purposes of this definition, it is called an iteration linearly convergent if it converges as fast as the sequence ( ) with 0 < q < 1. It is called quadratic convergent if it converges as quickly as the result. Similarly, higher convergence orders can (cubic, superlinear ) define.

Other examples

• Numerical Integration
• Interpolation
• Discretization methods for differential equations
• The central limit theorem of probability theory

• The Fourier coefficients of a C ∞ - function are falling rapidly.

Any slow convergence

Many important numerical methods are arbitrarily slowly convergent. So be a Banach space X and a sequence of n-dimensional subspaces, and let V be a method to each solution of an equation provides an approximate solution. The process V is then called arbitrarily slowly convergent if there is a y for every positive null sequence such that for the corresponding approximate solutions converges slower than the result.

If, for example, in the numerical integration only the continuity of the function to be integrated forward, but not a certain Differenzierbarkeitsordnung, the method of numerical integration is arbitrarily slowly convergent, that is, at any arbitrarily slowly towards zero convergent monotone sequence of positive numbers there exists a continuous function f, so that the sequence of quadrature values ​​against the integral converge slower than the given null sequence. Other examples can be found in the interpolation of the solution or incorrectly posed problems.

Reverse results

In many disciplines, the analysis can be obtained from the speed of convergence insights into the structure of the problem to be investigated. As an example, the amber sets are mentioned from the approximation theory: If a continuous function by polynomials of degree n with the rate of convergence for some a > 0 can be approximated, it is k- times differentiable.

Criticism of the concept

Often one is only interested in a method that quickly () a certain accuracy, for example, IEEE double precision,

Achieved. For this, however, it is secondary whether the procedure for large, for example, linear, quadratic or cubic convergence speed has.