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.

Title	linear convergence
Canonical name	LinearConvergence
Date of creation	2013-03-22 14:20:55
Last modified on	2013-03-22 14:20:55
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	13
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 41A25
Related topic	QuadraticConvergence
Defines	superlinear convergence