linear convergence

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^{*}||\le c||x_i-x^{*}||$ for all $i>N$ for some natural number $N>0$.

An alternative definition is that $||x_{i+1}-x_i||\le 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^{*}||\le 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.