05.15.06
Finding the roots of polynomials
We all learn at some point in time how to approximate real roots of functions via Newton’s method. To refresh your memory, Newton’s method is a wonderful simple iterative process that, given a differentiable function, produces a sequence of numbers that, if it converges to some number, then that number is guaranteed to be a root. In fact, there is a very straightforward geometric interpretation of the method, which can be summarized in the sentence:
Follow the tangent line to the curve at your current x0, and see where it meets the x axis. Then use this intercept as the next x0.
Drawing a picture will convince you immediately. But what about complex functions and complex roots? Will Newton’s method work then? It would largely depend on the point you start. For instance, to find roots to 
, using Newton’s method, if we start with a real value we will remain within the real numbers, and thus will never reach the two imaginary roots. Imagine even more complicated functions.
Ok, so the general problem might not be too easy, but what about the special case of polynomials? Surely there should be an easy way for polynomials!
There’s some obvious things you can do. For instance, you can compute the greatest common divisor of your polynomial and its derivative, and if this divisor is not a constant, then its roots are multiple roots of your polynomials. Since this g.c.d has smaller degree, this can make our live easier, as we can apply whatever method we have to the two factors that we get this way.
Ok, that wasn’t very interesting, right? Chances are that all the roots of the polynomial are distinct. I just found out that there is a wonderful method, called the Durand-Kerner method, which, when applied to a polynomial with distinct roots, gives us all the roots at the same time, pretty fast and with great precision. The idea is to start with a random set of numbers as our initial guesses for the roots, and keep improving them all at the same time via a very simple iterative process.
I haven’t seen the theory behind this method, but I implemented it and it works great! It will not work for a polynomial of degree less than 2 though, so you’ll have to find some other way to compute the roots of those polynomials 
.
