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.
- There is no reason to believe I will EVER find two points on the ever-expanding squared that evaluate to opposite-quadrant values.
- 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)$.
- Once I accept that new vertex into my set, which of its endpoints would I discard from the set?
- 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.
