Assume that the fixed point iteration for computing the fixed point $p=0$ of the function $g(x) = cos(x^{50})-1$ converges. Determine the order of convergence.

We know the order of convergence is $\alpha$ if $\lim_{n\to\infty} \frac{|({p_{n+1}-p})|}{|p_n-p|^\alpha} = \lambda$ for some positive $\alpha$ and $\lambda$.

By applying Taylor's expansion, we obtain $g(x) = g(p) + (x-p)g(p) + \cdots+ \frac{(x-p)^n}{n!}g^{(n)}(p) + \cdots$

And applying it to the above definition, I guess that the order of convergence is 50. This is observed through differentiating the function ~50 times and finding that $g^{(50)}(p)$ is the first time $g^{(n)}(p) \neq 0$, but I have no idea on how to formalize this. Any help will be appreciated

  • $\begingroup$ I would like to comment that the flaw in my thought process could be due to the fact that the trigonometric term (without powers of $x^n$) after differentiating is $-50!\sin(x^{50})$, which equals to $0$ when $x=0$. Further differentiating it will probably introduce $\geq 2$ nonzero terms, which cancels out to $0$. $\endgroup$ – David Apr 26 '18 at 9:41

Near $x=0$ you have: $$\cos(x^{50})-1=\left(1-\frac{(x^{50})^2}{2}+o(x^{100}) \right)-1=-\frac{x^{100}}{2}+o(x^{100})$$ so if $p_n \to 0$ then: $$g(p_n) = -\frac{p_n^{100}}{2}+o(p_n^{100})$$ and so with $\alpha=100$ you have: $$\frac{|g(p_n)-0|}{|p_n-0|^{100}}=-\frac{1}{2}+o(1)$$ so the order of convergence to $0$ is $100$.

  • $\begingroup$ Thank you! If it isn't inappropriate, would you be able to explain the difference between Big-O and Little-O notation? $\endgroup$ – David Apr 26 '18 at 9:26
  • $\begingroup$ Let $f$ and $g$ be function and suppose that $g$ is never $0$. Then $f=O(g)$ if $\frac{f}{g}$ is bounded and $f=o(g)$ if $\frac{f}{g} \to 0$. $\endgroup$ – Delta-u Apr 26 '18 at 9:28
  • $\begingroup$ Alright! Thank you! I would presume that in your first equation, it's supposed to be $o(x^{100})$ instead of $o(x^100)$? $\endgroup$ – David Apr 26 '18 at 9:33
  • $\begingroup$ Yes, thank you, I will correct my answer :-). $\endgroup$ – Delta-u Apr 26 '18 at 9:34
  • 2
    $\begingroup$ Or more elementary use $\cos y-1=-2\sin^2y/2$ so that $$|g(x)|\le 2\min(\tfrac12x^{50},1)^2=\min(\tfrac12x^{100},2).$$ $\endgroup$ – LutzL Apr 26 '18 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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