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

  • $\begingroup$ 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. $\endgroup$ – 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}$.

  • $\begingroup$ how did you obtain $q= 1/2$? $\endgroup$ – user420309 May 14 '18 at 9:33
  • $\begingroup$ is it because $\pi/2$ is starting point and $f(\pi/2)=1/2$? $\endgroup$ – user420309 May 14 '18 at 9:42
  • $\begingroup$ @Djhoe : The Lipschitz constant (bound on the derivative) of the sine is $1$, thus the Lipschitz constant of $f$ is $1/2$. $\endgroup$ – LutzL May 14 '18 at 9:42
  • $\begingroup$ Unfortunately we didn't cover the lipschitz constant, the only prerequisite I have for this question is the contraction mapping including definition and lemma, whereas q is defined to be strictly smaller than 1 $\endgroup$ – user420309 May 14 '18 at 9:46
  • 1
    $\begingroup$ 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. $\endgroup$ – LutzL May 14 '18 at 9:53

Your Answer

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