Welcome to MathOverflow

Question

2

3

Is it feasible to use Newton's method to find all the roots (if more than one) of a polynomial? Are there any efficient algorithms for finding all the roots?

edited Dec 9 2010 at 9:56

J. M.
2,065●7●20

asked Dec 9 2010 at 5:17

George Tyler
21●2

Yes. Once you find a root $a$, divide the polynomial by $x-a$ and then apply the algorithm again. – Ben Webster♦ Dec 9 2010 at 5:45

Are these real or complex polynomials? Are the coefficients integers? rational? Newton's method can be slow near multiple or closely spaced roots although exact multiple roots can be found using the $\gcd$ of a polynomial and its derivative. Once the roots are approximately located, (Sturm's theorem is helpful) Newtons method can be fairly robust. – Aaron Meyerowitz Dec 9 2010 at 5:46

The coefficients and the roots wanted are real integral values. – George Tyler Dec 9 2010 at 6:22

How do we choose good intervals to test for Sturm's theorem? – George Tyler Dec 9 2010 at 7:44

1

Your usage of "multiple roots" seems erroneous; "multiple" is used to denote a root that is counted more than once, e.g. 1 is a multiple (double) root of the polynomial $x^2-2x+1$. – J. M. Dec 9 2010 at 9:21

show 3 more comments

Denis Serre · Answer 1 · 2010-12-09 09:50:32Z UTC

The Newton's method has driven a lot of attention during the past decades in the community of complex analysis, because of its nice behaviour as a dynamical system. From the point of view of the approximation of the roots of a polynomial $P$, it has contrasted properties. On the one hand, it is a fast method for calculating one root $a$. But once you have a good approximation $\alpha$ of it, you face the problem of dividing $P$ by $X-\alpha$. This division is not exact, and it is unstable if $P$ has an other root close to $a$. The latter case happens frequently in large matrices, either random or with physical meaning.

This is why the codes employed by computers to calculate the set of roots follows an other idea. Form the companion matrix $B_P$, which turns out to be of Hessenberg form ($b_{ij}=0$ if $i\ge j+2$). Then apply the QR method. This one enjoys crucial properties:

it preserves the Hessenberg form,
one iteration is fast when applied to a Hessenberg matrix ($O(n^2)$ operations),
it is stable, in the sense that the roundoff errors are not amplified along the iterations. This is because one conjugates by unitary matrices.

Naively, we could think that the calculation of eigenvalues of a matrix must be done in two steps, first calculate the characteristic polynomial, then solve it. But the QR method is so much efficient that the converse is actually true: to find the roots of a polynomial, form the companion matrix and then apply QR.

If you fear that $P$ has multiple roots, you had better to eliminate them first by calculating the g.c.d. of $P$ and $P'$. This is not easy in general, but if $P\in\mathbb Z[X]$, you do it exactly.

Later. I realize that you seem to be interested only on polynomials whose roots are real. If this is correct, then you can accelerate the calculation by the following trick. First form a Sturm sequence of polynomials $P_0=P,P_1=P',\ldots$. Then use it to form a tridiagonal symmetric matrix $H$ whose characteristic polynomial is $P$: $P_{n-j}$ is the characteristic polynomial of the principal $j\times j$ matrix. Now apply QR to $H$. This is really fast. Each iteration requires only $O(n)$ operation, and the method becomes of cubic order.

Federico Poloni · Answer 2 · 2010-12-09 13:18:45Z UTC

1

Another good choice is the Aberth method http://en.wikipedia.org/wiki/Aberth_method. It has some advantages wrt the QR-based approaches, especially when the coefficients have very different magnitudes.

answered Dec 9 2010 at 13:18

Federico Poloni
4,249●1●12●24

This is in fact very similar to the (Weirestrass-)Durand-Kerner method I mentioned in the comments, in that both can be considered as Newton-Raphson methods applied to an appropriate system of $n$ equations in $n$ unknowns. There is a good discussion of these methods in McNamee's book (which I also linked to in the comments). The advantage of (Ehrlich-)Aberth(-Maehly) over (W)DK is that this has a cubic convergence rate (over (W)DK's quadratic convergence rate) if the polynomial's roots are all simple. – J. M. Dec 9 2010 at 13:44

timur · Answer 3 · 2010-12-09 06:15:26Z UTC

0

Use Sturm sequences. Or form a matrix that has eigenvalues equal to the roots of your polynomial and apply the QR iteration.

answered Dec 9 2010 at 6:15

timur
1,300●1●9●19

FWIW, if your input polynomial has all its roots real, one can use a Sturmian scheme to construct a symmetric tridiagonal companion matrix, which can then be subjected to the QR algorithm (which is more efficient in the symmetric case than in the unsymmetric case). – J. M. Dec 9 2010 at 9:27

Newton’s Method for Finding Multiple Roots

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.