Fixed-Point theorem: compute number of iterations

Question

I have the following function: $$f(x)=\exp(-x)-0.5x$$. I have to use fixed-point iteration to find the fixed point ($0.85$). I found $g(x)=\exp(-x)/0.5$ and wrote a small script to compute it. It works but now I have to show by hand the number of iterations required for convergence.

I did the following: $$ |g'(x)| \le k \le 1 \rightarrow 2\exp(-x), $$ which is bounded by $2$. How is this possible? It should be less than $1$ on $[0,1]$ but the script works even if I change the initial value. Thank you.

Answer 1

I guess that you want to solve $f(x)=0$ and for this you rewrite the equation as $$ g(x)=2\,e^{-x}=x. $$ It is clear that $g\colon[0,2]\to[0,2]$. Graphical analysis shows that there is a unique fixed point. Moreover, the iteration converges for any initial $x_0\ge0$.

To obtain an estimate of the number of iterations needed you want $|g'|<1$, but $$\sup_{0\le x\le2}|g'(x)|=2.$$ You should work on a smaller interval. Clearly $g'(\log2)=-1$. Since $g(\log2)=1$, an interval of the form $[\log2+\epsilon,1]$ should work.

Finally, let mi note that $k<1$ is a sufficient condition for convergence, but not necessary, as this example shows.

Answer 2

I suppose, you should reduce the interval, so you can have convergence. On $[0,1]$, you do not have a contracting map. In the interval $[-ln(0.4),1]$ (or a sub-interval of it), you can be sure that you have convergence (according to Banach fixed point theorem).

More specifically, you need to have a contracting map on your interval $I$ , which means

$|f(x)-f(y)|\leq q\times|x-y| \forall x,y\in I$

$0<q<1$

starting with the left hand side

$|f(x)-f(y)|=|e^{-x}-0.5x-e^{-y}+0.5y|<|e^{-x}-e^{-y}|+0.5|x-y|$

Now, the interval $I=[-ln(0.4),1]$ helps to have

$\frac{|e^{-x}-e^{-y}|}{|x-y|}<max_{z\in I}\{|\frac{\delta(e^{-z})}{\delta Z}|\}=max\{|e^{-z}|\}=0.4$

Therefore,

$|f(x)-f(y)|\leq |e^{-x}-e^{-y}|+0.5|x-y|<0.4|x-y|+0.5|x-y|=0.9|x-y|$