Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to understand what is the difference between 'rate of convergence' and 'order of convergence'. Does anyone know an intuitive explanation of the difference between them?

For example, say I have the sequence defined by $(1 + 1/n^2)$, $n>=1$

So it looks like $2, 1\frac{1}{4}, 1 \frac{1}{9}, 1 \frac{1}{16},...$

And has a limit of $1$ as n approaches infinity. So what is the rate of convergence and order of convergence for this example?

And how does that sequence tie in with the convergence equation (Wikipedia - Convergence speed for iterative methods) -

$$\lim_{k\to\infty} \frac{|x_{k+1} - L|}{|x_k - L|^q} = μ | μ > 0$$

share|improve this question
add comment

1 Answer 1

Following the relevant Wikipedia article, note that the rate of convergence is the number $\mu\in (0,1)$ such that

$$\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_k - L|} = \mu $$

provided such a $\mu$ exists and $\{x_k\}$ converges to L. If this holds, $\{x_k\}$ is said to converge linearly to L. Note that the rate of convergence only exists if $\{x_k\}$ converges linearly to L!

But what if the above limit exists and equals $0$? Then $\{x_k\}$ is said to converge superlinearly.

Order of convergence is an additional definition use to distinguish between sequences that converge superlinearly. Such a sequence $\{x_k\}$ has order of convergence q if

$$\lim_{k \to \infty} \frac{|x_{k+1} - L|}{|x_k - L|^q} = C\:,\textrm{ for }\:q>1$$

Given that $C$ is a positive constant, and $\{x_k\}$ converges to L. This is the equation you have included in your question. $q$ need not be an integer, as in the case of the secant method, where q is in fact the golden ratio $\approx 1.618$.

The best intuitive explanation that I can give is that rate of convergence and order of convergence are two numbers used to describe the speed of different kinds of convergence. A sequence has either a rate of convergence (if the convergence is linear) or an order of convergence (if the convergence is superlinear), and not both. The higher the rate/order, the faster the convergence.

The sequence you provide converges via the first limit to $1$ (work it out!), so it has neither a rate of convergence nor an order of convergence.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.