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$$
Best Answer
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.