<s>[INST] Convergence of Newton Method for monotonic polynomials Consider a polynomial $p : \mathbb R \to \mathbb R$ with $p'(x) > 0$ for all $x \in \mathbb R$. The function $p$ has exactly one real zero. Will the Newton method
$$x_{n+1} = x_n - \frac{p(x_n)}{p'(x_n)}$$
converge for all $x_0 \in \mathbb R$?
Intuitively I think there still might be a counterexample - but I couldn't find one, so is it maybe possible that it indeed converges for every $x_0$?
 [/INST] No, not necessarily. In particular, consider the polynomial,
$$p(x) = \frac{7}{2}x - \frac{5}{2}x^3 + x^5.$$
Note that
$$p'(x) = \frac{7}{2} - \frac{15}{2}x^2 + 5x^4,$$
a positive quadratic in $x^2$ with a negative discriminant $-\frac{55}{4}$, and hence is strictly positive everywhere. This means $p$ is strictly increasing, as required.
Take an initial iterate $x_0 = 1$. Then,
\begin{align*}
x_1 &= 1 - \frac{p(1)}{p'(1)} = 1 - \frac{2}{1} = -1 \\
x_2 &= -1 - \frac{p(-1)}{p'(-1)} = -1 - \frac{-2}{1} = 1,
\end{align*}
and so the iterates repeat.

Method
It's not difficult to form a cycle with Newton's method. I wanted a polynomial that passes through $(-1, -2)$ and $(1, 2)$, both with derivative $1$. Following the tangent at $(-1, -2)$ to the $x$-axis will yield $x = 1$, so if we take $x_n = -1$, then $x_{n+1} = 1$. Following the tangent at $(1, 2)$ yields an $x$-intercept of $x = -1$, so $x_{n+2} = -1$, and so the iterates repeat.
I tried for a degree $5$ polynomial. Let our polynomial be
$$p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5.$$
Our restrictions turn into
\begin{align*}
p(-1) = a_0 - a_1 + a_2 - a_3 + a_4 - a_5 &= -2 \\
p'(-1) = a_1 - 2a_2 + 3a_3 - 4a_4 + 5a_5 &= 1 \\
p(1) = a_0 + a_1 + a_2 + a_3 + a_4 + a_5 &= 2 \\
p'(-1) = a_1 + 2a_2 + 3a_3 + 4a_4 + 5a_5 &= 1.
\end{align*}
Solving this, we get a general solution in terms of $s$ and $t$:
$$p(x) = \frac{5}{2}x - \frac{1}{2}x^3 + t(1 - 2x^2 + x^4) + s(x - 2x^3 + x^5).$$
In particular, I needed to choose $s$ and $t$ so that the derivative
\begin{align*}
p'(x) &= \frac{5}{2} - \frac{3}{2}x^2 + t(3x^3 - 4x) + s(1 - 6x^2 + 5x^4) > 0
\end{align*}
Clearly, we required $s > 0$. I also decided to chose $t = 0$; it may not have been necessary, but it made things simpler. Now $p'(x)$ is now a cubic in $x^2$:
$$p'(x) = \left(\frac{5}{2} + s\right) - \left(\frac{3}{2} + 6s\right)x^2 + 5sx^4.$$
I wanted the discriminant to be negative, which is to say
$$\left(\frac{3}{2} + s\right)^2 - 20s\left(\frac{5}{2} + s\right) < 0.$$
Choosing $s = 1$ did the trick, and gave us the previously presented polynomial.
</s>