2
$\begingroup$

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

$\endgroup$
1
  • $\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, 2018 at 9:41

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
6
  • $\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, 2018 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, 2018 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, 2018 at 9:33
  • $\begingroup$ Yes, thank you, I will correct my answer :-). $\endgroup$
    – Delta-u
    Apr 26, 2018 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$
    – Lutz Lehmann
    Apr 26, 2018 at 10:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .