1
$\begingroup$

I am having a hard time understanding this proof (leading up to Newtons method) about why a sequence must converge. English is not my native language so I will do my best to use the correct mathematical terms.

Theorem: Suppose that a Function $f(x)$ has the property $f(x) = x$ Suppose that this function also has the property of being differentiable in the interval $I$ and that there is a root $a$ to $f(x) = x$ in $I$. Further suppose that:

(1) There is a number $c < 1 $ & $|f'(x)| < c$ when $x \in I$

(2) $f$ "mirrors" the interval $I$ in itself.

then $a$ is the only root to $I$ and $x_n = f(x_{n-1})$ converge towards $a$ for every $x_o$ in $I$.


Now what is should be proved is:

When only (1) is true on $f'$ the sequence will still converge if you start close enough to the root we are searching for. More precisely:

(1) is true and the root $a$ is localized to a subinterval $I_1 = ]a-\delta, a+\delta[$ of $I$ which is small enough that the interval $I_2 = ]a-3\delta, a+3\delta[$ is also contained within $I$.

Then the recursion sequence $x_n = f(x_{n-1})$ converge for every start value $x_o$ in $I_1$


In my book they prove this by saying:

Let $I' = [a-2\delta, a+2\delta]$ then $I_1 \subseteq I' \subseteq I_2$. $f$ will then "mirror" the interval $I'$ in itself. If $x \in I'$ then:

$|f(x) - a| = |f(x) - f(a)| = f'(\xi)(x-a) \le c|x-a|$

This makes that $f(x) \in I'$. According to the theorem this will make the $x_n = f(x_{n-1})$ converge for each $x_o$ in $I'$ and especially for each $x_o \in I_1$.

If someone could explain the proof to me I would be very happy! Thank you for your time!

  • 0
    For (2) above: I'm wondering if you mean the image of $f$ is $I$, and/or $f: I \to I$, with $f$ being onto $I$?2012-11-04
  • 0
    I've changed [tag:algebra] tag to [tag:algebra-precalculus], since we don't use algebra tag anymore, see [meta](http://meta.math.stackexchange.com/questions/473/the-use-of-the-algebra-tag/3081#3081) for details.2012-11-04
  • 0
    @Julian that seems to deprecate the level of this question. I'd say either "calculus" or "real analysis"?2012-11-04
  • 0
    I am struggling with the translation here. But another way of putting it is that: $f$ makes the image of the interval $I$ into itself. Is that more clear?2012-11-04
  • 0
    @amWhy: Let’s just say both.2012-11-04
  • 0
    @Lukas: Yes, it does. You’re saying that $f[I]\subseteq I$, yes? (By the way, where you have *derivable* the correct word is *differentiable*.)2012-11-04
  • 0
    Yes that would be it.2012-11-04
  • 0
    @amWhy Sorry, just looked at the question and saw that it is not abstract-algebra.2012-11-04
  • 0
    @LukasArvidsson: If $x \in [0,1)$, can you see why $x^n \to 0$? Try an find an 'error estimate' for $f(f(...(f(x))...))$.2012-11-04
  • 0
    I assume that Property (2) just means $f(I) \subset I$ so the iteration stays in the region for which Property (1) applies.2012-11-04
  • 0
    I understand why $x^n \rightarrow 0$ What I don't understand is how they prove the usefulness of the specific intervals $I_1, I', I_2$2012-11-04
  • 0
    I don't either. Having $|f'(x)|\leq c < 1$ and $f(I) \subset I$ is sufficient to show both uniqueness and convergence. The point here is that $f$ is a contraction map, ie, $|f(x)-f(y)| \leq c |x-y|$ with $c<1$.2012-11-04
  • 0
    I am sorry I forgot to add in the section "Now what should be proved is" is that only (1) is true not (2). And with the proof they try get around that "problem"2012-11-04
  • 0
    Well, now I don't really follow the details, but then I would guess that the whole point is to find an interval $I'$ so that $f(I') \subset I'$ on which $f$ is a contraction. I assume they are leading up to Newton's method?2012-11-04
  • 0
    Yes that would be it as far as I understand. Yes newtons is a just a page away :)2012-11-04
  • 0
    Do you see that if $f(I') \subset I'$ (I' a closed interval) and $|f'(x)| \leq c < 1 $ on $I'$ will produce the desired results?2012-11-04
  • 0
    I would appreciate it very much if you would like to elaborate a bit more on that! :)2012-11-04
  • 0
    OK, give me a minute...2012-11-04

1 Answers 1

1

This is a standard result known as the contraction mapping theorem. It is true in much more generality and is a very useful analytical tool. It is used to prove Newton's method (or equivalently the implicit function theorem), existence and uniqueness of solutions to ODEs, and much more. The technique is very useful, and has many generalizations (eg, to show continuity of solutions of a 'parameterized' fixed point map, which can be used to show continuity of solutions of parameterized ODEs). It is worth understanding well.

Suppose $f(I') \subset I'$, where $I' \subset \mathbb{R}$ is a closed interval, and $|f'(x)|\leq c< 1$ for $x \in I'$. The key condition here is $c<1$.

Then if $x,y \in I'$, the mean value theorem gives $|f(x)-f(y)|\leq c|x-y|$ .

First note that the set of 'local fixed points' $\{x \in I'| f(x) = x\}$ contains at most one point, for if $a,a' \in I'$ and $f(a) = a$, $f(a') = a'$, then we have $|a-a'| = |f(a)-f(a')| \leq c |a-a'|$, and the only way this can be true is if $a=a'$.

Now suppose $x_0 \in I'$ and $x_{n+1} = f(x_n)$. We want to show that $x_n$ converges to some $\hat{x}$.

If $x_n$ converges, then since $x_n \in I'$ and $I'$ is closed, then $\hat{x} \in I'$. Furthermore, by continuity of $f$, we have $f(\hat{x}) = \hat{x}$, and this must be the unique fixed point in $I'$ by the above remark.

So now we must show that $x_n$ converges. Note that since $I'$ is closed, it is complete and so all we need to do is show that the sequence is Cauchy. This is the key point of the proof here.

We have $|x_{n+2}-x_{n+1}| = |f(x_{n+1})-f(x_n)| \leq c |x_{n+1}-x_n|$, repeating shows that $|x_{n+1}-x_n| \leq c^n |x_1-x_0|$.

So we have (I'm assuming $n>m$ here, there is no loss of generality in doing so): $|x_n -x_m|\leq |x_n-x_{n-1}|+|x_{n-1}-x_{n-2}|+\cdots |x_{m+1} -x_m|$, and using the estimate, we have $|x_n -x_m|\leq (c^{n-1}+\cdots+c^{m+1}+c^m)|x_1-x_0|$. Now, since $c^{n-1}+\cdots+c^{m+1}+c^m = c^m(c^{n-m-1}+\cdots+c+1) \leq c^m(1+c+c^2+\cdot) = c^m \frac{1}{1-c}$, we have $|x_n -x_m|\leq c^m \frac{1}{1-c} |x_1-x_0|$. So, by choosing $n,m$ large enough, we can make this arbitrarily small, that is, the sequence is Cauchy. Hence it converges.

Since we know that if $x_0 \in I'$, then the sequence $x_n$ converges to the unique fixed point in $I'$.

  • 0
    Thank you very much! I will now dig into this! Great to know about the contraction mapping theorem as I now can try to understand it better! This has saved my day :)2012-11-04
  • 0
    You are very welcome, glad to be of help.2012-11-04