Editing Rate of convergence (section)

==== 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" />