1
$\begingroup$

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.

enter image description here

enter image description here

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

$\endgroup$
  • $\begingroup$ I expected to see the Newton method too, $x_{n+1}=x_n-f(x_n)/f'(x_n)$. From suitable starting points it converges fast to the 3 solutions. $\endgroup$ – Giovanni Resta Feb 23 '16 at 20:35
  • $\begingroup$ I only used 'obvious' iterations, this one is most effective of course $\endgroup$ – Yuriy S Feb 23 '16 at 20:44
  • $\begingroup$ The fourth one, the nested cubic roots method, by affixing a complex cube root of unity, can give you two of the three real roots. See answer below. $\endgroup$ – Tito Piezas III Feb 25 '16 at 18:28
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.