Editing Rate of convergence (section)

{{Short description|Speed of convergence of a mathematical sequence}}
{{Differential equations}}

In [[mathematical analysis]], particularly [[numerical analysis]], the '''rate of convergence''' and '''order of convergence''' of a [[sequence]] that converges to a [[Limit of a sequence|limit]] are any of several characterizations of how quickly that sequence approaches its limit. These are broadly divided into rates and orders of convergence that describe how quickly a sequence further approaches its limit once it is already close to it, called [[Asymptotic analysis|asymptotic]] rates and orders of convergence, and those that describe how quickly sequences approach their limits from starting points that are not necessarily close to their limits, called non-asymptotic rates and orders of convergence.  

Asymptotic behavior is particularly useful for deciding when to stop a sequence of numerical computations, for instance once a target precision has been reached with an iterative [[root-finding algorithm]], but pre-asymptotic behavior is often crucial for determining whether to begin a sequence of computations at all, since it may be impossible or impractical to ever reach a target precision with a poorly chosen approach. Asymptotic rates and orders of convergence are the focus of this article.  

In practical numerical computations, asymptotic rates and orders of convergence follow two common conventions for two types of sequences: the first for sequences of iterations of an [[Iterative method|iterative numerical method]] and the second for sequences of successively more accurate numerical [[Discretization|discretizations]] of a target. In formal mathematics, rates of convergence and orders of convergence are often described comparatively using [[asymptotic notation]] commonly called "[[big O notation]]," which can be used to encompass both of the prior conventions; this is an application of [[asymptotic analysis]]. 

For iterative methods, a sequence <math>(x_k)</math> that converges to <math>L</math> is said to have asymptotic ''order of convergence'' <math>q \geq 1</math> and asymptotic ''rate of convergence'' <math>\mu</math> if 
:<math>\lim _{k \rightarrow \infty} \frac{\left|x_{k+1}-L\right|}{\left|x_{k}-L\right|^{q}}=\mu.</math><ref name=":0">{{Cite book |last1=Nocedal |first1=Jorge |title=Numerical Optimization |last2=Wright |first2=Stephen J. |publisher=Springer |year=1999 |isbn=978-0-387-98793-4 |edition=1st |location=New York, NY |pages=28–29}}</ref>
Where methodological precision is required, these rates and orders of convergence are known specifically as the rates and orders of Q-convergence, short for quotient-convergence, since the limit in question is a quotient of error terms.<ref name=":0" /> The rate of convergence <math>\mu</math> may also be called the ''asymptotic error constant'', and some authors will use ''rate'' where this article uses ''order.''<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> [[Series acceleration]] methods are techniques for improving the rate of convergence of the sequence of partial sums of a [[Series (mathematics)|series]] and possibly its order of convergence, also.  

Similar concepts are used for sequences of discretizations. For instance, ideally the solution of a [[differential equation]] discretized via a [[regular grid]] will converge to the solution of the continuous equation as the grid spacing goes to zero, and if so the asymptotic rate and order of that convergence are important properties of the gridding method. A sequence of approximate grid solutions <math>(y_k)</math> of some problem that converges to a true solution <math>S</math> with a corresponding sequence of regular grid spacings <math>(h_k)</math> that converge to 0 is said to have asymptotic ''order of convergence'' <math>q</math> and asymptotic ''rate of convergence'' <math>\mu</math> if

<math display="block">\lim _{k \rightarrow \infty} \frac{\left|y_k - S\right|}{h_k^{q}}=\mu,</math>

where the absolute value symbols stand for a [[Metric (mathematics)|metric]] for the space of solutions such as the [[uniform norm]]. Similar definitions also apply for non-grid discretization schemes such as the [[Polygon mesh|polygon meshes]] of a [[finite element method]] or the [[Basis set (chemistry)|basis sets]] in [[computational chemistry]]: in general, the appropriate definition of the asymptotic rate <math>\mu</math> will involve the asymptotic limit of the ratio of an approximation error term above to an asymptotic order <math>q</math> power of a discretization scale parameter below.

In general, comparatively, one sequence <math>(a_k)</math> that converges to a limit <math>L_a</math> is said to asymptotically converge more quickly than another sequence <math>(b_k)</math> that converges to a limit <math>L_b</math> if 

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

and the two are said to asymptotically converge with the same order of convergence if the limit is any positive finite value. The two are said to be asymptotically equivalent if the limit is equal to one. These comparative definitions of rate and order of asymptotic convergence are fundamental in asymptotic analysis and find wide application in mathematical analysis as a whole, including numerical analysis, [[real analysis]], [[complex analysis]], and [[functional analysis]].