How do computer programs looks for polynomial's complex roots ?

Question

For example the polynomials below have complex roots :

0.454*x^6+23.172*x^5
-12.33*x^4
+123.22*x^3+1.32*x^2
+122*x-642.22=0

0.874*x^6+12.143*x^5
-9.23*x^4
+982.432*x^3+3.31*x^2
+82.7*x-32.22=0

What algorithm should be used to search for the complex roots ?

Answer 1

Best Answer - Chosen by Asker

For example the Durand-Kerner method or the Bairstow's method. See source for example.

Source(s):

http://en.wikipedia.org/wiki/Durand-Kern…

Asker's Rating:

Asker's Comment:

Looks like a good method to draw a convergence map as well. Thanks a lot.

Answer 2

I'm no expert on this, but let me make some comments anyway. In the general case where the coefficients are complex numbers the Jenkins-Traub algorithm is often used. There are many other algorithms, and I'm not sure what to recommend when the coefficients are real, how ever I think even Newton's method will work, if you work in the complex plane but it may not be clear where to start it and it will converge to different roots for different starting places.

Your first polynomial has two real roots, near -51.7 and 1.4. If you find them accurately and deflate first it may be easier. Also, since your coefficients are real, if a+bi is root so is a-bi. This is not true if the coefficients are complex.

Your second polynomial is similar with two real roots, one near -18 and the other near 0.2.

I would be interested in what someone more knowledgeable has to say.

Possibly the links below might help.

Source(s):

http://math-blog.com/2008/03/06/polynomi…
http://en.wikipedia.org/wiki/Jenkins-Tra…

Answer 3

I would have the computer calculate the value of x at a randomly-chosen starting point; this will give you a point (x1, y1).
Find the derivative of the equation, which is really easy for these functions. Plug the value x1 into the derivative to get the slope of the function at that point.
Now you have a point and the slope of a line and you want to find the x-intercept of this line --> (0 - y1) = m(x - x1) --> *(m*x1 - y1)/m = x, the value of the x-intercept.
You will want to use that x-value as your next iteration and begin again.

This is basically Newton's Method, but with a computer you should be able to find real-valued roots in only a few seconds. Every time you find a real root, you can reduce the order of your original equation.

Don't forget that complex roots always come in pairs.

Answer 4

My dog is taking a nap, so I can't ask her to answer this question.

Source(s):

"Always take a good look at what you're about to eat. It's not so important to know what it is, but it's critical to know what it was."