Editing Rate of convergence (section)

==Asymptotic rates of convergence for iterative methods==
=== Definitions ===
==== Q-convergence ====
Suppose that the [[sequence]] <math>(x_k)</math> of iterates of an [[iterative method]] converges to the [[Limit (mathematics)|limit]] number <math>L</math> as <math>k \rightarrow \infty</math>. The sequence is said to ''converge with order <math>q</math> to <math>L</math>'' and with a ''rate of convergence'' <math>\mu</math> if the <math>k \rightarrow \infty</math> limit of quotients of [[Absolute difference|absolute differences]] of sequential iterates <math>x_k, x_{k+1}</math> from their limit <math>L</math> satisfies

<math display="block">\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_k - L|^q} = \mu</math>

for some positive constant <math>\mu \in (0, 1)</math> if <math>q = 1</math> and <math>\mu \in (0, \infty)</math> if <math>q > 1</math>.<ref name=":0" /><ref>{{Cite web |last=Hundley |first=Douglas |title=Rate of Convergence |url=http://people.whitman.edu/~hundledr/courses/M467F06/ConvAndError.pdf |access-date=2020-12-13 |website=Whitman College}}</ref><ref>{{cite journal |last=Porta |first=F. A. |date=1989 |title=On Q-Order and R-Order of Convergence |url=https://link.springer.com/content/pdf/10.1007/BF00939805.pdf |journal=Journal of Optimization Theory and Applications |volume=63 |issue=3 |pages=415–431 |doi=10.1007/BF00939805 |access-date=2020-07-31 |s2cid=116192710}}</ref> Other more technical rate definitions are needed if the sequence converges but <math display="inline">\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_k - L|} = 1</math><ref name=":1">{{cite journal |last=Van Tuyl |first=Andrew H. |year=1994 |title=Acceleration of convergence of a family of logarithmically convergent sequences |url=https://www.ams.org/journals/mcom/1994-63-207/S0025-5718-1994-1234428-2/S0025-5718-1994-1234428-2.pdf |journal=Mathematics of Computation |volume=63 |issue=207 |pages=229–246 |doi=10.2307/2153571 |jstor=2153571 |access-date=2020-08-02}}</ref> or the limit does not exist.<ref name=":0" /> This definition is technically called Q-convergence, short for quotient-convergence, and the rates and orders are called rates and orders of Q-convergence when that technical specificity is needed. {{slink||R-convergence}}, below, is an appropriate alternative when this limit does not exist.

Sequences with larger orders <math>q</math> converge more quickly than those with smaller order, and those with smaller rates <math>\mu</math> converge more quickly than those with larger rates for a given order. This "smaller rates converge more quickly" behavior among sequences of the same order is standard but it can be counterintuitive. Therefore it is also common to define <math>-\log_{10} \mu</math> as the rate; this is the "number of extra decimals of precision per iterate" for sequences that converge with order 1.<ref name=":0" /> 

Integer powers of <math>q</math> are common and are given common names. Convergence with order <math>q = 1</math> and <math>\mu \in (0, 1)</math> is called ''linear convergence'' and the sequence is said to ''converge linearly to <math>L</math>''. Convergence with <math>q = 2</math> and any <math>\mu</math> is called ''quadratic convergence'' and the sequence is said to ''converge quadratically''. Convergence with <math>q = 3</math> and any <math>\mu</math> is called ''cubic convergence''. However, it is not necessary that <math>q</math> be an integer. For example, the [[secant method]], when converging to a regular, [[Polynomial#Solving_polynomial_equations|simple root]], has an order of the [[golden ratio]] φ ≈ 1.618.<ref>{{Cite web |last=Chanson |first=Jeffrey R. |date=October 3, 2024 |title=Order of Convergence |url=https://math.libretexts.org/Bookshelves/Applied_Mathematics/Numerical_Methods_(Chasnov)/02%3A_Root_Finding/2.04%3A_Order_of_Convergence |access-date=October 3, 2024 |website=LibreTexts Mathematics}}</ref> 

The common names for integer orders of convergence connect to [[Big O notation|asymptotic big O notation]], where the convergence of the quotient implies <math display="inline">|x_{k+1} - L| = O(|x_k - L|^q).</math> These are linear, quadratic, and cubic polynomial expressions when <math>q</math> is 1, 2, and 3, respectively. More precisely, the limits imply the leading order error is exactly <math display="inline">\mu |x_k - L|^q,</math> which can be expressed using [[Small o notation|asymptotic small o notation]] as<math display="inline">|x_{k+1} - L| = \mu |x_k - L|^q + o(|x_k - L|^q).</math>

In general, when <math> q > 1</math> for a sequence or for any sequence that satisfies <math display="inline">\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_k - L|} = 0,</math> those sequences are said to ''converge superlinearly'' (i.e., faster than linearly).<ref name=":0" /> A sequence is said to ''converge sublinearly'' (i.e., slower than linearly) if it converges and <math display="inline">\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_k - L|} = 1.</math> Importantly, it is incorrect to say that these sublinear-order sequences converge linearly with an asymptotic rate of convergence of 1. A sequence <math>(x_k)</math> ''converges logarithmically to <math>L</math>'' if the sequence converges sublinearly and also <math display="inline">\lim_{k \to \infty} \frac{|x_{k+1} - x_{k}|}{|x_{k} - x_{k-1}|} = 1.</math><ref name=":1" />

==== R-convergence ====
The definitions of Q-convergence rates have the shortcoming that they do not naturally capture the convergence behavior of sequences that do converge, but do not converge with an asymptotically constant rate with every step, so that the Q-convergence limit does not exist. One class of examples is the staggered geometric progressions that get closer to their limits only every other step or every several steps, for instance the example <math display="inline">(b_k) = 1, 1, 1/4, 1/4, 1/16, 1/16, \ldots, 1/4^{\left\lfloor \frac{k}{2} \right\rfloor}, \ldots</math> detailed below (where <math display="inline">\lfloor x \rfloor</math> is the [[floor function]] applied to <math>x</math>). The defining Q-linear convergence limits do not exist for this sequence because one subsequence of error quotients starting from odd steps converges to 1 and another subsequence of quotients starting from even steps converges to 1/4. When two subsequences of a sequence converge to different limits, the sequence does not itself converge to a limit. 

In cases like these, a closely related but more technical definition of rate of convergence called R-convergence is more appropriate. The "R-" prefix stands for "root."<ref name=":0" /><ref name="NocedalWright2006">{{Cite book |last1=Nocedal |first1=Jorge |title=Numerical Optimization |last2=Wright |first2=Stephen J. |publisher=[[Springer-Verlag]] |year=2006 |isbn=978-0-387-30303-1 |edition=2nd |location=Berlin, New York}}</ref>{{rp|620}} A sequence <math>(x_k)</math> that converges to <math>L</math> is said to ''converge at least R-linearly'' if there exists an error-bounding sequence <math>(\varepsilon_k)</math> such that <math display="inline">
|x_k - L|\le\varepsilon_k\quad\text{for all }k
</math> and <math> (\varepsilon_k)  </math> converges Q-linearly to zero; analogous definitions hold for R-superlinear convergence, R-sublinear convergence, R-quadratic convergence, and so on.<ref name=":0" />

Any error bounding sequence <math>(\varepsilon_k)</math> provides a lower bound on the rate and order of R-convergence and the greatest lower bound gives the exact rate and order of R-convergence. As for Q-convergence, sequences with larger orders <math>q</math> converge more quickly and those with smaller rates <math>\mu</math> converge more quickly for a given order, so these greatest-rate-lower-bound error-upper-bound sequences are those that have the greatest possible <math>q</math> and the smallest possible <math>\mu</math> given that <math>q</math>.

For the example <math display="inline">(b_k)</math> given above, the tight bounding sequence <math display="inline">(\varepsilon_k) = 2, 1, 1/2, 1/4, 1/8, 1/16, \ldots, 1/2^{k - 1}, \ldots</math>converges Q-linearly with rate 1/2, so <math display="inline">(b_k)</math> converges R-linearly with rate 1/2. Generally, for any staggered geometric progression <math>(a r^{\lfloor k / m \rfloor})</math>, the sequence will not converge Q-linearly but will converge R-linearly with rate <math display="inline">\sqrt[m]{|r|}. </math> These examples demonstrate why the "R" in R-linear convergence is short for "root."

===Examples===

The [[geometric progression]] <math display="inline">(a_k) = 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \ldots, 1/{2^k}, \dots </math>  converges to <math>L = 0</math>. Plugging the sequence into the definition of Q-linear convergence (i.e., order of convergence 1) shows that

<math display="block">\lim_{k \to \infty} \frac{\left| 1/2^{k+1} - 0\right|}{\left| 1/ 2^k - 0 \right|} = \lim_{k \to \infty} \frac{2^k}{2^{k+1}} = \frac{1}{2}. </math>

Thus <math>(a_k)</math> converges Q-linearly with a convergence rate of <math>\mu = 1/2</math>; see the first plot of the figure below.

More generally, for any initial value <math>a</math> in the real numbers and a real number common ratio <math>r</math> between -1 and 1, a geometric progression <math>(a r^k)</math> converges linearly with rate <math>|r|</math> and the sequence of partial sums of a [[geometric series]] <math display="inline">(\sum_{n=0}^k ar^n)</math> also converges linearly with rate <math>|r|</math>. The same holds also for geometric progressions and geometric series parameterized by any [[Complex number|complex numbers]] <math>a \in \mathbb{C}, r \in \mathbb{C}, |r| < 1.</math>

The staggered geometric progression <math display="inline">(b_k) = 1, 1, \frac{1}{4}, \frac{1}{4}, \frac{1}{16}, \frac{1}{16}, \ldots, 1/4^{\left\lfloor \frac{k}{2} \right\rfloor}, \ldots,</math> using the [[Floor_and_ceiling_functions|floor function]] <math display="inline">\lfloor x \rfloor</math> that gives the largest integer that is less than or equal to <math>x,</math> converges R-linearly to 0 with rate 1/2, but it does not converge Q-linearly; see the second plot of the figure below. The defining Q-linear convergence limits do not exist for this sequence because one subsequence of error quotients starting from odd steps converges to 1 and another subsequence of quotients starting from even steps converges to 1/4. When two subsequences of a sequence converge to different limits, the sequence does not itself converge to a limit. Generally, for any staggered geometric progression <math>(a r^{\lfloor k / m \rfloor})</math>, the sequence will not converge Q-linearly but will converge R-linearly with rate <math display="inline">\sqrt[m]{|r|}; </math> these examples demonstrate why the "R" in R-linear convergence is short for "root."

The sequence 
<math display="block">(c_k) = \frac{1}{2}, \frac{1}{4}, \frac{1}{16}, \frac{1}{256}, \frac{1}{65,\!536}, \ldots, \frac{1}{2^{2^k}}, \ldots</math>
converges to zero Q-superlinearly. In fact, it is quadratically convergent with a quadratic convergence rate of 1. It is shown in the third plot of the figure below.

Finally, the sequence 
<math display="block">(d_k) = 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{6}, \ldots, \frac{1}{k + 1}, \ldots</math>
converges to zero Q-sublinearly and logarithmically and its convergence is shown as the fourth plot of the figure below.

[[Image:ConvergencePlots.png|thumb|alt=Plot showing the different rates of convergence for the sequences ''a''<sub>''k''</sub>, ''b''<sub>''k''</sub>, ''c''<sub>''k''</sub> and ''d''<sub>''k''</sub>.|Log-linear plots of the example sequences ''a''<sub>''k''</sub>, ''b''<sub>''k''</sub>, ''c''<sub>''k''</sub>, and ''d''<sub>''k''</sub> that exemplify linear, linear, superlinear (quadratic), and sublinear rates of convergence, respectively.|600px|center]]

=== Convergence rates to fixed points of recurrent sequences ===
Recurrent sequences <math display="inline">x_{k+1}:=f(x_k)</math>, called [[Fixed-point iteration|fixed point iterations]], define discrete time autonomous [[Dynamical system|dynamical systems]] and have important general applications in mathematics through various [[fixed-point theorems]] about their convergence behavior. When ''f'' is [[continuously differentiable]], given a [[Fixed point (mathematics)|fixed point]] ''p'', <math display="inline">f(p)=p,</math> such that <math display="inline">|f'(p)| < 1</math>, the fixed point is an [[attractive fixed point]] and the recurrent sequence will converge at least linearly to ''p'' for any starting value <math>x_0</math> sufficiently close to ''p''. If <math>|f'(p)| = 0</math> and <math display="inline">|f''(p)| < 1</math>, then the recurrent sequence will converge at least quadratically, and so on. If <math>|f'(p)| > 1</math>, then the fixed point is a [[repulsive fixed point]] and sequences cannot converge to ''p'' from its immediate [[Neighbourhood (mathematics)|neighborhoods]], though they may still jump to ''p'' directly from outside of its local neighborhoods.

=== Order estimation ===
A practical method to calculate the order of convergence for a sequence generated by a fixed point iteration is to calculate the following sequence, which converges to the order <math>q</math>:<ref>{{cite web |last=Senning |first=Jonathan R. |title=Computing and Estimating the Rate of Convergence |url=http://www.math-cs.gordon.edu/courses/ma342/handouts/rate.pdf |access-date=2020-08-07 |website=gordon.edu}}</ref>
<math display="block">q \approx \frac{\log \left|\displaystyle\frac{x_{k+1} - x_k}{x_k - x_{k-1}}\right|}{\log \left|\displaystyle\frac{x_k - x_{k-1}}{x_{k-1} - x_{k-2}}\right|}.</math>

For numerical approximation of an exact value through a numerical method of order <math>q</math> see.<ref>{{cite web |last=Senning |first=Jonathan R. |title=Verifying Numerical Convergence Rates |url=https://www.csc.kth.se/utbildning/kth/kurser/DN2255/ndiff13/ConvRate.pdf |access-date=2024-02-09}}</ref>

=== Accelerating convergence rates ===
{{Main|Series acceleration}}
Many methods exist to accelerate the convergence of a given sequence, i.e., to [[sequence transformation|transform one sequence]] into a second sequence that converges more quickly to the same limit. Such techniques are in general known as "[[series acceleration]]" methods. These may reduce the [[computational cost|computational costs]] of approximating the limits of the original sequences. One example of series acceleration by sequence transformation is [[Aitken's delta-squared process]]. These methods in general, and in particular Aitken's method, do not typically increase the order of convergence and thus they are useful only if initially the convergence is not faster than linear: if <math>(x_k)</math> converges linearly, Aitken's method transforms it into a sequence <math>(a_k)</math> that still converges linearly (except for pathologically designed special cases), but faster in the sense that <math display="inline">\lim_{k \rightarrow \infty} (a_k-L)/(x_k-L)= 0</math>. On the other hand, if the convergence is already of order &ge; 2, Aitken's method will bring no improvement.