A sequence $\{x_i\}$ is said to converge linearly to $x^*$ if there is a constant $1>c>0$ such that $||x_{i+1}-x^*|| \leq c ||x_i -x^*||$ for all $i>N$ for some natural number $N>0$ .

An alternative definition is that $||x_{i+1}-x_i|| \leq c ||x_i - x_{i-1} ||$ for all $i$ .

Notice that if $N=1$ , then by iterating the first inequality we have $$ ||x_{i+1}-x^*|| \leq c^i ||x_1 -x^*||. $$ That is, the error decreases exponentially with the index $i$ .

If the inequality holds for all $c>0$ then we say that the sequence $\{x_i\}$ has superlinear convergence.