Sturm's Method for Counting Real Roots

Jacques Sturm developed a method which computes the number of distinct real roots of a real polynomial. This technique can be used to count the total number (of distinct) real roots or just count the number of roots lying in a particular interval.

Sturm says to take a polynomial $r_0=p(x)$ and compute its derivative $r_1=p'(x)$. Then divide $p(x)$ by $p'(x)$. This yields a polynomial quotient and remainder. Let $r_2 = - \mathrm{Remainder}(r_0,r_1)$ be the negative of the remainder. Now continue dividing $r_{i-1}$ by $r_{i}$ setting $r_{i+1}$ equal to the negative remainder until a zero remainder is achieved (this must happen eventually since each division yields a negative remainder of lower degree).

Next, take the list negative remainders (as well as $p(x)$ and $p'(x)$) and evaluate each at $x=a$. This yields a list of real numbers. Count the number of sign changes in this list (ignoring zeros) and call the number of sign changes $A$. Then do the same for $x=b$ and call the number of sign changes $B$. If neither $x=a$ nor $x=b$ is a repeated root, the number of distinct roots in the interval $I=(a,b] = \{ x\in \mathbb{R} \;|\; a \lt x\leq b\}$ is exactly $A-B$.

When either $x=a$ or $x=b$ is a repeated root, substituting that number into the sequence of polynomials will yield a string of 0's. But all is not lost, if the entire sequence is divided by its last nonzero term, the modified Sturm sequence then applies as a method.

Note that we can "evaluate the Sturm Sequence at $\pm\infty$" (where limits are actually being taken to $\pm\infty$) and use this method to find the total number of distinct real roots of $p(x)$ on the whole real line $\mathbb{R}=(-\infty,\infty)$.

The computation above is powered by SageMath. The Sage code is embedded in this webpage's html file. To view the code instruct your browser to show you this page's source. For example, in Chrome, right-click and choose "View page source".

Wikipedia entry for Sturm's method.