Fixed point iteration method converging to infinity

Question

So I am trying to use Fixed Point Iteration Method for this function:

$ f(x)=x^5 -x^4-x-3 $ .

By using bisection method I found out that the root is around $1.64056$.

So I started by doing:

$f(x)=0$ then found out that:

$x=x^5-x^4-3$ .

So here I used Microsoft Excel and it generated very big numbers, which are converging to Inf almost instantly, even if I select my $x_0$ really close to my actual root I need to find. I am adding an Excel screenshot of what I am getting. Is it even possible to use Iteration method for this kind a function? If so, where can I go from here?

Answer 1

So I am trying to use Fixed Point Iteration Method for this function: $$f(x)=x^5 -x^4-x-3$$

To achieve what?

In case you want to find a zero of $f(x)$ by means of an iteration of the form $$x\mapsto g(x)\qquad\text{where}\quad x_0=g(x_0)$$

$x_0$ is a fixed point of $g$, but it's only an attractive fixed-point (assuming $g$ is smooth) when $$|g'(x_0)|<1$$

You chose $g(x) = f(x) + x$ with $x_0\approx 1.64$, $g'(x) = 5x^4-4x^3$ and $$g'(x_0)\approx18.55$$

Thus the fixed-point is clearly repelling.

You can use fixed-point iteration in principle, but as I wrote the absolute value of the derivative at the fixed-point must be less than one$^1$. So you'd have to construct some other function like $$g(x) = \frac{x+3}{x^4} +1$$ (I did not check the derivative condition for this choice, though.$^3$)

Newton-Raphson iteration usually works really well and has quadratic convergence$^2$, in your case: $$x\mapsto x-\frac{f(x)}{f'(x)} = x - \frac{x^5 -x^4-x-3}{5x^4 - 4x^3-1}$$ yields $x_0\approx 1.640585621426312$.

---

$^1$Equal to one is called "indifferent"; it might converge (slowly) but that case needs further analysis.

$^2$Provided you are "close" enough to the zero and it's not a multiple zero of $f$.

$^3$I did now and it's $-1.42$, so it won't work, either.

Answer 2

In a polynomial with only one sign change in the coefficient sequence one can always find an equivalent form that is monotonous and convex or concave on the positive half-axis. With such a function it is known that the Newton iteration will converge monotonically towards the root if started on the right side of the root. This follows just from the geometry of the tangent as supporting line of the graph.

Here this can be achieved by dividing by $x^4$ or $x^5$. The first one gives $f(x)=x-1-x^{-3}-3x^{-4}$, which is monotonically increasing and concave over the positive half-axis. Any tangent there is thus above the graph, tangent roots thus smaller than the function roots, but larger than the base point of the tangent. Then starting, for example, from $x_1=1$ the Newton iteration will be growing towards the root of the function.

The Newton method of $f$ to be used as fixed-point iteration is $$N(x)=x-\frac{x-1-x^{-3}-3x^{-4}}{1+3x^{-4}+12x^{-5}}.$$

$k$	$x_k$
1	1.0000000000000000
2	1.2500000000000000
3	1.4919752765802732
4	1.6203796983619547
5	1.6402369415053781
6	1.6405855189039007
7	1.6405856214263030
8	1.6405856214263119
9	1.6405856214263119