Compare five ways of solving cubic equation by iterations (nested expressions)

Question

Say we have a depressed cubic equation in the general form:

$$x^3-bx-c=0$$

There are basically five ways of solving it by iterations. Let's consider them in no particular order (the names are my own).

1) The continued fraction / nested radical method:

$$x=\sqrt{b+\frac{c}{x}}=\sqrt{b+\cfrac{c}{\sqrt{b+\cfrac{c}{x}}}}=\sqrt{b+\cfrac{c}{\sqrt{b+\cfrac{c}{\sqrt{b+\cfrac{c}{x}}}}}}$$

Take some $x_0$ and solve the recurrence:

$$x_n=\sqrt{b+\frac{c}{x_{n-1}}}$$

2) The continued fraction / nested square method:

$$x=-\cfrac{c}{b-x^2}=-\cfrac{c}{b-\cfrac{c^2}{(b-x^2)^2}}=-\cfrac{c}{b-\cfrac{c^2}{\left( b-\cfrac{c^2}{(b-x^2)^2} \right)^2}}$$

3) The branching continued fraction method:

$$x=\cfrac{b}{x}+\cfrac{c}{x^2}=\cfrac{b}{\cfrac{b}{x}+\cfrac{c}{x^2}}+\cfrac{c}{\left( \cfrac{b}{x}+\cfrac{c}{x^2} \right)^2}$$

It can also be expressed in several different ways, like this one:

$$x=\cfrac{c+bx}{x^2}=\cfrac{c+b\cfrac{c+bx}{x^2}}{\cfrac{(c+bx)^2}{x^4}}$$

But anyway, for some $x_0$:

$$x_n=\cfrac{b}{x_{n-1}}+\cfrac{c}{x_{n-1}^2}$$

4) Nested cubic roots method:

$$x=\sqrt[3]{c+bx}=\sqrt[3]{c+b\sqrt[3]{c+bx}}=\sqrt[3]{c+b\sqrt[3]{c+b\sqrt[3]{c+bx}}}$$

5) And nested cubes method:

$$x=\frac{1}{b} \left(-c+x^3 \right)=\frac{1}{b} \left(-c+\frac{1}{b^3} \left(-c+x^3 \right)^3 \right)$$

---

They all work in different ways, so I wonder, what are general rules of using one method or the other? How to get all three roots by using them?

For example we have the equation with three real roots $(-3.65617,0.42297,3.23319)$:

$$x^3-12x+5=0$$

Let's take $x_0=1$. Then methods 1, 3 and 4 will converge to the third root, while methods 2 and 5 will converge to the second root.

Changing $x_0$ to other values will not lead to the first root, but some methods will not converge (mainly, method 3).

Answer 1

All your iterations are of the form $x_{i+1}=f(x_i)$ for some $f$ chosen so that at the root $x=f(x)$ If $|f'(x)| \lt 1$ at the root, the iteration will converge to the root for starting values that are close enough. The smaller you can make $|f'(x)|$, the faster the method will converge. Your first iteration has $f(x)= \sqrt{12-\frac 5x}$, which has $f'(x)$ about $0.074$ at the third root. That small value is why it converges so quickly. In contrast, your third method has $f'(x) \approx -0.85$ at the third root. The minus sign is what makes the oscillation in your plot-if $x_i$ is below the root $x_{i+1}$ is above. The value close to $1$ in absolute value is why the convergence is slow. You are waiting for $(-0.85)^n$ to get small.

Answer 2

Let me try two general methods and have look if these show up in your list: $$ f(x) = x^3 - bx - c = 0 $$ Newton-Raphson-Iteration $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^3 - b x_n - c}{3x_n^2 - b} $$ Fixed point iteration: $$ x^3 - bx - c = 0 \iff \\ x^3 - c = b x $$ If $b \ne 0$ we can write this as $$ x^3 - bx - c = 0 \iff \\ F(x) = \frac{x^3-c}{b} = x $$ which leads to the iteration $$ x_{n+1} = \frac{x_n^3-c}{b} $$ The Netwon-Raphson I have not spotted, but the fixed point iteration is your number 5 (nested cubes).

Newton-Raphson has quadratic convergence, so it is fast. Fixed point iteration features attractive $\lvert F(x^*) \rvert < 1$ and not attractive fixed points $x^*$. In the latter case one could try to iterate $x = F^{-1}(x)$, because $(F^{-1})'(x) = 1 / F'(F^{-1}(x))$.

The properties of these iterations result from the properties of their general method.

Note that the different roots (up to three), need different start values for the iteration.

Answer 3

The nested cubic roots method, by affixing a complex cube root of unity $\zeta = e^{2\pi\,i/3}$, can give you all three roots when the cubic has only one real root,

$$x_k= \zeta^k\sqrt[3]{c+b\,\zeta^k\sqrt[3]{c+b\,\zeta^k\sqrt[3]{c+b\,\zeta^k\sqrt[3]{c+bx\dots}}}}$$

for $k=0,1,2$.

When the cubic is a casus irreducibilis, the method can still give two of the three real roots.