3
$\begingroup$

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!

  • 2
    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?2012-02-15
  • 0
    @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.2012-02-15
  • 0
    The page just before the one you linked to calls it 'standard'. Anyway, I will leave you alone :-)2012-02-15
  • 0
    @Aryabhata: What page do you refer to? I have linked to three pages.2012-02-15
  • 0
    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).2012-02-15
  • 0
    https://www.or-exchange.org/questions/4868/rates-of-convergence-of-optimization-algorithms @Tim are you the same guy?2018-01-27

2 Answers 2