# 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 |