Speed of convergence of a mathematical sequence
In mathematical analysis, particularly numerical analysis, the rate of convergence and order of convergence of a sequence that converges to a limit are any of several characterizations of how quickly that sequence approaches its limit. These are broadly divided into rates and orders of convergence that describe how quickly a sequence further approaches its limit once it is already close to it, called asymptotic rates and orders of convergence, and those that describe how quickly sequences approach their limits from starting points that are not necessarily close to their limits, called non-asymptotic rates and orders of convergence. 
Asymptotic behavior is particularly useful for deciding when to stop a sequence of numerical computations, for instance once a target precision has been reached with an iterative root-finding algorithm, but pre-asymptotic behavior is often crucial for determining whether to begin a sequence of computations at all, since it may be impossible or impractical to ever reach a target precision with a poorly chosen approach. Asymptotic rates and orders of convergence are the focus of this article. 
In practical numerical computations, asymptotic rates and orders of convergence follow two common conventions for two types of sequences: the first for sequences of iterations of an iterative numerical method and the second for sequences of successively more accurate numerical discretizations of a target. In formal mathematics, rates of convergence and orders of convergence are often described comparatively using asymptotic notation commonly called "big O notation," which can be used to encompass both of the prior conventions; this is an application of asymptotic analysis. 
For iterative methods, a sequence formula_1 that converges to formula_2 is said to have asymptotic "order of convergence" formula_3 and asymptotic "rate of convergence" formula_4 if 
formula_5
Where methodological precision is required, these rates and orders of convergence are known specifically as the rates and orders of Q-convergence, short for quotient-convergence, since the limit in question is a quotient of error terms. The rate of convergence formula_4 may also be called the "asymptotic error constant", and some authors will use "rate" where this article uses "order." Series acceleration methods are techniques for improving the rate of convergence of the sequence of partial sums of a series and possibly its order of convergence, also. 
Similar concepts are used for sequences of discretizations. For instance, ideally the solution of a differential equation discretized via a regular grid will converge to the solution of the continuous equation as the grid spacing goes to zero, and if so the asymptotic rate and order of that convergence are important properties of the gridding method. A sequence of approximate grid solutions formula_7 of some problem that converges to a true solution formula_8 with a corresponding sequence of regular grid spacings formula_9 that converge to 0 is said to have asymptotic "order of convergence" formula_10 and asymptotic "rate of convergence" formula_4 if
formula_12
where the absolute value symbols stand for a metric for the space of solutions such as the uniform norm. Similar definitions also apply for non-grid discretization schemes such as the polygon meshes of a finite element method or the basis sets in computational chemistry: in general, the appropriate definition of the asymptotic rate formula_4 will involve the asymptotic limit of the ratio of an approximation error term above to an asymptotic order formula_10 power of a discretization scale parameter below.
In general, comparatively, one sequence formula_15 that converges to a limit formula_16 is said to asymptotically converge more quickly than another sequence formula_17 that converges to a limit formula_18 if 
formula_19
and the two are said to asymptotically converge with the same order of convergence if the limit is any positive finite value. The two are said to be asymptotically equivalent if the limit is equal to one. These comparative definitions of rate and order of asymptotic convergence are fundamental in asymptotic analysis and find wide application in mathematical analysis as a whole, including numerical analysis, real analysis, complex analysis, and functional analysis. 
Asymptotic rates of convergence for iterative methods.
Definitions.
Suppose that the sequence formula_1 of iterates of an iterative method converges to the limit number formula_2 as formula_22. The sequence is said to "converge with order formula_10 to formula_2" and with a "rate of convergence" formula_4 if the formula_22 limit of quotients of absolute differences of sequential iterates formula_27 from their limit formula_2 satisfies
formula_29
Thus formula_15 converges Q-linearly with a convergence rate of formula_31; see the first plot of the figure below.
More generally, for any initial value formula_32 in the real numbers and a real number common ratio formula_33 between -1 and 1, a geometric progression formula_34 converges linearly with rate formula_35 and the sequence of partial sums of a geometric series formula_36 also converges linearly with rate formula_35. The same holds also for geometric progressions and geometric series parameterized by any complex numbers formula_38
The staggered geometric progression formula_39 using the floor function formula_40 that gives the largest integer that is less than or equal to formula_41 converges R-linearly to 0 with rate 1/2, but it does not converge Q-linearly; see the second plot of the figure below. The defining Q-linear convergence limits do not exist for this sequence because one subsequence of error quotients starting from odd steps converges to 1 and another subsequence of quotients starting from even steps converges to 1/4. When two subsequences of a sequence converge to different limits, the sequence does not itself converge to a limit. Generally, for any staggered geometric progression formula_42, the sequence will not converge Q-linearly but will converge R-linearly with rate formula_43 these examples demonstrate why the "R" in R-linear convergence is short for "root."
The sequence 
formula_44
converges to zero Q-superlinearly. In fact, it is quadratically convergent with a quadratic convergence rate of 1. It is shown in the third plot of the figure below.
Finally, the sequence 
formula_45
converges to zero Q-sublinearly and logarithmically and its convergence is shown as the fourth plot of the figure below.
Convergence rates to fixed points of recurrent sequences.
Recurrent sequences formula_46, called fixed point iterations, define discrete time autonomous dynamical systems and have important general applications in mathematics through various fixed-point theorems about their convergence behavior. When "f" is continuously differentiable, given a fixed point "p", formula_47 such that formula_48, the fixed point is an attractive fixed point and the recurrent sequence will converge at least linearly to "p" for any starting value formula_49 sufficiently close to "p". If formula_50 and formula_51, then the recurrent sequence will converge at least quadratically, and so on. If formula_52, then the fixed point is a repulsive fixed point and sequences cannot converge to "p" from its immediate neighborhoods, though they may still jump to "p" directly from outside of its local neighborhoods.
Order estimation.
A practical method to calculate the order of convergence for a sequence generated by a fixed point iteration is to calculate the following sequence, which converges to the order formula_10:
formula_54
For numerical approximation of an exact value through a numerical method of order formula_10 see.
Accelerating convergence rates.
Many methods exist to accelerate the convergence of a given sequence, i.e., to transform one sequence into a second sequence that converges more quickly to the same limit. Such techniques are in general known as "series acceleration" methods. These may reduce the computational costs of approximating the limits of the original sequences. One example of series acceleration by sequence transformation is Aitken's delta-squared process. These methods in general, and in particular Aitken's method, do not typically increase the order of convergence and thus they are useful only if initially the convergence is not faster than linear: if formula_1 converges linearly, Aitken's method transforms it into a sequence formula_15 that still converges linearly (except for pathologically designed special cases), but faster in the sense that formula_58. On the other hand, if the convergence is already of order ≥ 2, Aitken's method will bring no improvement.
Asymptotic rates of convergence for discretization methods.
Definitions.
A sequence of discretized approximations formula_7 of some continuous-domain function formula_8 that converges to this target, together with a corresponding sequence of discretization scale parameters formula_9 that converge to 0, is said to have asymptotic "order of convergence" formula_10 and asymptotic "rate of convergence" formula_4 if
formula_12
for some positive constants formula_4 and formula_10 and using formula_67 to stand for an appropriate distance metric on the space of solutions, most often either the uniform norm, the absolute difference, or the Euclidean distance. Discretization scale parameters may be spacings of a regular grid in space or in time, the inverse of the number of points of a grid in one dimension, an average or maximum distance between points in a polygon mesh, the single-dimension spacings of an irregular sparse grid, or a characteristic quantum of energy or momentum in a quantum mechanical basis set.
When all the discretizations are generated using a single common method, it is common to discuss the asymptotic rate and order of convergence for the method itself rather than any particular discrete sequences of discretized solutions. In these cases one considers a single abstract discretized solution formula_68 generated using the method with a scale parameter formula_69 and then the method is said to have asymptotic "order of convergence" formula_10 and asymptotic "rate of convergence" formula_4 if
formula_72
again for some positive constants formula_4 and formula_10 and an appropriate metric formula_75 This implies that the error of a discretization asymptotically scales like the discretization's scale parameter to the formula_10 power, or formula_77 using asymptotic big O notation. More precisely, it implies the leading order error is formula_78 which can be expressed using asymptotic small o notation asformula_79
In some cases multiple rates and orders for the same method but with different choices of scale parameter may be important, for instance for finite difference methods based on multidimensional grids where the different dimensions have different grid spacings or for finite element methods based on polygon meshes where choosing either average distance between mesh points or maximum distance between mesh points as scale parameters may imply different orders of convergence. In some especially technical contexts, discretization methods' asymptotic rates and orders of convergence will be characterized by several scale parameters at once with the value of each scale parameter possibly affecting the asymptotic rate and order of convergence of the method with respect to the other scale parameters.
Example.
Consider the ordinary differential equation
formula_80
with initial condition formula_81. We can approximate a solution to this one-dimensional equation using a sequence formula_82 applying the forward Euler method for numerical discretization using any regular grid spacing formula_69 and grid points indexed by formula_84 as follows:
formula_85
which implies the first-order linear recurrence with constant coefficients
formula_86
Given formula_81, the sequence satisfying that recurrence is the geometric progression
formula_88
The exact analytical solution to the differential equation is formula_89, corresponding to the following Taylor expansion in formula_90:
formula_91
Therefore the error of the discrete approximation at each discrete point is
formula_92
For any specific formula_93, given a sequence of forward Euler approximations formula_94, each using grid spacings formula_95 that divide formula_96 so that formula_97, one has
formula_98
for any sequence of grids with successively smaller grid spacings formula_95. Thus formula_94 converges to formula_101 pointwise with a convergence order formula_102 and asymptotic error constant formula_103 at each point formula_104 Similarly, the sequence converges uniformly with the same order and with rate formula_105 on any bounded interval of formula_106, but it does not converge uniformly on the unbounded set of all positive real values, formula_107
Comparing asymptotic rates of convergence.
Definitions.
In asymptotic analysis in general, one sequence formula_108 that converges to a limit formula_2 is said to asymptotically converge to formula_2 with a faster order of convergence than another sequence formula_111 that converges to formula_2 in a shared metric space with distance metric formula_113 such as the real numbers or complex numbers with the ordinary absolute difference metrics, if
formula_114
the two are said to asymptotically converge to formula_2 with the same order of convergence if 
formula_116
for some positive finite constant formula_117 and the two are said to asymptotically converge to formula_2 with the same rate and order of convergence if 
formula_119
These comparative definitions of rate and order of asymptotic convergence are fundamental in asymptotic analysis. For the first two of these there are associated expressions in asymptotic O notation: the first is that formula_120 in small o notation and the second is that formula_121 in Knuth notation. The third is also called asymptotic equivalence, expressed formula_122
Examples.
For any two geometric progressions formula_123 and formula_124 with shared limit zero, the two sequences are asymptotically equivalent if and only if