Order of convergence (${\lim }_{k\to \infty }\Vert e_{k+1}\Vert /\Vert e_k{\Vert }^p=C\in (0,\infty )$)

An iteration converging to $x_{\ast }$ has exact asymptotic order $p$ if its nonzero errors $e_k=x_k-x_{\ast }$ satisfy the displayed limit. A bound $\Vert e_{k+1}\Vert \le C\Vert e_k{\Vert }^p$ instead asserts at least order $p$. Finite termination is treated separately because the error ratios become undefined.

An iteration of a map has linear convergence to its limit when its nonzero errors $e_k=x_k-\alpha$ satisfy $|e_{k+1}|/|e_k|\to \rho$ for some $0<\rho <1$. The error eventually shrinks by approximately the same factor at each step. This is exact order of convergence one, in contrast to quadratic convergence.

A sequence with errors $e_k=x_k-x^{\ast }$ converges Q-linearly in a specified norm if there is a constant $q<1$ with $\Vert e_{k+1}\Vert \le q\Vert e_k\Vert$ eventually. The limsup of consecutive nonzero error ratios is its asymptotic factor. This is stronger than merely having a bound $\Vert e_k\Vert \le C{q}^k$, which is called R-linear convergence. The norm and whether an iteration is one coordinate step or an entire sweep must be specified when quoting a factor.

An iteration has at least cubic convergence when its errors eventually satisfy the displayed inequality with fixed $C>0$. Exact order of convergence three requires a positive finite limit of $\Vert e_{k+1}\Vert /\Vert e_k{\Vert }^3$. If $C^{1/2}\Vert e_N\Vert <1$, setting $d_k=C^{1/2}\Vert e_k\Vert$ gives $d_{k+1}\le d_k^3$, hence $d_{N+j}\le d_N^{3^j}$.