For which polynomial roots does naively solving for $x$ give a convergent iterative method?

Question

In the "The Treatise of Chord and Sine" Jamshid al-Kashi would calculate the unconstructable number $\sin(1^\circ)$ by using the constructible number $\sin(3^\circ)$. He used an iterative method derived from the used the trigonometric identity $\sin (3\theta) = 3\sin(\theta)-4\sin(\theta)^3$, which is equivalent to finding the roots for $4x^3-3x+c=0$. To do this he naively solved for $x$ by rearranging to $x=(4x^3+c)/3$. From here he used the iterative equation $x_{n+1}=(4x_n^3+c)/3$ and it converges quickly even for a relatively bad initial guess. Doing a few test cases shows that this works a lot of the time and for arbitrary polynomials with real roots.

However not all polynomial roots can be calculated this way. For example if I try $x^2-2=x^2+x-x-2=0$ to motivate $x_{n+1}=x_n^2+x_n-2$ it will diverge to $\infty$ even for a guess very close to $\sqrt{2}$.

So the question is given an iterative method of the form $x_{n+1}=p(x_n)$ for some polynomial $p(x)$ what can we say about the radius of convergence? With the condition $\vert p'(L)\vert < 1$ we can assure that $x_{n+1}=(4x_n^3+c)/3$ converges on the interval $(-\frac12 ,\frac12)$ as discussed in the comments however initial values such as $\frac45$ also work well outside that range. Can we say more about the polynomial form specifically?

Answer 1

A fixed point $r$ of differentiable function $f$ is attracting if $|f'(r)| < 1$, and repelling if $|f'(r)| > 1$ (it's more complicated if $|f'(r)| = 1$). If it's attracting, the the iteration of $f$ starting at a point sufficiently close to $r$ converges to $r$.

If $(a,b)$ is the immediate basin of attraction for an attracting fixed point $r$ of continuous function $f$, i.e. the largest interval containing $r$ such that iteration of $f$ starting at any point in the interval converges to $r$. The following are the possibilities:

1. $f(a) = a$, $f(b) = b$: $a$ and $b$ are fixed points, which can't be attractors.
2. $f(a) = a$, $f(b) = a$: $a$ is a fixed point (and not an attractor), $b$ is mapped to $a$.
3. $f(a) = b$, $f(b) = b$: $b$ is a fixed point (and not an attractor), $a$ is mapped to $b$.
4. $f(a) = b$, $f(b) = a$: $a$ and $b$ form a $2$-cycle (that is not an attractor).
5. $a = -\infty$, $f(b) = b$.
6. $f(a) = a$, $b = +\infty$.
7. $a = -\infty$, $b=+\infty$.

By finding the fixed points and the $2$-cycles, we can determine the basin of attraction: you just take the closest such points (if any) on either side of $r$. For example, with $p(x) = (4 x^3 - 1/2)/3 $ the fixed points (solutions of $(4 x^3 -1/2)/3 = x$) are approximately $-0.7660444431$, $-0.1736481777$ and $0.9396926208$ and there are no real $2$-cycles. The vales of $p'$ at these fixed points are approximately $2.347296355$, $0.1206147585$, and $3.532088886$ respectively. Thus only the middle one is attracting, and its immediate basin of attraction is the interval between the other two fixed points.