# Analog to bisection: Converging on complex roots of a polynomial

I am working on a Perl module that, among other features, will solve all the zeroes of a polynomial. Thus far, I am doing OK for $2$, $3$, $4$th degree using quadratic, Cardano's and Ferarri's formulas. For $5$th degree with real coefficients I have used bisection to get reasonably close to the guaranteed real root, then used Newton's method to get it within $12$ decimal places. (I've called that close enough.) Then I "deflate" the polynomial and pass it on to my calls for $4$th degree.

The theory is that I can do this for any odd-degree polynomial. The obvious problem is that when I deflate by that one root, I get an even-degree polynomial. If that's above $4$, I'm in trouble.

I have seen some discussion of Sturms theorem in this forum and on Wikipedia. The problem is that this is good only for getting near a real root, even if I understood the theorem. I may even apply it to odd-degree polynomials in the future. And I'm still scratching my head over wild assumptions in Laguerre's method. Again, I may use that in a later release of my module.

But for now, I'm looking for a bisection-analogous scheme that would help me locate the neighborhood of a complex root of an even-degree polynomial. After all, there is no guarantee that a real root even exists.

I have thought of using squares of increasing size around the origin but I needed an analogy to being of opposite signs. It occurs to me that two inputs (at any vertex of the square) that evaluate to complex numbers being in vertically opposite quadrants would be a good starting point. e.g.: $$P(z_1) = -1 + 3i$$ $$P(z_4) = 4 - 5i$$ so that I would use the midpoint of the inputs $\frac{z1 + z4}2$ as the next vertex. But then it's no lo longer a square.. Which may not be a bad thing. But there are a few holes in my logic, assumptions I don't believe are justified.

1. There is no reason to believe I will EVER find two points on the ever-expanding squared that evaluate to opposite-quadrant values.
2. Once I accept that midpoint as the new vertex of the quadrilateral, there is no reason to believe I will still find opposite-quadrant values of $P(z)$.
3. Once I accept that new vertex into my set, which of its endpoints would I discard from the set?
4. What do I do if two vertices evaluate to opposite-quadrant complex numbers relative to a third point? HMMm.. I guess I would accept the one who's evaluation is closet to $0$.

OK, you get the idea. And I'm sure that's not all of it.

Is there a known scheme for verging in close to complex roots analogous to to bisection for real roots? Or can someone come up with a scheme to rescue my scheme? For that matter, should anyone do so?

Thanks much!

-- J.S.

-
While Laguerre's method does make a lot of strange assumptions, I can verify that it does indeed work :) –  Ataraxia Jul 17 '13 at 14:02

Did you have a look at http://en.wikipedia.org/wiki/Splitting_circle_method ? It explains the state of the art algorithm for finding root of a complex polynomial. It basically uses residue computation to count the number of roots in a disk.

-
This is the first I've ever heard of it. It ain't a casual read! ;-( It is using terms I have long forgotten (like moduli of the coefficients and the residue theorem. I tried to scan it for a cookbook recipe for finding a good circle. I think I'll give up and check out Laguerre's algorithm again. –  Jacob Salomon Jul 18 '13 at 4:47
Depending on your mathematical skill and how much you are ready to invest, the algorithms are very precisely described in Bourdon's PhD thesis: algo.inria.fr/gourdon/thesis.ps.gz –  hivert Jul 18 '13 at 7:24
235 pages is quite a thesis. I probably don't have the Math skills to comprehend it - At AT&T I remarked to colleagues that I felt odd there, being around all those PHD's and me never having gotten past the bachelor's. However, I can't tell about this thesis 'cause I don't read French. Funny, because his web page with links to the thesis is in English. :-( –  Jacob Salomon Jul 22 '13 at 2:53
I did indeed bite said bullet. With a starting guess of (i+i) it converged to within 9 decimal places in about 6 iterations.I would still like to hear from someone who has a moral equivalent to bisection that works on the complex plain but as far as I can see, it was a dead end idea. –  Jacob Salomon Jul 29 '13 at 2:52
I did indeed bite said bullet, using Laguerre's inspired lunacy. With a starting guess of (i+i) it converged to within 9 decimal places in about 6 iterations. I would still like to hear from someone who has an equivalent to bisection on the complex plain but as far as I carry it, it was a dead end idea. Even with 64-bit floating point numbers, I could not get the same 12-place accuracy in the 6th degree polynomial, owing to rounding errors; I had to loosen up the margin to 1/(10^9). But that is the domain of the Perl universe. Thanks for the encouragement, Ataraxia. –  Jacob Salomon Jul 29 '13 at 2:59