# Determining the Order of Convergence of Fixed Point Interation

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

• 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$. – 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$.
• 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$. – Delta-u Apr 26 '18 at 9:28
• Alright! Thank you! I would presume that in your first equation, it's supposed to be $o(x^{100})$ instead of $o(x^100)$? – David Apr 26 '18 at 9:33
• 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).$$ – LutzL Apr 26 '18 at 10:34