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.

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!

share|improve this question
1  
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

2 Answers 2

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

share|improve this answer
    
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.

share|improve this answer

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.