# Rate of convergence

**Rate of convergence** is a characterization, used chiefly in numerical analysis, of how quickly a convergent sequence of approximations approaches its limit. Two related quantities are standard: the *rate*, usually written with big-O notation as a bound on the error at step \( n \), and the *order*, an exponent \( p \) describing how each error compares with the previous one. The distinction matters in practice because it predicts how many iterations or how fine a discretization an algorithm needs to reach a target accuracy.<sup>[1](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)</sup><sup> • </sup><sup>[2](https://mathworld.wolfram.com/RateofConvergence.html)</sup>

| Key fact | Detail |
|---|---|
| Big-O rate | \( (p_n) \to p \) with rate \( O(\beta_n) \) if \( \|p_n - p\| \le \lambda \|\beta_n\| \) for all sufficiently large \( n \), with \( \lambda > 0 \) independent of \( n \)<sup>[1](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)</sup> |
| Order (Q-order) | \( \lim_{n \to \infty} e_{n+1}/e_n^{\,p} = C \) with \( 0 < C < \infty \), where \( e_n = \|x_n - x_*\| \); order 1 with \( C < 1 \) is linear, order 2 quadratic, order 3 cubic<sup>[2](https://mathworld.wolfram.com/RateofConvergence.html)</sup> |
| Superlinear | Successive error ratio tends to 0, \( e_{n+1}/e_n \to 0 \), even when no order \( p > 1 \) exists in the limit definition<sup>[2](https://mathworld.wolfram.com/RateofConvergence.html)</sup><sup> • </sup><sup>[3](https://cswr.nrhstat.org/numopt)</sup> |
| Newton's method | Converges locally and quadratically to a simple zero; for a zero of multiplicity \( m \) convergence is linear, and multiplying the update ratio by \( m \) restores quadratic convergence<sup>[4](https://dlmf.nist.gov/3.8)</sup> |
| Secant method | For a simple zero it converges locally with order \( p = \tfrac{1}{2}(1+\sqrt{5}) = 1.618\ldots \), and needs only one function evaluation per iteration<sup>[4](https://dlmf.nist.gov/3.8)</sup> |
| Bisection method | The bracketing interval shrinks by half each step, \( x_n = 2^{-n}\|b_0 - a_0\| \), giving linear convergence with ratio \( 1/2 \)<sup>[5](https://john-livingston.github.io/advstatcomp/chapters/ch02_rates_of_convergence/)</sup> |
| Gradient descent | Rate \( O(1/\sqrt{k}) \) for smooth nonconvex objectives, \( O(1/k) \) for smooth convex, and \( O(\gamma^k) \) with \( 0 < \gamma < 1 \) under strong convexity<sup>[6](https://www.cs.cmu.edu/~mgormley/courses/10425/slides/lecture8-graddesc.pdf)</sup> |

## Definitions

The big-O form states the rate directly. Let \( (p_n) \) converge to \( p \), and let \( (\beta_n) \) be a positive sequence converging to 0. If there is a constant \( \lambda > 0 \), independent of \( n \), such that

\[ \|p_n - p\| \le \lambda \, \|\beta_n\| \]

for all sufficiently large \( n \), then \( (p_n) \) converges to \( p \) with rate \( O(\beta_n) \), and one writes \( p_n = p + O(\beta_n) \) to indicate that the error decays like \( \beta_n \).<sup>[1](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)</sup><sup> • </sup><sup>[7](https://faculty.washington.edu/trogdon/105A/html/Lecture3.html)</sup> A useful test is the limit theorem: if

\[ \lim_{n \to \infty} \frac{\|p_n - p\|}{\beta_n} = L, \qquad 0 < L < \infty, \]

then the rate is \( O(\beta_n) \) with constant \( L \).<sup>[1](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)</sup> For example, \( p_n = (2n+1)/n \) converges to 2 with rate \( O(1/n) \) and constant 1, while \( q_n = (8n^3 - n)/(4n^3) \) converges to 2 with rate \( O(1/n^2) \) and constant \( 1/2 \).<sup>[1](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)</sup>

The order form compares consecutive errors. With \( e_n = \|x_n - x_*\| \) eventually nonzero, the sequence has order \( p \) when

\[ \lim_{n \to \infty} \frac{e_{n+1}}{e_n^{\,p}} = C, \qquad 0 < C < \infty. \]

The constant \( C \) is the asymptotic error constant.<sup>[2](https://mathworld.wolfram.com/RateofConvergence.html)</sup><sup> • </sup><sup>[8](https://notes.edubirdie.com/docs/whitman-college/math-467-numerical-analysis/67811-notes-rate-of-convergence)</sup> The same idea extends from sequences to functions of a discretization parameter: \( f(h) \to L \) at \( O(g(h)) \) if \( \|f(h) - L\| \le K g(h) \) for a positive constant \( K \) as \( h \to 0 \); the finite-difference approximation \( f(h) = (\sin h - \sin 0)/h \) to the derivative of \( \sin x \) at 0 satisfies \( f(h) = 1 + O(h^2) \).<sup>[7](https://faculty.washington.edu/trogdon/105A/html/Lecture3.html)</sup> Similar definitions apply to non-grid discretizations such as finite element meshes and the basis sets of computational chemistry.<sup>[9](https://wi.kifa.st/en/Rate_of_convergence)</sup>

## Linear, superlinear, and quadratic convergence

**Linear convergence** means the error decreases by a constant factor per step. For fixed point iteration \( x_{k+1} = g(x_k) \), the error ratios typically satisfy \( E_{k+1}/E_k \to C = \|g'(x)\| \), so errors eventually shrink roughly geometrically, \( E_k \approx K C^k \). The name comes from the approximately linear relation \( E_{n+1} \approx C E_n \) between consecutive errors; in optimization the same behavior is called geometric convergence, and the number of correct digits then grows linearly with the iteration count.<sup>[10](https://lemesurierb.people.charleston.edu/introduction-to-numerical-methods-and-analysis-python/docs/main/error-measures-convergence-rates.html)</sup><sup> • </sup><sup>[3](https://cswr.nrhstat.org/numopt)</sup> A precise optimization-style definition uses the limsup (limit superior: the largest value the sequence repeatedly approaches) of successive error ratios: convergence is linear when this limsup equals some \( r \in (0,1) \), called the asymptotic rate; sublinear when it equals 1; and superlinear when it equals 0.<sup>[3](https://cswr.nrhstat.org/numopt)</sup>

For a contraction mapping \( \Phi \), Banach's fixed point theorem gives \( \|\theta_n - \theta_\infty\| \le c^n \|\theta_0 - \theta_\infty\| \), so convergence is at least geometric with rate bounded by \( c \). This global bound can be pessimistic; a local upper bound on the asymptotic rate is \( r_{\max} = \sup_{\|\gamma\| = 1} \|D\Phi(\theta_\infty)\gamma\| \), the largest directional stretch of the derivative at the fixed point.<sup>[3](https://cswr.nrhstat.org/numopt)</sup>

**Superlinear convergence** covers everything faster than linear: \( e_{n+1}/e_n \to 0 \). This includes every case of order \( p > 1 \), and for most practical purposes establishing superlinear convergence is sufficient without pinning down the exact order.<sup>[10](https://lemesurierb.people.charleston.edu/introduction-to-numerical-methods-and-analysis-python/docs/main/error-measures-convergence-rates.html)</sup> In superlinear methods the error decreases by a growing factor from iteration to iteration.<sup>[11](https://www.netlib.org/linalg/old_html_templates/chapter2.6.html)</sup>

**Quadratic convergence** satisfies \( e_{n+1} \le M e_n^2 \) for a finite constant \( M \) once \( n \) is large enough; it roughly doubles the number of correct decimal places per iteration.<sup>[5](https://john-livingston.github.io/advstatcomp/chapters/ch02_rates_of_convergence/)</sup><sup> • </sup><sup>[12](https://www.maths.usyd.edu.au/u/david/mc3/nm/addlectmat/3NML3.pdf)</sup> Simple model sequences illustrate the hierarchy: \( 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 \).<sup>[2](https://mathworld.wolfram.com/RateofConvergence.html)</sup>

## Rates of standard methods

The order a method achieves reflects how much information about the problem it uses. Algorithms that use little information about the objective, such as bisection, converge slowly; methods that use derivative information typically converge faster.<sup>[5](https://john-livingston.github.io/advstatcomp/chapters/ch02_rates_of_convergence/)</sup>

- **Bisection** halves the bracketing interval each iteration, so the error bound is \( 2^{-n}\|b_0 - a_0\| \), although the ratio of successive actual errors is not necessarily exactly \( 1/2 \): linear convergence, but with guaranteed convergence to any predetermined accuracy for a continuous sign-changing function.<sup>[5](https://john-livingston.github.io/advstatcomp/chapters/ch02_rates_of_convergence/)</sup><sup> • </sup><sup>[4](https://dlmf.nist.gov/3.8)</sup><sup> • </sup><sup>[15](https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/10RootFinding/bisection/error.html)</sup>
- **Newton's method** \( z_{n+1} = z_n - f(z_n)/f'(z_n) \) converges locally and quadratically to a simple zero. At a zero of multiplicity \( m \) the convergence drops to linear, but multiplying the ratio \( f(z_n)/f'(z_n) \) by \( m \) restores quadratic convergence.<sup>[4](https://dlmf.nist.gov/3.8)</sup> Near a simple root the error is bounded by a constant times the square of the preceding error, which accounts for the characteristic quadratic behavior.<sup>[2](https://mathworld.wolfram.com/RateofConvergence.html)</sup>
- **Regula falsi** (inverse linear interpolation) converges linearly.<sup>[4](https://dlmf.nist.gov/3.8)</sup>
- **The secant method** converges locally with order \( p = (1+\sqrt{5})/2 \approx 1.618 \) for a simple zero; because it needs only one function evaluation per iteration, its numerical efficiency is ultimately higher than Newton's, though convergence is not guaranteed and an iterate may leave the starting interval.<sup>[4](https://dlmf.nist.gov/3.8)</sup>
- **Steffensen's method** for \( z = \varphi(z) \) converges locally and quadratically over both \( \mathbb{R} \) and \( \mathbb{C} \).<sup>[4](https://dlmf.nist.gov/3.8)</sup>

For iterative methods for linear systems, the rate depends greatly on the spectrum of the coefficient matrix, which is why such methods are usually paired with a preconditioner, a matrix that transforms the system into one with a more favorable spectrum; without one the iteration may fail to converge at all.<sup>[11](https://www.netlib.org/linalg/old_html_templates/chapter2.6.html)</sup> For the Conjugate Gradient method on a symmetric positive definite system, the number of iterations needed to reduce the error by a fixed relative factor is proportional to the square root of the spectral condition number, and when the extremal eigenvalues are well separated one often observes superlinear behavior, a rate that increases per iteration as error components along extreme eigenvectors are eliminated first.<sup>[13](https://netlib.org/linalg/old_html_templates/subsubsection2.6.3.1.2.html)</sup>

## Rates in optimization

[Gradient descent](https://www.edgepedia.org/gradient-descent)'s rate depends on the smoothness and convexity of the objective. With fixed step size \( \eta \le 1/\beta \) for a \( \beta \)-smooth (Lipschitz gradient) possibly nonconvex function, gradient descent reaches a point with gradient norm \( O(1/\sqrt{k}) \) after \( k \) steps, and this rate cannot be improved over the class of differentiable functions with Lipschitz gradients by any deterministic algorithm. For smooth convex objectives the function-value gap is \( O(1/k) \), and under strong convexity it decays as \( O(\gamma^k) \) with \( 0 < \gamma < 1 \), so an \( \epsilon \)-suboptimal point is found in \( O(\log(1/\epsilon)) \) iterations.<sup>[6](https://www.cs.cmu.edu/~mgormley/courses/10425/slides/lecture8-graddesc.pdf)</sup> In deep learning, analyses of overparametrized networks identify conditions on width, depth, and initialization that produce a benign optimization landscape along the training trajectory and thereby a linear convergence rate of gradient descent to a global minimum.<sup>[14](https://signalprocessingsociety.org/publications-resources/ieee-signal-processing-magazine/2026/05/convergence-implicit-bias-and-edge-stability-gradient-descent-deep-learning-reviewing-recent)</sup>

## Interpreting rates in practice

Comparing orders is the usual way to compare algorithms: since \( 1/n^2 \) approaches 0 faster than \( 1/n \), an \( O(1/n^2) \) method is generally the faster one, and interest centers on the order because it predicts behavior on hard problems where \( n \) is large.<sup>[1](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)</sup> The asymptotic error constant still matters in practical terms, since a method with a favorable order but a large constant can be slower over the iteration range actually used.<sup>[1](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)</sup> Rates are also asymptotic statements: quadratic convergence for [Newton's method](https://www.edgepedia.org/newtons-method) holds locally, for initial values close enough to the root, and the DLMF example \( f(x) = x - \tan x \) shows that the choice of starting value can be critical, with the iteration failing to converge to the wanted zero for starting points outside a narrow interval.<sup>[4](https://dlmf.nist.gov/3.8)</sup>

## References

1. [Section 2.3, Convergence of Sequences, *Introduction to Numerical Analysis* (P. Staab)](https://pstaabp.github.io/numerical-analysis-book/sect-convergence-sequence.html)
2. [Rate of Convergence, Wolfram MathWorld](https://mathworld.wolfram.com/RateofConvergence.html)
3. [Chapter 9, Numerical Optimization, *Computational Statistics with R*](https://cswr.nrhstat.org/numopt)
4. [DLMF §3.8, Nonlinear Equations, NIST Digital Library of Mathematical Functions](https://dlmf.nist.gov/3.8)
5. [Section 2.2, Rates of Convergence, *Advanced Statistical Computing with Python*](https://john-livingston.github.io/advstatcomp/chapters/ch02_rates_of_convergence/)
6. [Lecture 8, Convergence of Gradient Descent, CMU 10-425](https://www.cs.cmu.edu/~mgormley/courses/10425/slides/lecture8-graddesc.pdf)
7. [Lecture 3, Rate of Convergence, University of Washington Amath 105A](https://faculty.washington.edu/trogdon/105A/html/Lecture3.html)
8. [Notes: Rate of Convergence, MATH 467 Numerical Analysis, Whitman College](https://notes.edubirdie.com/docs/whitman-college/math-467-numerical-analysis/67811-notes-rate-of-convergence)
9. [Rate of Convergence (reference mirror)](https://wi.kifa.st/en/Rate_of_convergence)
10. [Section 1.5, Measures of Error and Order of Convergence, *Introduction to Numerical Methods and Analysis with Python*](https://lemesurierb.people.charleston.edu/introduction-to-numerical-methods-and-analysis-python/docs/main/error-measures-convergence-rates.html)
11. [Chapter 2.6, Iterative Methods, Templates for the Solution of Linear Systems, Netlib](https://www.netlib.org/linalg/old_html_templates/chapter2.6.html)
12. [Numerical Methods lecture notes, Sydney NML3](https://www.maths.usyd.edu.au/u/david/mc3/nm/addlectmat/3NML3.pdf)
13. [Convergence of iterative methods, Netlib](https://netlib.org/linalg/old_html_templates/subsubsection2.6.3.1.2.html)
14. [On the Convergence, Implicit Bias, and Edge of Stability of Gradient Descent in Deep Learning, IEEE Signal Processing Magazine](https://signalprocessingsociety.org/publications-resources/ieee-signal-processing-magazine/2026/05/convergence-implicit-bias-and-edge-stability-gradient-descent-deep-learning-reviewing-recent)
15. [ece.uwaterloo.ca](https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/10RootFinding/bisection/error.html)

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Numerical, string, and geometric algorithms › Numerical methods and approximation*

*Initially written Sep 17, 2026 · Reviewed: Sep 19, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license