Editing Rate of convergence (section)

== Comparing asymptotic rates of convergence ==

=== Definitions ===
In [[asymptotic analysis]] in general, one sequence <math>(a_k)_{k \in \mathbb{N}}</math> that converges to a [[Limit (mathematics)|limit]] <math>L</math> is said to asymptotically converge to <math>L</math> with a faster order of convergence than another sequence <math>(b_k)_{k \in \mathbb{N}}</math> that converges to <math>L</math> in a shared [[metric space]] with [[distance metric]] <math>|\cdot|,</math> such as the [[Real number|real numbers]] or [[Complex number|complex numbers]] with the ordinary [[absolute difference]] metrics, if

<math display="block">\lim _{k \rightarrow \infty} \frac{\left|a_k - L\right|}{|b_k - L|} = 0,</math>

the two are said to asymptotically converge to <math>L</math> with the same order of convergence if 

<math display="block">\lim_{k \rightarrow \infty} \frac{\left|a_k - L\right|}{|b_k - L|} = \mu</math>

for some positive finite constant <math>\mu,</math> and the two are said to asymptotically converge to <math>L</math> with the same rate and order of convergence if 

<math display="block">\lim_{k \rightarrow \infty} \frac{\left|a_k - L\right|}{|b_k - L|} = 1.</math>

These comparative definitions of rate and order of asymptotic convergence are fundamental in [[asymptotic analysis]].<ref name="Balcázar">{{cite journal |last1=Balcázar |first1=José L. |last2=Gabarró |first2=Joaquim |title=Nonuniform complexity classes specified by lower and upper bounds |url=http://archive.numdam.org/article/ITA_1989__23_2_177_0.pdf |url-status=live |journal=RAIRO – Theoretical Informatics and Applications – Informatique Théorique et Applications |language=en |volume=23 |issue=2 |page=180 |issn=0988-3754 |archive-url=https://web.archive.org/web/20170314153158/http://archive.numdam.org/article/ITA_1989__23_2_177_0.pdf |archive-date=14 March 2017 |access-date=14 March 2017 |via=Numdam}}</ref><ref name="Cucker">{{cite book |last1=Cucker |first1=Felipe |title=Condition: The Geometry of Numerical Algorithms |last2=Bürgisser |first2=Peter |publisher=Springer |year=2013 |isbn=978-3-642-38896-5 |location=Berlin, Heidelberg |pages=467–468 |chapter=A.1 Big Oh, Little Oh, and Other Comparisons |doi=10.1007/978-3-642-38896-5 |chapter-url=https://books.google.com/books?id=SNu4BAAAQBAJ&pg=PA467}}</ref> For the first two of these there are associated expressions in [[Big O notation|asymptotic O notation]]: the first is that <math>a_k - L = o(b_k - L)</math> in small o notation<ref name=":22">{{Cite book |last=Apostol |first=Tom M. |author-link=Tom M. Apostol |title=Calculus |date=1967 |publisher=John Wiley & Sons |isbn=0-471-00005-1 |edition=2nd |volume=1 |location=USA |pages=286}}</ref> and the second is that <math>a_k - L = \Theta(b_k - L) </math> in Knuth notation.<ref name="knuth">{{cite journal |last=Knuth |first=Donald |date=April–June 1976 |title=Big Omicron and big Omega and big Theta |journal=SIGACT News |volume=8 |issue=2 |pages=18–24 |doi=10.1145/1008328.1008329 |s2cid=5230246 |doi-access=free |s2cid-access=free}}</ref> The third is also called asymptotic equivalence, expressed <math>a_k - L \sim b_k - L.</math><ref name=":2">{{Cite book |last=Apostol |first=Tom M. |title=Calculus |date=1967 |publisher=John Wiley & Sons |isbn=0-471-00005-1 |edition=2nd |volume=1 |location=USA |pages=396}}</ref><ref>{{SpringerEOM|id=Asymptotic_equality|title=Asymptotic equality}}</ref>

=== Examples ===
For any two [[Geometric progression|geometric progressions]] <math>(a r^k)_{k \in \mathbb{N}}</math> and <math>(b s^k)_{k \in \mathbb{N}},</math> with shared limit zero, the two sequences are asymptotically equivalent if and only if both <math>a = b</math> and <math>r = s.</math> They converge with the same order if and only if <math>r = s.</math> <math>(a r^k)</math> converges with a faster order than <math>(b s^k)</math> if and only if <math>r < s.</math> The convergence of any [[geometric series]] to its limit has error terms that are equal to a geometric progression, so similar relationships hold among geometric series as well. Any sequence that is asymptotically equivalent to a convergent geometric sequence may be either be said to "converge geometrically" or "converge exponentially" with respect to the absolute difference from its limit, or it may be said to "converge linearly" relative to a logarithm of the absolute difference such as the "number of decimals of precision." The latter is standard in numerical analysis.

For any two sequences of elements proportional to an inverse power of <math>k,</math> <math>(a k^{-n})_{k \in \mathbb{N}}</math> and <math>(b k^{-m})_{k \in \mathbb{N}},</math> with shared limit zero, the two sequences are asymptotically equivalent if and only if both <math>a = b</math> and <math>n = m.</math> They converge with the same order if and only if <math>n = m.</math> <math>(a k^{-n})</math> converges with a faster order than <math>(b k^{-m})</math> if and only if <math>n > m.</math> 

For any sequence <math>(a_k)_{k \in \mathbb{N}}</math> with a limit of zero, its convergence can be compared to the convergence of the shifted sequence <math>(a_{k-1})_{k \in \mathbb{N}},</math> rescalings of the shifted sequence by a constant <math>\mu,</math> <math>(\mu a_{k-1})_{k \in \mathbb{N}},</math> and scaled <math>q</math>-powers of the shifted sequence, <math>(\mu a_{k-1}^q)_{k \in \mathbb{N}}.</math> These comparisons are the basis for the Q-convergence classifications for iterative numerical methods as described above: when a sequence of iterate errors from a numerical method <math>(|x_k - L|)_{k \in \mathbb{N}}</math> is asymptotically equivalent to the shifted, exponentiated, and rescaled sequence of iterate errors <math>(\mu |x_{k-1} - L|^q)_{k \in \mathbb{N}},</math> it is said to converge with order <math>q</math> and rate <math>\mu.</math>