How do I construct a second order convergent fixed point iteration?

Question

Say I am dealing with $f(x) = x^3+2x+1$ and I need to come up a fixed point iteration to find its root, that has a second order convergence. How should one approach this question? Should I just compute a couple formulae and see which one converge quadratically? Is there a better method than that?

Answer 1

Okay, the question has been changed, so I'm going to edit my answer:

First, why can't you just use something like Newton's method (applied to the function $x^3+2x+1$)? Note this is a fixed point method for the function $g(x)=x-\frac{f(x)}{f'(x)}.$ It will converge quadratically because your zero is simple.

If you don't like that, then the most naive thing that you could do is define an iteration $$x_{n+1}=x_n^3+3x_n+1,$$ then use Aitken extrapolation, which will be second order. This will converge to some real $x$ with $x=x^3+3x+1,$ so it will satisfy $x^3+2x+1=0.$ Thus, it will be a root.

Generally, Aitken extrapolation is a good way to take a first-order fixed point method and extend it to one which is second order (to answer the title's question).

Answer 2

To find the root of a function $f$, Newton's method should come to mind first: $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} . $$

From you comment, it seems you are not aware that it is a fixed point iteration also, because if $x_\star$ is a fixed point, and $f'(x_\star) \neq 0$, then $f(x_\star) = 0$.