Given that $s$ is a solution to the equation $x = \arccos(x)$, and assuming that we start with $x_0 = 0.5$ we want to provide an estimate for the number of steps that are necessary until $|x_n - s| < 10^{-15}$.
How do I solve this problem? I have never really used fixed point iterations to do this..
On
If you compute with real iterations $x_{n+1} = \arccos(x_n)$, you will fail already in the second step, because $x_1=\arccos(0.5)= 1.0471975511965977,\; \arccos(x_1)=0.3060421086132657\times i$.
I explain an approximate solution for the iteration $x_{n+1} = \cos(x_n)$ with $x=0.5:$. The convergence is obviously linear, we can assume that the difference $|x_{n+1}-x_n|$ decreases by about one bit per step. $x=0.5$ has approximately 1 bit accuracy. We have $10^{-15} \approx 2^{-49.8},$ so we expect a priori convergence after about 49 steps. Actually the accuracy is already reached after 38 steps.
When you do fixed point iteration, you want the derivative of the right side to be less than $1$ in absolute value, which is not the case with your iteration. This is why your iteration fails. When you are close to the root, the error is multiplied by the first derivative at every step. If the first derivative is $d$ and the initial error is $e$, after $n$ steps the error will be about $ed^n$, so you want $ed^n \lt 10^{-15}$. Now you can solve for $n$.