# Fixed point method : where is my error?

• May 23rd 2008, 08:55 PM
arbolis
Fixed point method : where is my error?
I've mostly solved the following problem :
The equation $\displaystyle x^2-x-1=0$ has a zero in $\displaystyle [-1,0]$.
a)Verify that the function $\displaystyle g(x)=x^2-1$ has $\displaystyle 2$ fixed points and that the derivative of g in a fixed point has its absolute value greater than $\displaystyle 1$. Take note that the existence of a fixed point doesn't imply that the derivative evaluated in this point has an absolute value lesser than 1. DONE
b)Show that
$\displaystyle g(x)$ satisfies the conditions of existence of a fixed point in [-1,0]. DONE (I showed that g was contractive on this interval)
c)Chose a
$\displaystyle x_0$ closed to the fixed point of g in $\displaystyle [-1,0]$, analyze the convergence of the sequence $\displaystyle x_{n+1}=g(x_n)$. This is where I'm stuck in. My work : I chose $\displaystyle x_0=-1$. I get $\displaystyle x_1=0$. Then $\displaystyle x_2=-1$. It shouldn't be possible! It's not convergent, it will oscillate infinitely! Where is my error? If g is contractive on [-1,0], it must have a fixed point, so what am I doing wrong here?
• May 23rd 2008, 11:58 PM
flyingsquirrel
Hi
Quote:

Originally Posted by arbolis
I've mostly solved the following problem :
The equation $\displaystyle x^2-x-1=0$ has a zero in $\displaystyle [-1,0]$.
a)Verify that the function $\displaystyle g(x)=x^2-1$ has $\displaystyle 2$ fixed points and that the derivative of g in a fixed point has its absolute value greater than $\displaystyle 1$. Take note that the existence of a fixed point doesn't imply that the derivative evaluated in this point has an absolute value lesser than 1. DONE
b)Show that
$\displaystyle g(x)$ satisfies the conditions of existence of a fixed point in [-1,0]. DONE (I showed that g was contractive on this interval)

g is not contractive on
$\displaystyle [-1,\,0]$ : $\displaystyle \frac{|g(-0.9)-g(-0.8)|}{|-0.9-(-0.8)|}=\frac{|0.9^2-0.8^2|}{0.9-0.8}=0.9+0.8=1.7>1$. To show that $\displaystyle g$ has a fixed point on $\displaystyle [-1,\,0]$, think about the intermediate value theorem.

Quote:

c)Choose a $\displaystyle x_0$ closed to the fixed point of g in $\displaystyle [-1,0]$, analyze the convergence of the sequence $\displaystyle x_{n+1}=g(x_n)$. This is where I'm stuck in. My work : I chose $\displaystyle x_0=-1$. I get $\displaystyle x_1=0$. Then $\displaystyle x_2=-1$. It shouldn't be possible! It's not convergent, it will oscillate infinitely!
$\displaystyle x_0=-1$ is not the only possibility, $\displaystyle x_0\in [-1,\,0]$. You should try to link the fixed point and the limit of the sequence : let's assume that $\displaystyle (x_n)$ has a limit $\displaystyle L$. What can be said about $\displaystyle L$ ?
• May 24th 2008, 09:01 AM
arbolis
Quote:

g is not contractive on [-1,0]
Oh... Therefore this website is wrong : Homeomath : fonction contractante, where it states " Si une fonction définie et dérivable sur un intervalle I et telle que pour tout réel x de I on a f ' (x) < 1 alors f est contractante". It should be the absolute value of $\displaystyle f'(x)$. Ok, I will try with the intermediate value theorem.

Quote:

What can be said about $\displaystyle L$ ?
I think L is the negative root of $\displaystyle x^2-x-1$.
Quote:

You should try to link the fixed point and the limit of the sequence
I still don't know what to chose for $\displaystyle x_0$. According to my calculator the root of the $\displaystyle x^2-x-1$ is between $\displaystyle -0.62$ and $\displaystyle -0.61$, so it means I should start $\displaystyle x_0$ close to it? If yes, then how could I have guessed it without a calculator?
• May 24th 2008, 11:34 AM
flyingsquirrel
Quote:

Originally Posted by arbolis
I think L is the negative root of $\displaystyle x^2-x-1$.

OK
Quote:

I still don't know what to chose for $\displaystyle x_0$. According to my calculator the root of the $\displaystyle x^2-x-1$ is between $\displaystyle -0.62$ and $\displaystyle -0.61$, so it means I should start $\displaystyle x_0$ close to it?
In fact, whichever $\displaystyle x_0$ one chooses, the sequence will "oscillate" : $\displaystyle x_{2n}$ will tend to $\displaystyle 0$ (resp. $\displaystyle -1$) and $\displaystyle x_{2n+1}$ will tend to $\displaystyle -1$ (resp. $\displaystyle 0$). I think that asking you to choose $\displaystyle x_0$ "closed to the fixed point" is just a means of preventing you from choosing $\displaystyle x_0=-1$ or $\displaystyle x_0=0$ which gives a sequence that can be studied very easily. :D

Let $\displaystyle x_0\in]-1,\,0[$ (choose any value but the negative root of $\displaystyle x^2-x-1$ :D)
The sequence $\displaystyle (x_n)$ is neither increasing nor decreasing. (reason : $\displaystyle g(x)-x$ is positive on $\displaystyle [-1,\,L[$ and negative on $\displaystyle ]L,\,0]$) In this case, we usually study the two sequences defined by $\displaystyle a_n=x_{2n}$ and $\displaystyle b_n=x_{2n+1}$. Since $\displaystyle (a_n)$ and $\displaystyle (b_n)$ are monotone*, finding their limits (if they do converge) is not too hard. If these two limits are equal, the sequence $\displaystyle (x_n)$ converges, if they are not equal, $\displaystyle (x_n)$ diverges.

* $\displaystyle a_n=x_{2n}=g(x_{2n-1})=g\circ g(x_{2(n-1)})=g\circ g(a_{n-1})$ and, as $\displaystyle g$ is decreasing on $\displaystyle [-1,\,0]$, $\displaystyle g\circ g$ is increasing thus $\displaystyle (a_n)$ is monotone. It'll be increasing if $\displaystyle a_0<a_1$ and decreasing otherwise. The same goes for $\displaystyle (b_n)$.