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:

If we let $x = x_n$ and $y = 0$, then we see that, for every $n$ $$ \left|x_{n+1}\right| = \left|g(x_n) - g(0)\right| < \frac{1}{2}\left|x_n - 0\right| = \frac{1}{2}\left|x_n\right| $$

Can we also say that $|x_2| < 1/2|x_1| < 1/2^{2}$

(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}$?

(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}$?

I am trying to solve this problem, but I can not seem to get through it. I was reading the "Analysis of Numerical Methods" by Isaacson, but he just assumes that things should be known for a beginner. This has been very frustrating because I want to learn this particular problem, but what I was reading does not help. I really tried on this problem but have come to the point of exhaustion. I know if I see the solution I will understand it. Can someone please show me?


2 Answers 2


Your guess for first question is right, but you have to iterate this "to the end": $$ \vert x_n \vert < \frac{1}{2} \vert x_{n-1} \vert < \dots < \left ( \frac{1}{2} \right )^n \cdot \vert x_0 \vert$$ So after that you can choose appropriate number $n$.

Intuition behind second and third question is the following. If you have a contraction $f$ with nondegenerate linear part, locally it "looks like" its linear part $f_1 = f'(0) x $. "Looks like" means that $f(x) \sim f_1(x)$ in sense of calculus. When you have some degeneracy in linear terms or quadratic (I think that was meant in third question), locally $f(x)$ is now like $f_2 (x) = f''(0) x^2$ or $f_3(x) = f'''(0) x^3$. So, these two are contractions in some neighbourhood of zero and their speed is faster than speed of linear contraction. Beware that this estimate of contraction speed works only in some neighbourhood of zero. But it's not hard to say that after some finite amount of iteration the image of initial point will fall in this neighbourhood and then you can use more precise estimation.

  • $\begingroup$ I got the theory but do you have any idea what my n should be. Can you help me choose an n because I have been trying to work on this one problem for a while now until the point where I am just exhausted. $\endgroup$
    – 9599
    Commented Oct 9, 2013 at 4:35
  • $\begingroup$ Well, reiterating will help here too. Take for example $f_2 (x)$ and initial point $x_0$. It's not hard to see that $f^n_2(x_0) = (f''(0))^n \cdot x^{2n}_0$. Remember the neighbourhood? Let it be the segment $\lbrack -c,\; c \rbrack$. So, you see, that you have another exponential estimate like $f^n_2(x_0) < (f''(0))^n \cdot c^{2n}$. The same method that worked in question one will work here. $\endgroup$
    – Evgeny
    Commented Oct 9, 2013 at 4:41

Nice question by the way. It had me thinking. Your guess about the first part is correct somewhat. The second and third question I assume would be the same.

For part (i) you could have $|x_2|$ $<$ $1/2$ $|x_1|$ $<$ $1/2^{2}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .