Fixed Point Method : Negative Roots

Question

Graphical Representation of Function f(x) and g(x)

Red function: $f(x) = x^6-x-1 = 0$,

Green function: $g(x) = (1 + x)^{(1/6)}$

So I am doing my Problem Based Learning on this Fixed Point Method for root finding and when using the equations as mentioned above I manage to get to the root using the $x_0$, midpoint of $a$ and $b$.

Where the midpoint of $a$ and $b$, $x_0$ is used as the initial guess for the first iteration by subbing into $g(x)$. The next iterations use the outcome of the previous $g(x)$ until a specified error tolerance.

This is my reference I used for my problem. Particularly example 1

1st Case:

$a = 0$, $b = 2$ I get to the root within 16 iterations, $1.13472413840151942210$

2nd Case:

$a = -2$, $b = 0$

I was imagining I'd get to the negative root of $f(x)$ which is roughly $-0.77809$, However my iterations all end up to the same root, $1.13472413840151942210$.

I feel like there's something to do with the fact of $|g(x)'| < 1$ but I cant seem to explain it.

I would like to also take this opportunity to thank you as this is my first time posting on a forum as such. I am learning to provide clearer and more helpful information as well as a better formatting of posts.

Answer 1

If $x = (1+x)^{1/6}$ then $x^6-x-1=0$, but if $x = -(1+x)^{1/6}$ the same happens. So, the solutions of $x^6-x-1=0$ are not just the solutions of $x = (1+x)^{1/6}$, but also the solutions of $x = -(1+x)^{1/6}$.

The fixed point of $g_1(x)=(1+x)^{1/6}$ is the positive root of the original equation, while the fixed point of $g_2(x)=-(1+x)^{1/6}$ is the negative root.

Using the fixed point method with $g_1$ can only give you the positive root.

Answer 2

Your obvious problem is that the root function only returns positive results. Try to set the sign to negative, $g(x)=-\sqrt[6]{1+x}$ to force the issue. This converges, even if it is glacially slow

 k       x_k
------------------------
 0   -0.5
 1   -0.8908987181403393
 2   -0.6912550369338881
 3   -0.822116403225611
 4   -0.7499333206387577
 5   -0.7937358043597973
 6   -0.768665356365025
 7   -0.7835020057736696
 8   -0.7748940262088103
 9   -0.7799459430317561
10   -0.7770009741470807
11   -0.7787244804404263
12   -0.7777181388435623
13   -0.7783065238056899
14   -0.7779627787449485
15   -0.7781636929840169
16   -0.7780462928891745
17   -0.7781149039704025
18   -0.7780748098870945
19   -0.778098240819203

Apply the convergence acceleration of your choice, for instance Aitkins delta-squared process.

The next step is to use proper root-finding methods on the function $f$, like a modified regula falsi or Dekker's methods or the Brent method.

---

One could continue hand-crafting fixed-point iterations by observing that the roots are close, but not too close to $x=\pm 1$. Thus first transform the equation to $$ x=x^6-1=(x^3-1)(x^3+1) $$ and divide by the factor that is not close to zero. This gives $$ x^3=1+\frac{x}{x^3+1}\implies x_{next}=g_+(x)=\sqrt[3]{1+\frac{x}{1+x^3}} $$ as fixed-point iteration for the positive root and for the negative root $$ x^3=-1+\frac{x}{x^3-1}\implies x_{next}=g_-(x)=-\sqrt{1+\frac{x}{1-x^3}}. $$ These iterations converge indeed with a faster linear rate

 k   x_k for g_minus     x_k for g_plus
------------------------------------------- 
 0  -0.500000000000000   0.500000000000000
 1  -0.822070691443490   1.130403814338055
 2  -0.778338554305334   1.135078280368128
 3  -0.778085964080519   1.134695038513041
 4  -0.778089652182065   1.134726529073776
 5  -0.778089597891093   1.134723941995059
 6  -0.778089598690192   1.134724154537335
 7  -0.778089598678431   1.134724137075878
 8  -0.778089598678604   1.134724138510428
 9  -0.778089598678601   1.134724138392572
10  -0.778089598678601   1.134724138402255

---

You could of course also apply Newtons method, with $f(x)$ as the function for the negative root and $f(x)/x$ for the positive root. These functions are selected because they are entirely convex/concave and monotonous on their half-axis. $$ x_{next}=N_1(x)=x-\frac{f(x)}{f'(x)}=\frac{x(6x^5-1)-x^6+x+1}{5x^5-1}=\frac{5x^6+1}{6x^5-1} $$ and $$ x_{next}=x-\frac{xf(x)}{xf'(x)-f(x)}=x\frac{(5x^6+1)-(x^6-x-1)}{5x^6+1} =x\frac{4x^6+x+2}{5x^6+1} $$

 k   x_k for first    x_k for second formula
------------------------------------
 0  -0.500000000000   0.500000000000
 1  -0.907894736842   1.188405797101
 2  -0.808358737005   1.138884053084
 3  -0.779907714619   1.134750594258
 4  -0.778096294308   1.134724139477
 5  -0.778089598770   1.134724138402
 6  -0.778089598679   1.134724138402
 7  -0.778089598679   1.134724138402

These are also fixed-point formulas, but obviously converge much faster.