Newton-Raphson method and solvability by radicals

Question

If a polynomial is not solvable by radicals, then does the Newton-Raphson method work slower or faster? I don't know how to approach this.

Answer 1

The speed of Newton-Raphson has [EDIT: almost] nothing to do with solvability by radicals. What it does have to do with is $f''(r)/f'(r)$ where $r$ is the root: i.e. if $r$ is a root of $f$ such that $f'(r) \ne 0$ and Newton-Raphson starting at $x_0$ converges to $r$, then $$\lim_{n \to \infty} \dfrac{x_{n+1} - r}{(x_n - r)^2} = - \frac{f''(r)}{2 f'(r)}$$
If, say, $f(x) = x^n + \sum_{j=0}^{n-1} c_j x^j$ is a polynomial of degree $n\ge 5$, $f''(r)/f'(r)$ is a continuous function of the coefficients $(c_0, \ldots, c_n)$ in a region that avoids $f'(r) = 0$. But there is a dense set of $(c_0,\ldots,c_n)$ for which $f$ is solvable by radicals (e.g. where the roots are all of the form $a+bi$ with $a$ and $b$ rational), and a dense set where it is not (e.g. where $c_0,\ldots,c_n$ are algebraically independent).

EDIT: On the other hand, if the convergence of Newton-Raphson is slow (linear rather than quadratic) and $f$ is a polynomial of degree $5$, then $f$ is solvable by radicals (over the field generated by the coefficients). For in this case $f'(r) = 0$, and so $r$ is a root of the gcd of $f$ and $f'$, which has degree $<5$.