# Banach's fixed point theorem in $\mathbb{R}$. Number of iterations needed to satisfy an error

Hey I am a quite puzzled by this question

The function $$f : [-\pi, \pi] \to [-\pi,\pi] ,~~ f(x)= \frac{\sin(x)}{2}$$ is a contraction. Hence the fixed point iteration $x_{k+1}= f(x_{k})$ starting from $x_{0}=\frac{\pi}{2} \in [-\pi , \pi]$ is converging to a fixed point $x^{*}$ How many iterations $k$ are at least necessary s.t. the error is guaranteed to satisfy $|x_{k}-x^{*}| \leq \frac{1}{1024}$

I have been starring at Banach's fixed point theorem for $\mathbb{R}$ which states that the error estimate is $$|x^{*}-x_{n}| \leq \frac{q^{n}}{1-q}|f(x_{0})-x_{0}|$$ where I believe that $q<1$ since it is a part of the contraction mapping definition.

So I can see that you have to find the number of iterations before you get close enough to the fixed point with the bound given in the inequality.

Unfortunately I am not sure even how to start this, any help would be appreciated

• Are you sure the formulation is "at least" and not "at most"? The error bound is just that, a bound, the actual error might be smaller resp. the error target might be reached in less steps. – LutzL May 14 '18 at 9:48

We have $q=1/2$, hence you have to determine $n$ such that
$\frac{q^{n}}{1-q}|f(x_{0})-x_{0}| \le \frac{1}{1024}$.
• how did you obtain $q= 1/2$? – user420309 May 14 '18 at 9:33
• is it because $\pi/2$ is starting point and $f(\pi/2)=1/2$? – user420309 May 14 '18 at 9:42
• @Djhoe : The Lipschitz constant (bound on the derivative) of the sine is $1$, thus the Lipschitz constant of $f$ is $1/2$. – LutzL May 14 '18 at 9:42
• The contraction constant is a Lipschitz constant. You can apply the mean value theorem to $\frac{|f(y)-f(x)|}{|y-x|}\le \sup |f'(z)|$ to calculate such a constant. – LutzL May 14 '18 at 9:53