5
$\begingroup$

Given a large univariate polynomial, say of degree 200 or more, is there a procedural way of finding all the complex roots? By "roots", I mean complex decimal approximations to the roots, though the multiplicity of the root is important. I have access to MAPLE and the closest function I've seen is:

with(RootFinding): Analytic(Z,x,-(2+2*I)..2+2*I); 

but this chokes if Z is of high degree (in fact it fails to complete even if deg(Z)>15).

  • 0
    https://mathoverflow.net/questions/19999/finding-all-roots-of-a-polynomial2018-11-18

4 Answers 4

5

Everyone's first starting point when dealing with the polynomial rootfinding problem should be a peer at J.M. McNamee's excellent bibliography and book.

Now, it is a fact that polynomials of very high degree tend to make most polynomial rootfinders choke. Even the standard blackbox, the Jenkins-Traub algorithm, can choke if not properly safeguarded. Eigenmethods, while they can have nice accuracy, can be very demanding of space and time (O(n²) space and O(n³) operations for a problem with only O(n) inputs!)

My point is that unless you are prepared to devote some time and extra precision, this is an insoluble problem.

Having been pessimistic in those last few sentences, one family of methods you might wish to peer at (and I have had personal success with) are the so-called "simultaneous iteration" methods. The simplest of them, (Weierstrass-)Durand-Kerner, is essentially an application of Newton's method to the Vieta formulae, treated as n equations in n unknowns (the assumption taken by (W)DK is that your polynomial is monic, but that is easily arranged).

If you wish for more details and references, the book by McNamee I mentioned earlier is a good start.

2

I think one of the biggest problems is approximating multiple roots. The approach described in

L.Brugnano, D.Trigiante. "Polynomial Roots: the Ultimate Answer?", Linear Algebra and its Applications 225 (1995) 207-219

relies on the approximation of eigenvalues of a tridiagonal matrix, obtained via the application of Euclid's GCD algorithm to the original polynomial, and seems to work pretty well.

I couldn't find the pdf for the article though, sorry.

  • 1
    http://dx.doi.org/$1$0.1016/0024-3795(93)00341-V is the paper being referred to. This approach, which can be also thought of as the construction of a Sturm sequence from the polynomial and its derivative to form the tridiagonal matrix whose characteristic polynomial is the original polynomial, works especially well for polynomials with real roots in my experience, though it seems to be a mixed bag for polynomials with complex roots.2010-10-23
1

I think this might help.

Rouche's Theorem: Let $D$ be a bounded domain, with piecewise smooth boundary, $\partial{D}$. Let $f(z)$ and $h(z)$ be analytic on $D \cup \partial{D}$. If $|h(z)| < |f(z)$ for $z \in \partial{D}$, then $f(z)$ and $f(z)+h(z)$ have the same number of zero's in $D$, counting multiplicities.

Example: We find the zeros of the function $p(z)=z^{6}+9z^{4}+z^{3}+2z+4$, inside the unit circle.

For using Rouche's theorem, let $p(z)= f(z) + h(z)$, where $f(z)$ dominates, $h(z)$ inside the unit circle.

Consider $f(z) = 9z^{4}$, which has four zeros inside the unit circle, all at the origin. $h(z) =z^{6}+z^{3}+2z+4$, which satisfies, $|h(z)| < |f(z)|$ for $|z|=1$. Therefore by Rouche's theorem $p(z)$ also has 4 zeros inside the unit circle.

  • 0
    @J. M.: OK. Someone should fix that article. (I left a note on the talk page for now.)2010-10-23
1

I think the following page summarizes the root-finding well, by showing how to reduce it to an appropriate Eigenvalue computation:

http://mathworld.wolfram.com/PolynomialRoots.html