Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Rate of convergence
Summary
In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence that converges to is said to have order of convergence and rate of convergence if
The rate of convergence is also called the asymptotic error constant.
Note that this terminology is not standardized and some authors will use rate where
this article uses order (e.g., ).
In practice, the rate and order of convergence provide useful insights when using iterative methods for calculating numerical approximations. If the order of convergence is higher, then typically fewer iterations are necessary to yield a useful approximation. Strictly speaking, however, the asymptotic behavior of a sequence does not give conclusive information about any finite part of the sequence.
Similar concepts are used for discretization methods. The solution of the discretized problem converges to the solution of the continuous problem as the grid size goes to zero, and the speed of convergence is one of the factors of the efficiency of the method. However, the terminology, in this case, is different from the terminology for iterative methods.
Series acceleration is a collection of techniques for improving the rate of convergence of a series discretization. Such acceleration is commonly accomplished with sequence transformations.
Suppose that the sequence converges to the number . The sequence is said to converge with order to , and with a rate of convergence of , iffor some positive constant if , and if . It is not necessary, however, that be an integer. For example, the secant method, when converging to a regular, simple root, has an order of φ ≈ 1.618.
Convergence with order
is called linear convergence if , and the sequence is said to converge Q-linearly to .
is called quadratic convergence.
is called cubic convergence.
etc.
A practical method to calculate the order of convergence for a sequence is to calculate the following sequence, which converges to :
In addition to the previously defined Q-linear convergence, a few other Q-convergence definitions exist.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (10)
Series acceleration
In mathematics, series acceleration is one of a collection of sequence transformations for improving the rate of convergence of a series. Techniques for series acceleration are often applied in numerical analysis, where they are used to improve the speed of numerical integration. Series acceleration techniques may also be used, for example, to obtain a variety of identities on special functions. Thus, the Euler transform applied to the hypergeometric series gives some of the classic, well-known hypergeometric series identities.
Rate of convergence
In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence that converges to is said to have order of convergence and rate of convergence if The rate of convergence is also called the asymptotic error constant. Note that this terminology is not standardized and some authors will use rate where this article uses order (e.g., ).
Shanks transformation
In numerical analysis, the Shanks transformation is a non-linear series acceleration method to increase the rate of convergence of a sequence. This method is named after Daniel Shanks, who rediscovered this sequence transformation in 1955. It was first derived and published by R. Schmidt in 1941. For a sequence the series is to be determined. First, the partial sum is defined as: and forms a new sequence .
Related courses (34)
MATH-101(g): Analysis I
Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.
MATH-100(a): Advanced analysis I
Nous étudions les concepts fondamentaux de l'analyse, le calcul différentiel et intégral de fonctions réelles d'une variable.
EE-556: Mathematics of data: from theory to computation
This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees
Related MOOCs (9)
Analyse I
Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond
Analyse I (partie 1) : Prélude, notions de base, les nombres réels
Concepts de base de l'analyse réelle et introduction aux nombres réels.
Analyse I (partie 2) : Introduction aux nombres complexes
Introduction aux nombres complexes