contraction point? This is an interesting question I saw in a book online:
Suppose that $g:\mathbb R \to $$\mathbb R$ is a contraction. Then $g$ has a unique
fixed point $c$ and that for any number $x_0$, the sequence $x_0, x_1, x_2,\ldots$ given by
$x_n = g(x_{n-1})$. converges to the fixed point. In certain situations, the speed of convergence may be faster than a rough estimate based only on the contraction constant would suggest.
To be concrete, suppose the fixed point is zero and the contaction constant
is $1/2$. That is, suppose that that $g:\mathbb R \to $$\mathbb R$ satisfies $g(0) = 0$ and that for all $a,b ∈  $$\mathbb R$, $|g(x)-g(y)|<1/2|x-y|$. Let $x_0$ $= 1$. The sequence $x_0, x_1, x_2,\ldots$ converges to $0.$  

(i) For what $n$ can you be certain that $|x_n|<10^{-100}$?

Here is my attempt:
$$ \vert x_n \vert < \frac{1}{2} \vert x_{n-1} \vert < \dots < \left ( \frac{1}{2} \right )^n \cdot \vert x_0 \vert$$
Still what is our n?

(ii) If we assume that $g'(0) = 0$ and $|g''(x)|<1$ the sequence ${x_n}\to\ 0$ faster. With these assumptions, for what n can you be certain that $|x_n|<10^{-100}$?

I suppose we could use this Theorem which would make $g'(x)$ a contraction:
Theorem: Suppose $g(x)$ is differentiable, and $|(g' (x))\leq\ Lambda < 1$. Then, $g(x)$ is a contraction.
Still what is our n?
Here is my attempt:
If you have a contraction $f$ with nondegenerate linear part, locally it "looks like" its linear part $f_1 = f'(0) x $. $f(x)$ is now like $f_2 (x) = f''(0)x^2$. So, these two are contractions in some neighbourhood of zero and their speed is faster than speed of linear contraction. 

(iii) If we assume that $g'(0) = 0$ and $|g(0)| = 0$, and $g'''(x)<1$, the sequence ${x_n} \to\ 0$ faster still. With these assumptions, for what $n$ can you be certain that $|x_n| < 100^{-100}$?

$f_3(x) = f'''(0) x^3$. So, these two are contractions (for ii and iii) in some neighbourhood of zero and their speed is faster than speed of linear contraction. 
Still what is our n?
I am trying to solve this problem, but I can not seem to get through it. I was reading Keller in Numerical Methods but he just assumes that things should be known without explanation. I really tried on this problem but have come to the point of exhaustion and frustration. I know if I see the solution I will understand it. Can someone please show me?
 A: So, in the first case $|x_n|<2^{-n}$. To ensure this is less than $10^{-100}$ we want to pick $n$ so that $2^{-n}<10^{-100}$. Which is, $-n \ln 2 < -100 \ln 10$, resulting in $n> 100 (\ln 10)/\ln 2$. Grabbing a calculator... $n> 332.19$. Since $n$ must be an integer, $333$ would be the answer. 
The logic of 2 and 3 is the same after you get the estimate for $|x_n|$. But the estimates are different. 
To estimate $|x_n|$ in  (ii), use the fact that $g'$ is a contraction: since $g'(0)=0$, this yields $|g'(x)|<|x|$ and after integration   $|g(x)|\le x^2/2$. Starting from $x_0=1$, you get 
$$|x_1|< 2^{-1},\quad |x_2|<2^{2(-1)-1} =2^{-3},\quad |x_3|<2^{2(-3)-1} \dots \tag1 $$
You can try to work out a formula for the exponents of $2$ by induction, but I would avoid such finesse and use the cruder bound $|g(x)|\le x^2$ starting with the second term: 
$$|x_2|< 2^{2(-1)}=2^{-2},\quad |x_3|<2^{2(-2)} =2^{-4},\quad |x_4|<2^{2(-4)}=2^{-8} \dots \tag2$$
hence $$|x_n|<2^{-2^{n-1}} \tag3$$
is the estimate that can be used to determine a suitable $n$. (Note: it will be a different value of $n$ from the one  we'd get by sweating through the computations in (1)).
In the third case $|g(x)|<|x|^3/6$. I would do $|x_1|<6^{-1}$ and after that just use  $|g(x)|<|x|^3$:
$$|x_2|< 6^{3(-1)}=6^{-3},\quad |x_3|<6^{3(-3)} =6^{-9},\quad |x_4|<6^{3(-9)}=6^{-27} \dots  $$
hence $$|x_n|<6^{-3^{n-1}} \tag4$$
Again, this is not the best estimate one could get (I ignored a factor of $1/6$ after the first step), but it captures the asymptotic behavior.
