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!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.