TOPICS
Search

Rate of Convergence


The rate of convergence of a sequence describes how quickly its terms approach a limit. For a sequence x_n->x_* whose errors e_n=|x_n-x_*| are eventually nonzero, a common definition of order p>=1 is

 lim_(n->infty)(e_(n+1))/(e_n^p)=C,

where 0<C<infty. This is called Q-order to distinguish it from definitions based on bounds for the errors. Order 1 with C<1 gives linear convergence, while orders 2 and 3 give quadratic and cubic convergence. Superlinear convergence means e_(n+1)/e_n->0, even when no order p>1 exists in this definition.

For example, x_n=2^(-n) converges linearly to 0 with C=1/2, while x_n=2^(-2^n) converges quadratically to 0 with C=1. Near a simple root, Newton's method applied to a twice continuously differentiable function has an error bounded by a constant times the square of the preceding error. This accounts for its characteristic quadratic convergence when the leading error coefficient is nonzero.

For root-finding algorithms, the Kung-Traub conjecture gives the sharp universal local order 2^(n-1) for deterministic stationary methods without memory using at most n scalar evaluations per iteration, with attainment for n>=2 (Kung and Traub 1974, Colbrook 2026).


See also

Convergence, Fixed Point Iteration, Limit, Newton's Method, Sequence

Explore with Wolfram|Alpha

References

Colbrook, M. J. "Adversarial Wronskians: A Proof of the Kung-Traub Conjecture." 20 Sep 2026. https://arxiv.org/abs/2610.40660v1.Driscoll, T. A. and Braun, R. J. "Newton's Method." In Fundamentals of Numerical Computation. https://fncbook.com/newton/.Kung, H. T. and Traub, J. F. "Optimal Order of One-Point and Multipoint Iteration." J. ACM 21, 643-651, 1974. https://doi.org/10.1145/321850.321860.

Cite this as:

Weisstein, Eric W. "Rate of Convergence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RateofConvergence.html

Subject classifications