The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Getting Complex with Euclid, Sturm, and Newton

Date: 02/20/2016 at 20:09:48
From: Ben
Subject: Is there a way to find all complex roots of any polynomial

Hello,

I would really appreciate any help with two questions regarding the 
complex roots of a polynomial.

1. Is there a way to find all of them? perhaps a complex analog to how the 
rational zero theorem lets you use synthetic division to find all of a 
polynomial's real roots?

2. How do you determine a count of the number of complex roots in a 
polynomial (or whether it has any at all) without undertaking any lengthy 
calculations that produce the actual complex roots, themselves?

To sum it up, I need to know a reliable way -- one that always works -- of 
finding all of a polynomial's complex roots after determining how many of 
them there actually are, if any.

Thank you for your time.



Date: 02/21/2016 at 12:42:06
From: Doctor Vogler
Subject: Re: Is there a way to find all complex roots of any polynomial

Hi Ben,

Thanks for writing to Dr. Math. 

First of all, the Rational Roots Theorem will tell you how many rational 
roots a polynomial has, but not how many *real* roots it has.

  https://en.wikipedia.org/wiki/Rational_root_theorem

For some complex numbers r_1 through r_n (and a is the leading coefficient 
of the polynomial), every polynomial of degree n -- with real or complex 
coefficients -- can be factored into the form

   a(x - r_1)(x - r_2)(x - r_3)...(x - r_n)

Therefore, the degree of the polynomial (n) is the number of complex 
roots, if you count multiplicity (which means that if r_1 = r_2, then we 
still count it twice).

So if you mean the number of complex roots counting multiplicity, then the 
answer is the degree of the polynomial.

If you mean *unique* complex roots (that is, *not* counting multiplicity), 
then you need to find out how many roots are multiple. Most polynomials do 
not have multiple roots, but there is a simple way to find out which 
ones do:

Compute the derivative f'(x) of your polynomial f(x), and then take the 
polynomial-greatest common divisor (gcd):

   g(x) = gcd(f(x), f'(x)).

This polynomial will be a constant for most f(x) -- specifically, for all 
polynomials that have no multiple roots. Moreover, g(x) will have roots 
exactly where f(x) has multiple roots, and the multiplicity of each such 
root will be one less than the multiplicity in f(x).

For example,

    f(x) = (x - 1)^3*(x - 2)*(x - 3) 
         = x^5 - 8x^4 + 24x^3 - 34x^2 + 23x - 6

   f'(x) = 5x^4 - 32x^3 + 72x^2 - 68x + 23

To find the gcd, you use the Euclidean algorithm.

    g(x) = gcd(f(x), f'(x)) = x^2 - 2*x + 1 = (x - 1)^2.

To find multiple roots in g(x), you compute gcd(g(x), g'(x)).

With each iteration, the number by which the degree reduces is the number 
of distinct roots. This also gives you factors of the original polynomial.

Furthermore, if by "complex" (which includes real numbers) you actually 
mean non-real complex numbers, then you need to answer the question "How 
many *real* roots are there?"

For this, use Sturm's Theorem.

  https://en.wikipedia.org/wiki/Sturm_theorem

Sturm's Theorem can tell you both how many real roots a polynomial has, 
and how many roots it has in any interval you ask for. You can use this to 
do a binary search (or similar) to get close to any real roots. When you 
are close enough, you can then use Newton's Method to compute all such 
real roots to any degree of precision desired.

You can similarly use Newton's Method to calculate complex roots, but let 
me give you a word of warning. If your polynomial has only real 
coefficients, and you start with a real initial guess, then all iterations 
will give you real answers, so you will never reach a complex root. 
Instead, start with a non-real initial guess, which can converge to a 
non-real complex root (and, since the coefficients are all real, the 
complex conjugate of that root is also a root).

I don't know of a complex-number equivalent of Sturm's Theorem, but you 
can use this method to find all real or complex roots of a polynomial, 
as well.

Start with any initial guess, and iterate Newton's Method until it 
converges to some root r. Then divide the polynomial by x - r, giving you 
a polynomial of one lower degree. Now repeat, finding a root of that 
smaller polynomial. Keep going until you get to degree 2 (and use the 
quadratic formula) or 1 (and solve for the last root) or 0 (in which case 
you have no more roots).

See also:

Factoring Polynomials over Real and Complex Numbers
    http://mathforum.org/library/drmath/view/70443.html 

If you have any questions about this or need more help, please write back 
and show me what you have been able to do, and I will try to offer 
further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 02/21/2016 at 15:41:50
From: Ben
Subject: Thank you (Is there a way to find all complex roots of any ...)

It'll take me some time to go through what you wrote -- but I'm here to 
thank you for your help!
Associated Topics:
College Algorithms
College Imaginary/Complex Numbers

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/