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.

```

```
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.
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.

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).

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

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
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search