Namespaces
Variants
Actions

Difference between revisions of "Rate of convergence"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
A characteristic of an iterative method that enables one to make a judgement on the dependence of the error of the method at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775701.png" />-th iteration on the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775702.png" /> (see [[#References|[1]]]–[[#References|[3]]]). For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775703.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775704.png" /> is the norm of the error at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775705.png" />-th iteration, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775706.png" />, then one says that the method converges with the rate of a [[Geometric progression|geometric progression]] with denominator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775707.png" />, while the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775708.png" /> is called the asymptotic rate of convergence.
+
{{TEX|done}}
 +
A characteristic of an iterative method that enables one to make a judgement on the dependence of the error of the method at the $n$-th iteration on the number $n$ (see [[#References|[1]]]–[[#References|[3]]]). For example, if $\|z^n\|\leq q^n\|z^0\|$, where $\|z^n\|$ is the norm of the error at the $n$-th iteration, while $q<1$, then one says that the method converges with the rate of a [[Geometric progression|geometric progression]] with denominator $q$, while the value $-\ln q$ is called the asymptotic rate of convergence.
  
Given inequalities of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r0775709.png" />, one speaks of a polynomial rate of convergence of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077570/r07757010.png" /> (for example, the quadratic rate of convergence of the Newton–Kantorovich iteration method, cf. [[Kantorovich process|Kantorovich process]]).
+
Given inequalities of the type $\|z^{n+1}\|\leq C\|z^n\|^k$, one speaks of a polynomial rate of convergence of order $k$ (for example, the quadratic rate of convergence of the Newton–Kantorovich iteration method, cf. [[Kantorovich process|Kantorovich process]]).
  
 
====References====
 
====References====

Latest revision as of 12:05, 13 August 2014

A characteristic of an iterative method that enables one to make a judgement on the dependence of the error of the method at the $n$-th iteration on the number $n$ (see [1][3]). For example, if $\|z^n\|\leq q^n\|z^0\|$, where $\|z^n\|$ is the norm of the error at the $n$-th iteration, while $q<1$, then one says that the method converges with the rate of a geometric progression with denominator $q$, while the value $-\ln q$ is called the asymptotic rate of convergence.

Given inequalities of the type $\|z^{n+1}\|\leq C\|z^n\|^k$, one speaks of a polynomial rate of convergence of order $k$ (for example, the quadratic rate of convergence of the Newton–Kantorovich iteration method, cf. Kantorovich process).

References

[1] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[2] G.I. Marchuk, "Methods of numerical mathematics" , Springer (1982) (Translated from Russian)
[3] A.A. Samarskii, E.S. Nikolaev, "Numerical methods for grid equations" , 1–2 , Birkhäuser (1989) (Translated from Russian)
[4] L.A. Hageman, D.M. Young, "Applied iterative methods" , Acad. Press (1981)
[5] J.F. Traub, "Iterative methods for the solution of equations" , Prentice-Hall (1964)


Comments

Of course, one can speak of the rate of convergence of any process (not just iterative) in which convergence plays a role. See, in particular, Approximation of functions (and related articles).

How to Cite This Entry:
Rate of convergence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Rate_of_convergence&oldid=13011
This article was adapted from an original article by E.G. D'yakonov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article