Rate of convergence
• the speed at which a convergent sequence approaches its limit
• useful in finding out how much iteration is needed in algorithms to conjure an almost exact approximation
(like those discussed in Numerical Analysis, Newton-Rhapson, the Runge-Kutta,etc.)
Basic definitions
• Suppose that the sequence {xk} converges to the number L.We say that this sequence converges linearly to L, if there exists a number μ that is0 <μ< 1 such that
• The number μ is called the rate of convergence.
• If the rate of convergence is 0, then the sequence is said to convergesuperlinearly.
• If the rate of convergence is 1, then the sequence is said to converge sublinearly.
• The next definition is used to distinguish superlinear rates of convergence. We say that the sequence converges with order q to L for q>1if
•
In particular, convergence with orderq = 2 is called quadratic convergence; q = 3 is called cubic convergence,etc.This is sometimes called Q-linear convergence, Q-quadratic convergence, etc., to distinguish it from the definition below. The Q stands for "quotient," because the definition uses the quotient between two successive terms.
Extended definition
The drawback of the above definitions is that these do not catch some sequences which still converge reasonably fast, but whose "speed" is variable. Therefore, the definition of rate of convergence is sometimes extended as follows.
Under the new definition, the sequence {xk} converges with at least order q if there exists a sequence {εk} such that
and the sequence {εk} converges to zero with order q according to the above "simple" definition. To distinguish it from that definition, this is sometimes called R-linear convergence,R-quadratic convergence, etc. (with the R standing for "root").
Linear, Superlinear/Quadratic and sublinear rate of convergence.
Examples
Consider the following sequences:
The sequence {ak} converges linearly to 0 with rate 1/2.
The sequence {ck} converges superlinearly.
In fact, it is quadratically convergent. Finally, the sequence {dk} converges sublinearly.
More Examples
