The rate of convergence quantifies how quickly a sequence ${x_k}$ approaches its limit $x^\ast$ as the index $k$ increases. Formally, if the errors $e_k = |x_k - x^\ast|$ satisfy
$$ \lim_{k\to\infty}\frac{e_{k+1}}{e_k^{,p}} = C,\qquad C eq 0, $$
the sequence is said to converge with order $p$ and asymptotic error constant $C$. The value of $p$ characterises the speed:
- Linear convergence ($p = 1$, $0<C<1$): the error is reduced by roughly a constant factor each iteration, i.e., $e_{k+1}\approx C e_k$.
- Superlinear convergence ($p = 1$ with $C = 0$): the reduction factor tends to zero, faster than any linear rate but without a fixed exponent.
- Quadratic convergence ($p = 2$): the error squares at each step, $e_{k+1}\approx C e_k^{2}$.
- Higher‑order convergence ($p>2$): analogous generalisation, e.g., cubic ($p=3$).
When a sequence converges linearly, the rate constant $C$ (often written $\rho$ or $\lambda$) can be expressed as
$$ \rho = \lim_{k\to\infty}\frac{e_{k+1}}{e_k}, $$
and the number of correct digits roughly increases by $-\log_{10}\rho$ per iteration.
The rate of convergence is widely used to assess iterative algorithms in numerical analysis, such as:
- Root‑finding methods – Newton’s method exhibits quadratic convergence under standard smoothness assumptions, while the bisection method converges linearly with $\rho = 1/2$.
- Fixed‑point iterations – Convergence rate depends on the spectral radius of the Jacobian of the iteration function at the fixed point.
- Optimization algorithms – Gradient descent typically shows linear convergence for strongly convex functions; accelerated schemes (e.g., Nesterov’s method) can achieve faster rates.
- Iterative linear solvers – Convergence of methods like the Conjugate Gradient algorithm is often described in terms of reduction of the residual norm per iteration, linked to the condition number of the matrix.
In practice, the observed convergence rate may be estimated from computed iterates by fitting a model to $\log e_k$ versus $\log k$ or by computing successive ratios of errors.
The concept is distinct from asymptotic convergence, which refers to the behavior of the error as $k\to\infty$, and from convergence speed, an informal term sometimes used interchangeably with rate of convergence.
