# 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^{*}||\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.

Title linear convergence LinearConvergence 2013-03-22 14:20:55 2013-03-22 14:20:55 Mathprof (13753) Mathprof (13753) 13 Mathprof (13753) Definition msc 41A25 QuadraticConvergence superlinear convergence