Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Do you have any reason to think it will make any difference at all? –  Chris Eagle Nov 1 '12 at 20:13
    
Well, I tried some cases and it works slower but I don't know how to generalize. –  dot dot Nov 1 '12 at 20:15
1  
Does the Newton-Raphson method work slow or faster than what?! –  Fly by Night Nov 1 '12 at 20:16
    
It works slower (at least with the cases I tried) with polynomials that are not solvable than radicals than when I use it with polynomials which are solvable by radicals. –  dot dot Nov 1 '12 at 20:18
    
Can you provide some examples? –  Peter Phipps Nov 1 '12 at 20:19

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.