By using the Fixed-Point Iteration, I have to find the roots of $f(x)=x^2-x-1=0$

Question

By using the Fixed-Point Iteration, I have to find the roots of $f(x)=x^2-x-1=0$

First I write it in terms $x=f(x)$ $$x^2=x+1$$ $$x=1+\frac{1}{x}$$

Then I make a sequence $x_{n+1}=1+\displaystyle\frac{1}{x_n}$

Now I pick $x_1=2$ $$x_{2}=1+\displaystyle\frac{1}{x_1}=1.5$$ $$x_{3}=1+\displaystyle\frac{1}{x_2}=1.6666$$ $$x_{4}=1+\displaystyle\frac{1}{x_3}=1.6$$ $$x_{5}=1+\displaystyle\frac{1}{x_4}=1.625$$ $$x_{6}=1+\displaystyle\frac{1}{x_5}=1.612538462$$

So it is converging to $1.618$ which is the root, but how do I find the other root?

Answer 1

We have $$ x=1+\frac1x\\ x-1=\frac1x\\ \frac{1}{x-1} =x $$ Now use that one and start with $x_1=-1$

Answer 2

The product of both roots is $-1{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$.

Using this and the convergence of the sequence you gave, you get that $$ y_n = -\frac 1{x_n} = -\frac 1{1 + \frac 1{x_{n-1}}} = -\frac 1{1 -y_{n-1}} = \frac 1{y_{n-1} - 1} $$ converges, giving Arthur's answer.

---

Or, following Ben's suggestion,

$$ y_n = 1 - x_n = 1-\left[1 + \frac 1{x_{n-1}}\right] = -\frac 1{x_{n-1}} = -\frac 1{1-y_{n-1}} = \frac 1{y_{n-1}-1} $$

converges also to the root desired.

Answer 3

The test will converge to the closest root to $x_n$. Because you chose 2 for $x_n$, it converged to $1.618$. But if you chose something closer to the other root, you will see it converges to $-0.618$.