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
    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
    You are very welcome, glad to be of help.2012-11-04