Proving that the Newton iteration is strictly monotonically decreasing.

Question

Let $p(x)$ be a polynomial with $\operatorname{deg}(f)\geq 2$ that just has real roots. The largest root of $p$ is $x^*$. I now have to show that Newton's method (Newton's iteration to find zeros) is strictly monotonically decreasing for every $x_0>x^*$.

My attempt

I somehow have to implement the information about the zeros of $p$. I figured, I could use the Fundamental theorem of algebra to write $p$ as:$$f(x)=a(x-x_1)\cdot \ldots \cdot (x-x^*)\cdot \ldots \cdot (x-x_{n-1})$$ and than write $x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}$ and use $x_0>x^*$. Is $f(x_0)$ negative? Can someone help me?

Answer 1

Assuming the leading coefficient is positive, you get the value and all derivatives positive for $x>x_*$. This implies that the function is monotonically increasing and convex there. Now apply what you know about tangents to convex functions. Consider the tangent at $x_0$,

• The tangent value at $x_*$ is below $p(x_*)=0$.
• The root $x_1$ of the tangent is above $x_*$, more precisely $x_*<x_1<x_0$.
• The value of $f$ at the tangent root is positive,...