Rate of convergence#quadratic convergence

Suppose that the sequence $(x\_k)$ of iterates of an iterative method converges to the limit number $L$ as $k\; \backslash rightarrow\; \backslash infty$. The sequence is said to converge with order $q$ to $L$ and with a rate of convergence $\backslash mu$ if the $k\; \backslash rightarrow\; \backslash infty$ limit of quotients of absolute differences of sequential iterates $x\_k,\; x\_\{k+1\}$ from their limit $L$ satisfies

$$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash frac$$

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 $(b\_k)\; =\; 1,\; 1,\; 1/4,\; 1/4,\; 1/16,\; 1/16,\; \backslash ldots,\; 1/4^\{\backslash left\backslash lfloor\; \backslash frac\{k\}\{2\}\; \backslash right\backslash rfloor\},\; \backslash ldots$ detailed below (where $\backslash lfloor\; x\; \backslash rfloor$ is the floor function applied to $x$). 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."{{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}}{{rp|620}} A sequence $(x\_k)$ that converges to $L$ is said to converge at least R-linearly if there exists an error-bounding sequence $(\backslash varepsilon\_k)$ such that $$

|x_k - L|\le\varepsilon_k\quad\text{for all }k

and $(\backslash varepsilon\_k)$ converges Q-linearly to zero; analogous definitions hold for R-superlinear convergence, R-sublinear convergence, R-quadratic convergence, and so on.

Any error bounding sequence $(\backslash varepsilon\_k)$ 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 $q$ converge more quickly and those with smaller rates $\backslash mu$ converge more quickly for a given order, so these greatest-rate-lower-bound error-upper-bound sequences are those that have the greatest possible $q$ and the smallest possible $\backslash mu$ given that $q$.

For the example $(b\_k)$ given above, the tight bounding sequence $(\backslash varepsilon\_k)\; =\; 2,\; 1,\; 1/2,\; 1/4,\; 1/8,\; 1/16,\; \backslash ldots,\; 1/2^\{k\; -\; 1\},\; \backslash ldots$converges Q-linearly with rate 1/2, so $(b\_k)$ converges R-linearly with rate 1/2. Generally, for any staggered geometric progression $(a\; r^\{\backslash lfloor\; k\; /\; m\; \backslash rfloor\})$, the sequence will not converge Q-linearly but will converge R-linearly with rate $\backslash sqrt[m]$

The geometric progression $(a\_k)\; =\; 1,\; \backslash frac\{1\}\{2\},\; \backslash frac\{1\}\{4\},\; \backslash frac\{1\}\{8\},\; \backslash frac\{1\}\{16\},\; \backslash frac\{1\}\{32\},\; \backslash ldots,\; 1/\{2^k\},\; \backslash dots$ converges to $L\; =\; 0$. Plugging the sequence into the definition of Q-linear convergence (i.e., order of convergence 1) shows that

$$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash frac\{\backslash left|\; 1/2^\{k+1\}\; -\; 0\backslash right|\}\{\backslash left|\; 1/\; 2^k\; -\; 0\; \backslash right|\}\; =\; \backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash frac\{2^k\}\{2^\{k+1\}\}\; =\; \backslash frac\{1\}\{2\}.$$

Thus $(a\_k)$ converges Q-linearly with a convergence rate of $\backslash mu\; =\; 1/2$; see the first plot of the figure below.

More generally, for any initial value $a$ in the real numbers and a real number common ratio $r$ between -1 and 1, a geometric progression $(a\; r^k)$ converges linearly with rate $|r|$ and the sequence of partial sums of a geometric series $(\backslash sum\_\{n=0\}^k\; ar^n)$ also converges linearly with rate $|r|$. The same holds also for geometric progressions and geometric series parameterized by any complex numbers

The staggered geometric progression $(b\_k)\; =\; 1,\; 1,\; \backslash frac\{1\}\{4\},\; \backslash frac\{1\}\{4\},\; \backslash frac\{1\}\{16\},\; \backslash frac\{1\}\{16\},\; \backslash ldots,\; 1/4^\{\backslash left\backslash lfloor\; \backslash frac\{k\}\{2\}\; \backslash right\backslash rfloor\},\; \backslash ldots,$ using the floor function $\backslash lfloor\; x\; \backslash rfloor$ that gives the largest integer that is less than or equal to $x,$ 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 $(a\; r^\{\backslash lfloor\; k\; /\; m\; \backslash rfloor\})$, the sequence will not converge Q-linearly but will converge R-linearly with rate $\backslash sqrt[m]$

The sequence

$$(c\_k)\; =\; \backslash frac\{1\}\{2\},\; \backslash frac\{1\}\{4\},\; \backslash frac\{1\}\{16\},\; \backslash frac\{1\}\{256\},\; \backslash frac\{1\}\{65,\backslash !536\},\; \backslash ldots,\; \backslash frac\{1\}\{2^\{2^k\}\},\; \backslash ldots$$

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

$$(d\_k)\; =\; 1,\; \backslash frac\{1\}\{2\},\; \backslash frac\{1\}\{3\},\; \backslash frac\{1\}\{4\},\; \backslash frac\{1\}\{5\},\; \backslash frac\{1\}\{6\},\; \backslash ldots,\; \backslash frac\{1\}\{k\; +\; 1\},\; \backslash ldots$$

converges to zero Q-sublinearly and logarithmically and its convergence is shown as the fourth plot of the figure below.

Image:ConvergencePlots.png

Recurrent sequences $x\_\{k+1\}:=f(x\_k)$, called fixed point iterations, define discrete time autonomous 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 p, $f(p)=p,$ such that , the fixed point is an attractive fixed point and the recurrent sequence will converge at least linearly to p for any starting value $x\_0$ sufficiently close to p. If $|f\text{'}(p)|\; =\; 0$ and $|f$(p)| < 1, then the recurrent sequence will converge at least quadratically, and so on. If $|f\text{'}(p)|\; >\; 1$, then the fixed point is a repulsive fixed point and sequences cannot converge to p from its immediate neighborhoods, though they may still jump to p'' directly from outside of its local neighborhoods.

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 $q$:{{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}}

$$q\; \backslash approx\; \backslash frac\{\backslash log\; \backslash left|\backslash displaystyle\backslash frac\{x\_\{k+1\}\; -\; x\_k\}\{x\_k\; -\; x\_\{k-1\}\}\backslash right|\}\{\backslash log\; \backslash left|\backslash displaystyle\backslash frac\{x\_k\; -\; x\_\{k-1\}\}\{x\_\{k-1\}\; -\; x\_\{k-2\}\}\backslash right|\}.$$

For numerical approximation of an exact value through a numerical method of order $q$ see.{{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}}

{{Main|Series acceleration}}

Many methods exist to accelerate the convergence of a given sequence, i.e., to 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 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 $(x\_k)$ converges linearly, Aitken's method transforms it into a sequence $(a\_k)$ that still converges linearly (except for pathologically designed special cases), but faster in the sense that $\backslash lim\_\{k\; \backslash rightarrow\; \backslash infty\}\; (a\_k-L)/(x\_k-L)=\; 0$. On the other hand, if the convergence is already of order ≥ 2, Aitken's method will bring no improvement.

{{more citations needed section|date=August 2020}}

A sequence of discretized approximations $(y\_k)$ of some continuous-domain function $S$ that converges to this target, together with a corresponding sequence of discretization scale parameters $(h\_k)$ that converge to 0, is said to have asymptotic order of convergence $q$ and asymptotic rate of convergence $\backslash mu$ if

$$\backslash lim\; \_\{k\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{\backslash left|y\_k\; -\; S\backslash right|\}\{h\_k^\{q\}\}=\backslash mu,$$

for some positive constants $\backslash mu$ and $q$ and using $|x|$ to stand for an appropriate distance metric on the space of solutions, most often either the uniform norm, the absolute difference, or the Euclidean distance. Discretization scale parameters may be spacings of a regular grid in space or in time, the inverse of the number of points of a grid in one dimension, an average or maximum distance between points in a polygon mesh, the single-dimension spacings of an irregular sparse grid, or a characteristic quantum of energy or momentum in a quantum mechanical basis set.

When all the discretizations are generated using a single common method, it is common to discuss the asymptotic rate and order of convergence for the method itself rather than any particular discrete sequences of discretized solutions. In these cases one considers a single abstract discretized solution $y\_h$ generated using the method with a scale parameter $h$ and then the method is said to have asymptotic order of convergence $q$ and asymptotic rate of convergence $\backslash mu$ if

$$\backslash lim\; \_\{h\; \backslash rightarrow\; 0\}\; \backslash frac\{\backslash left|y\_h\; -\; S\backslash right|\}\{h^\{q\}\}=\backslash mu,$$

again for some positive constants $\backslash mu$ and $q$ and an appropriate metric $|x|.$ This implies that the error of a discretization asymptotically scales like the discretization's scale parameter to the $q$ power, or $\backslash left|y\_h\; -\; S\; \backslash right|\; =\; O(h^\{q\})$ using asymptotic big O notation. More precisely, it implies the leading order error is $\backslash mu\; h^\{q\},$ which can be expressed using asymptotic small o notation as$\backslash left|y\_h\; -\; S\backslash right|\; =\; \backslash mu\; h^\{q\}\; +\; o(h^\{q\}).$

In some cases multiple rates and orders for the same method but with different choices of scale parameter may be important, for instance for finite difference methods based on multidimensional grids where the different dimensions have different grid spacings or for finite element methods based on polygon meshes where choosing either average distance between mesh points or maximum distance between mesh points as scale parameters may imply different orders of convergence. In some especially technical contexts, discretization methods' asymptotic rates and orders of convergence will be characterized by several scale parameters at once with the value of each scale parameter possibly affecting the asymptotic rate and order of convergence of the method with respect to the other scale parameters.

Consider the ordinary differential equation

:$\backslash frac\{dy\}\{dx\}\; =\; -\backslash kappa\; y$

with initial condition $y(0)\; =\; y\_0$. We can approximate a solution to this one-dimensional equation using a sequence $(y\_n)$ applying the forward Euler method for numerical discretization using any regular grid spacing $h$ and grid points indexed by $n$ as follows:

:$\backslash frac\{y\_\{n+1\}\; -\; y\_n\}\{h\}\; =\; -\backslash kappa\; y\_\{n\},$

which implies the first-order linear recurrence with constant coefficients

:$y\_\{n+1\}\; =\; y\_n(1\; -\; h\backslash kappa).$

Given $y(0)\; =\; y\_0$, the sequence satisfying that recurrence is the geometric progression

$$y\_\{n\}\; =\; y\_0(1\; -\; h\backslash kappa)^n\; =\; y\_0\backslash left(1\; -\; nh\backslash kappa\; +\; \backslash frac\{n(n-1)\}\{2\}h^2\backslash kappa^2\; +\; ....\backslash right).$$

The exact analytical solution to the differential equation is $y\; =\; f(x)\; =\; y\_0\backslash exp(-\backslash kappa\; x)$, corresponding to the following Taylor expansion in $nh\backslash kappa$:

$$f(x\_n)\; =\; f(nh)\; =\; y\_0\backslash exp(-\backslash kappa\; nh)$$

= y_0\left(1 - nh\kappa + \frac{n^2 h^2\kappa^2}{2} + ...\right).

Therefore the error of the discrete approximation at each discrete point is

:$$|y\_n\; -\; f(x\_n)|\; =\; \backslash frac\{nh^2\backslash kappa^2\}\{2\}\; +\; \backslash ldots$$

For any specific $x\; =\; p$, given a sequence of forward Euler approximations $((y\_n)\_k)$, each using grid spacings $h\_k$ that divide $p$ so that $n\_\{p,k\}\; =\; p/h\_k$, one has

$$\backslash lim\_\{h\_k\; \backslash rightarrow\; 0\}\; \backslash frac$$

for any sequence of grids with successively smaller grid spacings $h\_k$. Thus $((y\_n)\_k)$ converges to $f(x)$ pointwise with a convergence order $q\; =\; 1$ and asymptotic error constant $p\; \backslash kappa^2\; /\; 2$ at each point $p\; >\; 0.$ Similarly, the sequence converges uniformly with the same order and with rate $L\; \backslash kappa^2\; /\; 2$ on any bounded interval of $p\; \backslash leq\; L$, but it does not converge uniformly on the unbounded set of all positive real values, $[0,\; \backslash infty).$

In asymptotic analysis in general, one sequence $(a\_k)\_\{k\; \backslash in\; \backslash mathbb\{N\}\}$ that converges to a limit $L$ is said to asymptotically converge to $L$ with a faster order of convergence than another sequence $(b\_k)\_\{k\; \backslash in\; \backslash mathbb\{N\}\}$ that converges to $L$ in a shared metric space with distance metric $|\backslash cdot|,$ such as the real numbers or complex numbers with the ordinary absolute difference metrics, if

$$\backslash lim\; \_\{k\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{\backslash left|a\_k\; -\; L\backslash right|\}$$

the two are said to asymptotically converge to $L$ with the same order of convergence if

$$\backslash lim\_\{k\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{\backslash left|a\_k\; -\; L\backslash right|\}$$

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

$$\backslash lim\_\{k\; \backslash rightarrow\; \backslash infty\}\; \backslash frac\{\backslash left|a\_k\; -\; L\backslash right|\}$$

These comparative definitions of rate and order of asymptotic convergence are fundamental in asymptotic analysis.{{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}}{{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}} For the first two of these there are associated expressions in asymptotic O notation: the first is that $a\_k\; -\; L\; =\; o(b\_k\; -\; L)$ in small o notation{{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}} and the second is that $a\_k\; -\; L\; =\; \backslash Theta(b\_k\; -\; L)$ in Knuth notation.{{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}} The third is also called asymptotic equivalence, expressed $a\_k\; -\; L\; \backslash sim\; b\_k\; -\; L.${{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}}{{SpringerEOM|id=Asymptotic_equality|title=Asymptotic equality}}

For any two geometric progressions $(a\; r^k)\_\{k\; \backslash in\; \backslash mathbb\{N\}\}$ and $(b\; s^k)\_\{k\; \backslash in\; \backslash mathbb\{N\}\},$ with shared limit zero, the two sequences are asymptotically equivalent if and only if both $a\; =\; b$ and $r\; =\; s.$ They converge with the same order if and only if $r\; =\; s.$ $(a\; r^k)$ converges with a faster order than $(b\; s^k)$ if and only if 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 $k,$ $(a\; k^\{-n\})\_\{k\; \backslash in\; \backslash mathbb\{N\}\}$ and $(b\; k^\{-m\})\_\{k\; \backslash in\; \backslash mathbb\{N\}\},$ with shared limit zero, the two sequences are asymptotically equivalent if and only if both $a\; =\; b$ and $n\; =\; m.$ They converge with the same order if and only if $n\; =\; m.$ $(a\; k^\{-n\})$ converges with a faster order than $(b\; k^\{-m\})$ if and only if $n\; >\; m.$

For any sequence $(a\_k)\_\{k\; \backslash in\; \backslash mathbb\{N\}\}$ with a limit of zero, its convergence can be compared to the convergence of the shifted sequence $(a\_\{k-1\})\_\{k\; \backslash in\; \backslash mathbb\{N\}\},$ rescalings of the shifted sequence by a constant $\backslash mu,$ $(\backslash mu\; a\_\{k-1\})\_\{k\; \backslash in\; \backslash mathbb\{N\}\},$ and scaled $q$-powers of the shifted sequence, $(\backslash mu\; a\_\{k-1\}^q)\_\{k\; \backslash in\; \backslash mathbb\{N\}\}.$ 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 $(|x\_k\; -\; L|)\_\{k\; \backslash in\; \backslash mathbb\{N\}\}$ is asymptotically equivalent to the shifted, exponentiated, and rescaled sequence of iterate errors $(\backslash mu\; |x\_\{k-1\}\; -\; L|^q)\_\{k\; \backslash in\; \backslash mathbb\{N\}\},$ it is said to converge with order $q$ and rate $\backslash mu.$

{{more citations needed section|date=October 2024}}

Non-asymptotic rates of convergence do not have the common, standard definitions that asymptotic rates of convergence have. Among formal techniques, Lyapunov theory is one of the most powerful and widely applied frameworks for characterizing and analyzing non-asymptotic convergence behavior.

For iterative methods, one common practical approach is to discuss these rates in terms of the number of iterates or the computer time required to reach close neighborhoods of a limit from starting points far from the limit. The non-asymptotic rate is then an inverse of that number of iterates or computer time. In practical applications, an iterative method that required fewer steps or less computer time than another to reach target accuracy will be said to have converged faster than the other, even if its asymptotic convergence is slower. These rates will generally be different for different starting points and different error thresholds for defining the neighborhoods. It is most common to discuss summaries of statistical distributions of these single point rates corresponding to distributions of possible starting points, such as the "average non-asymptotic rate," the "median non-asymptotic rate," or the "worst-case non-asymptotic rate" for some method applied to some problem with some fixed error threshold. These ensembles of starting points can be chosen according to parameters like initial distance from the eventual limit in order to define quantities like "average non-asymptotic rate of convergence from a given distance."

For discretized approximation methods, similar approaches can be used with a discretization scale parameter such as an inverse of a number of grid or mesh points or a Fourier series cutoff frequency playing the role of inverse iterate number, though it is not especially common. For any problem, there is a greatest discretization scale parameter compatible with a desired accuracy of approximation, and it may not be as small as required for the asymptotic rate and order of convergence to provide accurate estimates of the error. In practical applications, when one discretization method gives a desired accuracy with a larger discretization scale parameter than another it will often be said to converge faster than the other, even if its eventual asymptotic convergence is slower.

{{Reflist}}

{{Differential equations topics}}

Category:Numerical analysis

Convergence