Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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$? –  amWhy Nov 4 '12 at 15:43
    
I've changed algebra tag to algebra-precalculus, since we don't use algebra tag anymore, see meta for details. –  Julian Kuelshammer Nov 4 '12 at 15:44
    
@Julian that seems to deprecate the level of this question. I'd say either "calculus" or "real analysis"? –  amWhy Nov 4 '12 at 15:46
    
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? –  Lukas Arvidsson Nov 4 '12 at 15:46
    
@amWhy: Let’s just say both. –  Brian M. Scott Nov 4 '12 at 15:47

1 Answer 1

up vote 1 down vote accepted

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'$.

share|improve this answer
    
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 :) –  Lukas Arvidsson Nov 4 '12 at 16:59
    
You are very welcome, glad to be of help. –  copper.hat Nov 4 '12 at 16:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.