Rate of convergence

Definition

Let $(x_k)_{k \ge 0}$ be a real sequence that converges to a limit $L$, with $x_k \ne L$ for all $k$. Let $e_k = \abs{x_k - L}$ be the error at step $k$.

1. The sequence converges linearly with rate $\mu$ if $\lim_{k \to \infty} e_{k+1} / e_k = \mu$ for some $\mu \in (0, 1)$.
2. It converges superlinearly if $\lim_{k \to \infty} e_{k+1} / e_k = 0$, and sublinearly if $\lim_{k \to \infty} e_{k+1} / e_k = 1$.
3. For a real number $q > 1$, it converges with order $q$ if $\lim_{k \to \infty} e_{k+1} / e_k^q = \mu$ for some $\mu > 0$.

Order $2$ is called quadratic convergence and order $3$ cubic convergence. The same definitions apply to sequences in a normed space, with $e_k = \norm{x_k - L}$.