The problem of finding zeros of polynomials is an ancient one. The Sumerians found the well known formula for the roots of a quadratic. Later, in the Middle Ages, exact formula were found for the roots of cubic and quartic polynomials. A significant advance came with Abel's proof that some quintics do not have solutions in terms of radicals and Galois' theory of solvable polynomials. Since finding exact solutions is impossible, in general, the emphasis moved to finding approximate roots of a polynomial.

Newton's Method - known to all from Calculus I - is an iterative technique for finding an approximation to a single zero of a function. To find all roots of a polynomial p, the naive approach is to find an approximate root r₁ using Newtons Method, and factoring p as (x - r₁) . q, and then inductively applying Newton;s Method to obtain an approximate root to q. This process is called deflation. However, since the value of the root obtained by Newton's Method is approximate all of the coefficients of q also are approximate - sometimes the roots of the approximate q are wildly different from the remaining roots of p. For example if p=(x-1)(x-2)...(x-20), and our approximate root r₁=20.0000001 (which is very close to the exact root 20), then working to 10 decimal places the zeros of p divided by (x-20) all have modulus > 17, and all but one are complex!

The purpose of our project was to read a recent paper of Hubbard et al concerning the geometry and topology of Newton's Method when applied to polynomials. Based on our understanding of the paper we have written java applets and other java programs which take as their input an arbitrary complex polynomial, and (1) renormalizes it so that all roots lie in the unit disk, (2) generates a small - of size n (log n)², where n is the degree of the polynomial - set of seeds for Newton's method, so that at least one seed will converge to each root of the polynomial, and then (3) calculates the roots of the polynomial using Newton's Method applied to the given set of seeds. We encountered problems with javas fixed precision arithmetic so we wrote classes to handle arbitrary precision complex arithmetic.

The final stage of the project has been to try to extend the results of Hubbard et al to functions outside of the rather small class of polynomials. The natural extension is to holomorphic functions defined on a domain containing the closed unit disk. Such a function has only finitely many zeros in the unit disk, and is sufficiently nice that Newton's Method is applicable. We have encountered many obstacles in the way of such an extension. The behavior of Julia sets of holomorphic functions other than polynomials (and rational functions) is poorly understood. Also there are problems to do with what is computable when talking about functions defined by (infinite) power series. Nonetheless we now believe we have a provably correct algorithm for finding all zeros in the unit disk of a holomorphic function. It is however very inefficient. Perhaps further understanding will lead to a better algorithm.

A full project report, and various applets, including those calculating all roots of a given complex polynomial, can be found here.