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.

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}$.