Vipul: Created page with "==Definition== The '''rate of convergence''' for a convergent sequence describes how quickly the terms of the sequence converge to the limit. We discuss some cases below...."

2014-04-26T16:18:14Z

Created page with "==Definition== The '''rate of convergence''' for a convergent sequence describes how quickly the terms of the sequence converge to the limit. We discuss some cases below...."

New page

==Definition==

The '''rate of convergence''' for a [[convergent sequence]] describes how quickly the terms of the sequence converge to the limit. We discuss some cases below.

For the definitions below, the sequence is <math>(x_n)_{n \in \mathbb{N}}</math> and the limit is <math>L</math>. In symbols, we have:

<math>\lim_{n \to \infty} x_n = L</math>

===Steadily linear, superlinear, and sublinear convergence===

Suppose the following holds:

<math>\lim_{n \to \infty} \frac{|x_{n+1} - L|}{|x_n - L|} = \mu</math>

Clearly, <math>\mu \in [0,1]</math> (if <math>\mu</math> were greater than 1, the sequence couldn't converge). We have three cases:

* <math>\mu \in (0,1)</math>, i.e., <math>0 < \mu < 1</math>: In this case, the sequence <math>(x_n)</math> converges to <math>L</math> linearly, and the constant <math>\mu</math> is called the rate of (linear) convergence. The use of the term "linear" signifies that the next error term <math>|x_{n+1} - L|</math> is approximately a ''linear'' function of the preceding error term <math>|x_n - L|</math>.
* <math>\mu = 0</math>: In this case, the sequence <math>(x_n)</math> converges to <math>L</math> ''super''linearly. In other words, a function that would approximate the behavior of the next error term in terms of the previous error term would decay faster than a linear function.
* <math>\mu = 1</math>: In this case, the sequence <math>(x_n)</math> converges to <math>L</math> ''sub''linearly. In other words, a function that would describe the next error term in terms of the previous one would decay slower than a linear function.

===Convergence of a power function form===

Suppose <math>q > 1</math> is a real number. We say that the sequence <math>(x_n)</math> converges to a limit <math>L</math> with [[order of convergence]] <math>q</math> if the following holds:

<math>\lim_{n \to \infty} \frac{|x_{n+1} - L|}{|x_n - L|^q} = \mu, \mu > 0</math>

In other words, if we were to try to construct a function that approximately predicted <math>|x_{n+1} - L|</math> in terms of <math>|x_n - L|</math>, the [[order of zero]] of a the function at zero would be <math>q</math>. Note that convergence of this form is superlinear.

Two special cases:

* <math>q = 2</math>, in which case we say the sequence '''converges quadratically''' or has '''quadratic convergence'''.
* <math>q = 3</math>, in which case we say the sequence '''converges cubically''' or has '''cubic convergence'''.

===Logarithmic convergence===

{{further|[[logarithmic convergence]]}}

If the sequence converges ''sublinearly'', and further:

<math>\lim_{n \to \infty} \frac{|x_{n+2} - x_{n+1}|}{|x_{n+1} - x_n|} = 1</math>

then we say that the convergence is ''logarithmic''. This use of terminology differs somewhat from the others, because it is ''not'' the case that we can use a logarithmic function to approximate the description of <math>|x_{n+1} - L|</math> in terms of <math>|x_n - L|</math>. (So what's the rationale of the term?)

===Non-steady convergence or R-convergence===

In some cases, the convergence of the sequence is not ''steadily'' of a certain type, but it still approximates that type.

We say that a sequence <math>(x_n)</math> has R-convergence of a particular type to a limit <math>L</math> if we can find a sequence <math>(\varepsilon_n)</math> such that, for all <math>n</math>:

<math>|x_n - L| < \varepsilon_n</math>

and the sequence <math>\varepsilon_n</math> has convergence to 0 of that type.

In particular, we can talk of R-linear convergence, R-superlinear convergence, R-sublinear convergence, R-quadratic convergence, R-logarithmic convergence, etc.

Rate of convergence - Revision history

Vipul: Created page with "==Definition== The '''rate of convergence''' for a convergent sequence describes how quickly the terms of the sequence converge to the limit. We discuss some cases below...."