# Rate of convergence of a sequence in $\mathbb{R}$ and Big O notation

From Wikipedia

$f(x) = O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that $|f(x)| \le \; M |g(x)|\mbox{ for all }x>x_0$.

Also from Wikipedia

Suppose that the sequence $\{x_k\}$ converges to the number $L$. We say that this sequence converges linearly to $L$, if there exists a number $μ ∈ (0, 1)$ such that $\lim_{k\to \infty} \frac{|x_{k+1}-L|}{|x_k-L|} = \mu$.

If the sequences converges, and

• $μ = 0$, then the sequence is said to converge superlinearly.
• $μ = 1$, then the sequence is said to converge sublinearly.

I was wondering

1. Is it true that if $\{x_n\}$ either linearly, superlinearly or sublinearly converges to $L$, only if $|x_{n+1}-L| = O(|x_n-L|)$? This is based on what I have understood from their definitions and viewing $\{ x_{n+1}-L \}$ and $\{ x_n-L \}$ as functions of $n$. Note that "only if" here means "if" may not be true, since $\mu$ may lie outside of $[0,1]$ and $\{x_n\}$ may not converge.
2. Some Optimization book says that the steepest descent algorithm has linear rate of convergence, and writes $|x_{n+1}-L| = O(|x_n-L|)$. Is the usage of big O notation here expanding the meaning of linear rate of convergence?

Thanks and regards!

-
Your question is not really about optimization, is it? Does it really matter where you saw this? Isn't this just a clarification of rate of convergence and BigO? – Aryabhata Feb 15 '12 at 18:57
@Aryabhata: I want to know if that particular optimization example uses correct notation in optimization community. I don't know if they have their different customs. – Tim Feb 15 '12 at 18:59
The page just before the one you linked to calls it 'standard'. Anyway, I will leave you alone :-) – Aryabhata Feb 15 '12 at 19:08
@Aryabhata: What page do you refer to? I have linked to three pages. – Tim Feb 15 '12 at 19:15
Page 29. Where it talks about quadratic convergence. Of course, the 'standard' might well be standard of the optimization community (but I highly doubt it). – Aryabhata Feb 15 '12 at 19:39

For (1), construct a sequence such that both $x_{2n}$ and $x_{2n+1}$ converge to $L$, but $x_{2n}$ converges much faster in such a way that $|x_{2n+1}-L|/|x_{2n}-L| \to \infty$.

For (2), note that $|x_{n+1}-L| = O(|x_n-L|)|$ only means that there exists a positive constant $c$ such that $|x_{n+1}-L| < c|x_n-L||$ for large enough $n$. Convergence means that $c < 1$.

More explicitly, if $|x_{n+1}-L| = 2|x_n-L|$ then $|x_{n+1}-L| = O(|x_n-L|)$, but $x_n$ certainly does not converge to $L$.

-
Thanks! Please see my update while you were compiling the reply. – Tim Feb 15 '12 at 18:42
Do you mean that When $|x_{n+1}−L|=O(|x_n−L|)|$, the sequence converges if and only if there exists a positive constant $c < 1$ such that $|x_{n+1}-L| < c|x_n-L||$ for large enough $n$? If yes, is it by the ratio test? – Tim Feb 15 '12 at 18:46
Thanks, Marty! I wonder what the example you gave in the first paragraph is for? I.e. the one "construct a sequence such that both $x_{2n}$ and $x_{2n+1}$ converge to $L$, but $x_{2n}$ converges much faster in such a way that $|x_{2n+1}−L|/|x_{2n}−L|→∞$." (1) Does such a sequence still converges, doesn't it? But the ratio test fails to work, because the ratio does not converges? (2) Does $|x_{n+1}-L| = O(|x_n-L|)$ not hold, does it? – Tim Feb 18 '12 at 0:49

To answer your added question, from the definition, $x_n$ converges to $L$ if and only if $|x_n-L| \to 0$ as $n \to \infty$.

The existence of a positive c such that $c < 1$ and $|x_{n+1}-L| \le c|x_n-L|$ is sufficient for convergence, but not necessary.

For example, if $x_n = 1/(\ln n)$, then $x_n \to 0$, but there is no $c < 1$ such that $x_{n+1} < c x_n$ for all large enough n.

It can be shown that there is no slowest rate of convergence - for any rate of convergence, a slower one can be constructed. This is sort of the inverse of constructing arbitrarily fast growing functions and can lead to many interesting places.

-