2

How can I use the contraction mapping theorem to show there is a unique solution to $x=\cos x$ and get a reasonable estimation?

Im struggling to use the theorem in this particular case so any help will be great!

Siminore
  • 35,136
Raul
  • 938
  • Is this your contraction theorem? And what is domain of your function $\cos x$? – Cortizol Dec 03 '13 at 08:37
  • Raul, can you tell us a little bit about how you attempted to handle the question? I do believe not much acrobatics is require here to apply the fixed point theorem (I presume your complete domain would be $[0,1]$ with the standard metric?) – Jonathan Y. Dec 03 '13 at 08:59
  • 2
    The domain would have to be $[\epsilon, 1]$ in order to use the contraction theorem. – Dustan Levenstein Dec 03 '13 at 09:28

1 Answers1

4

Since $\cos(\mathbb{R}) = [-1,1]$, there is no fixed point outside $[-1,1]$, we can restrict to those $x \in [-1,1]$. Since $\cos([-1,1]) = [\cos 1,1]$, there is no fixed point outside $[\cos 1,1]$, we can restrict $x$ further. Let's just restrict $x$ to $[0,1]$.

For $x \ne y \in [0,1]$, we can apply mean value theorem to find a $\xi$ between $x$ and $y$ such that

$$|\cos x - \cos y| = |\sin \xi\cdot( x - y)| \le \sin 1| x - y|$$

Since $0 < \sin 1 < 1$, the map $x \mapsto \cos x$ is a contraction mapping when restricted to $[0,1]$. By contraction mapping theorem, the equation $x = \cos x$ has an unique fixed point in $[0,1]$ and hence over all $\mathbb{R}$.

Even contraction mapping theorem guarantee the existence of an unique fixed point. Direct iteration $x \mapsto \cos x$ will not be very efficient in locating the fixed point.

By brute force, one can check that $x = \cos x$ has a fixed point at $x_{f} \sim 0.73908513321516$.
Since the derivative of $\cos x$ at $x_{f}$ is $-\sin(x_f) \sim -0.67361202918321$ and $\left|\log_{10}(x_f)\right|$ $\sim 0.17159016592461$. If you start with a number close to $x_f$ and attempt to improve it by iteration, you need about 6 iterations to gain one more digit of accuracy.

If you insists on using contraction mapping to get an estimate of the fixed point, you need to rewrite it to make the scaling constant in the contraction mapping smaller. For example, if you rewrite $$x = \cos x \quad\longleftrightarrow\quad x = f(x) \stackrel{def}{=} \frac{3 \cos x + 2 x}{5}$$ You can check $x \mapsto f(x)$ is again an contraction mapping on $[0,1]$ with same fixed point $x_f$. However, with only 3 iterations of $f$, you already get an estimate

$$x_f \sim f(f(f(1))) \sim 0.73908508052689$$

which is accurate to order $10^{-7}$.

achille hui
  • 122,701
  • Direct iteration $x \mapsto \cos x$ will be effective in locating the fixed point. It may not be very efficient. I get convergence in 80 steps using double precision starting from $x_0=0$. – lhf Dec 03 '13 at 11:17
  • @lhf Thanks for pointing that out, efficient is a better term to describe the situation. – achille hui Dec 03 '13 at 11:23
  • It'd be nice if you could explain why you think
    direct iteration is not very efficient. Is it because $\sin(x^*)\approx 0.67$ is not very small?     – lhf Dec 03 '13 at 11:25
  • 1
    @lhf For this particular problem, direct iteration takes around 6 iterations to gain one decimal place in accuracy. It is okay in this case because evaluation of $\cos x$ is cheap. If the iteration is more expensive, one will want to reduce the number of iterations as much as possible. What I really want to point out is sometimes a simple rewrite of the equation allow one to cut down the computation cost significantly. – achille hui Dec 03 '13 at 11:36