Iterative method to find both roots of $x^2-1=0$

Question

Is there an iterative method of the form

$$x_{n+1}=\alpha x_n^2+\beta x_n+\gamma$$

such that the method converges to the two roots of the equation $x^2-1=0$, given an appropriate starting position?

I feel that there is no such method because we clearly can't use the theorem of the fixed point iteration convergence, because the second derivative must have only one root and not two.

Answer 1

The limit of a converging sequence is unique and so no method can converge to two different roots.

Even if you want to find the two roots depending on the starting point, this cannot be done with a quadratic iteration because a quadratic polynomial can have at most one attractive fixed point (wikipedia).

On the other hand, Newton's method will converge to one root or the other depending on the starting position. For $x^2-1=0$, Newton's method converges to $1$ if $x_0>0$ and to $-1$ if $x_0<0$. Newton's method is not defined for $x_0=0$ and so this is the best you can do.

(If you consider Newton's method for $z^2-1=0$ on the complex plane, then it will fail to converge if $z_0$ is purely imaginary even if $z_0\ne 0$. Things get really interesting for equations of higher degree.)

Answer 2

Yes, there is a simple iterative method. Add $ax$ to both sides, then divide by $a$ and you get

$$x=\frac1ax^2+x-\frac1a$$

Or,

$$x_{n+1}=\frac1ax_n^2+x_n-\frac1a$$

which will converge to either $-1$ or $1$, or diverge/oscillate, depending on $x_0$ and the value of $a$.