0
$\begingroup$

For large degree polynomials (>=5) with real coefficients, the only general root-finding algorithms are approximate. Since polynomials might have complex roots, any algorithm for finding the real roots of a polynomial must apply an approximate root-finding algorithm, then filter the results to obtain only real solutions.

A naive algorithm for filtering the results for real solutions, by simply checking that the imaginary part is identical to 0:

Filter Algorithm 1:

\begin{align*} \text{complex}(x) = \begin{cases} \text{True} & \text{imag}(x) = 0, \\ \text{False}& \text{else} \end{cases} \end{align*}

Is insufficient, since, due to the approximate nature of the initial root-finding, real solutions are not guaranteed to have imaginary parts that are identical to 0.

One possibility is to apply a "tolerance" to check that the imaginary part is not above a certain threshold. However, complex roots may have small imaginary parts, and this risks identifying actual complex roots as real ones.

Another possibility may be to check to see if the complex conjugate of a particular root is also a root, but, since we have already narrowed our search to approximate roots with small imaginary parts, then this will not help separate real roots from complex ones.

How can we determine with higher precision if a particular approximate root is "truly" a complex root, or is actually a real root with a floating-point error imaginary part?

$\endgroup$
8
  • $\begingroup$ Plug in the real component of the root back into the polynomial. See how close to zero it is. $\endgroup$ – Don Thousand Sep 23 '19 at 17:24
  • $\begingroup$ @DonThousand, but, if $p$ is my polynomial and $p(a+\epsilon i) \approx 0$ where $\epsilon$ is very small, then since $p$ is continuous, $p(a) \approx 0$, since a small change in $x$ must produce a small change in $y$. $\endgroup$ – Him Sep 23 '19 at 17:35
  • $\begingroup$ Does the polynomial have real coefficients (or coefficients which are all real multiplies of a fixed complex number that can be divided out)? If so, then you can attempt to filter by using an intermediate value theorem checker: look at the real part of your proposed root, move a little left and a little right and check whether the polynomial changed sign. If it did, then you know the root you have approximated is real. If it didn't, then there are some things that could make it a false negative, some of which can be ruled out with further calculation (e.g. by finding roots of the derivative). $\endgroup$ – Ian Sep 23 '19 at 18:05
  • $\begingroup$ (Cont.) If the polynomial has "fundamentally complex" coefficients (i.e. the coefficients are not real multiples of a fixed complex number) then this problem is more or less hopeless in general (all you can really do is confirm that the root is within some horizontal strip of the real axis). $\endgroup$ – Ian Sep 23 '19 at 18:06
  • $\begingroup$ @Ian, my polynomials all have real coefficients. I have edited the question to reflect your observation. $\endgroup$ – Him Sep 23 '19 at 18:09
0
$\begingroup$

You simply can't tell, by nature of it being an approximate algorithm. Even if the imaginary part is $0$ as a floating point number, that doesn't rule out that the imaginary part is nonzero, but smaller than the smallest possible floating point number.

The way to ensure that the root is real is by using a root finding algorithm whose search space is the real numbers instead of the complex numbers. Root finding algorithms for real roots of real valued functions exist, like the bisection method or Newton's method. You have to have some alternative way of guaranteeing that you've found all of the roots, but this has probably been done if it has been done for complex roots.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.