Thanks for the reference! Here's the Doyle-McMullen paper: http://math.dartmouth.edu/~doyle/docs/icos/icos.pdf http://www.math.dartmouth.edu/~doyle/docs/icos/icos/icos.html At 04:12 AM 9/20/2010, Bill Thurston wrote:
I haven't been following this thread, but I want to mention that Peter Doyle and Curt McMullen made a global analysis of all possible root-finding algorithms for polynomials that involve iterating an complex analytic function of one variable with parameters depending on the coefficients of the polynomial. (Newton's method is one such iteration, but it gets trapped in unproductive loops with positive probability already for cubics. They showed that algorithms can be constructed that converge a.s. for polynomials of degrees 1 through 5, but no such method converges a.s. to a root for polynomials of degree 6 or higher.
The proof is based on the fact that the simple parts of Galois groups through degree 5 are all automorphism groups of polyhedra, but this is false for higher degrees. The construction for quintics is ingenious, making essential use of the theory Klein developed describing invariants for the icosahedral group, expressing them in terms of the rational functions that describes the map of CP^1 to its symmetry quotient by the icosahedral group.
I think these methods are all super-exponential once they're in the attracting basin, but I don't remember
Bill