Rate of convergence

From Calculus
(Redirected from Order of convergence)
Jump to: navigation, search

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 (x_n)_{n \in \mathbb{N}} and the limit is L. In symbols, we have:

\lim_{n \to \infty} x_n = L

Steadily linear, superlinear, and sublinear convergence

Suppose the following holds:

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

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

  • \mu \in (0,1), i.e., 0 < \mu < 1: In this case, the sequence (x_n) converges to L linearly, and the constant \mu is called the rate of (linear) convergence. The use of the term "linear" signifies that the next error term |x_{n+1} - L| is approximately a linear function of the preceding error term |x_n - L|.
  • \mu = 0: In this case, the sequence (x_n) converges to L superlinearly. 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.
  • \mu = 1: In this case, the sequence (x_n) converges to L sublinearly. 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 q > 1 is a real number. We say that the sequence (x_n) converges to a limit L with order of convergence q if the following holds:

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

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

Two special cases:

  • q = 2, in which case we say the sequence converges quadratically or has quadratic convergence.
  • q = 3, in which case we say the sequence converges cubically or has cubic convergence.

Logarithmic convergence

For further information, refer: logarithmic convergence

If the sequence converges sublinearly, and further:

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

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 |x_{n+1} - L| in terms of |x_n - L|. (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 (x_n) has R-convergence of a particular type to a limit L if we can find a sequence (\varepsilon_n) such that, for all n:

|x_n - L| < \varepsilon_n

and the sequence \varepsilon_n 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.