Find number of real roots using Sturm's method.

Question

Sturm's method for finding number of real roots is very good . But it is time consuming to find reminder in division of polynomials specially for high degrees. I want to know , Is there any way to find first term of reminder? (Because in Sturm's method we need to determine sign of reminder) For example : $f(x) = 3x^3 + 5x^2 - 6x- 2$ By Sturm's method : $$ p_0(x) = 3x^3 + 5x^2 - 6x- 2$$ $$p_1(x) = 9x^2 + 10x - 6 $$ $$p_2(x) = \frac{158x}{27 } + \frac{8}{9}$$ $$p_3(x) = +\frac{45630}{6241} $$ and now we must determine signs of $p_i(-\infty)$ and $p_i(+\infty)$ Which first gives us $-$ , $+$ , $-$ , $+$ for three changes and the second $+$ , $+$ , $+$ , $+$ for zero sign changes . Therefore ,we have $3-0 = 3$ real roots . It is obvious that calculation for solving this problem is very hard and we don't use coefficients like $\frac{158}{27 }$ for determining sign of $p_i(x)$

Answer 1

All errors in prior versions were fixed. Note that this is a long post, and was a nightmare to encode in MathJax

I think that Synthetic Division would really help you. It basically simplifies the process of Polynomial Long Division. I will use your example from above. $$\frac{3x^3 + 5x^2 - 6x- 2}{9x^2 + 10x - 6}=\frac{p(x)}{q(x)}$$ Let $p(x)$ be the polynomial in your numerator and $q(x)$ be a monic polynomial in the denominator. To make the denominator monic we must divide by the leading coefficient, to get a new $q^*(x) = x^2+\frac{10}{9}x-\frac{2}{3}$

We start by drawing this table

$$\begin{array}{c|rrrr}&x^3 & x^2 & x^1 & x^0\\ \hline& & & &\\ {} & & & & \\ & & & &\\\hline & & & & {} \end{array}$$ Now let's fill in the coefficients of $p(x)$ in the first line. $$\begin{array}{c|rrrr}& x^3 & x^2 & x^1 & x^0\\ \hline& 3 & 5 & -6 & -2\\ {} & & & & \\ & & & &\\\hline & & & & {} \end{array}$$

We now negate all the coefficients of $q^*(x)$ and include all of them except the first going diagonally up; for example, since $q^*(x) = x^2+\frac{10}{9}x-\frac{2}{3}$ our negated coefficients will be $\{-1,-\frac{10}{9},\frac{2}{3}\}$ and we will only use $\{-\frac{10}{9},\frac{2}{3}\}$ $$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & \\ {-\frac{10}{9}}& & & &\\\hline & & & & \end{array}$$ We now "drop" the first coefficient $$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & \\ {-\frac{10}{9}}& & & &\\\hline & & 3 & & \end{array}$$ We now multiply this "dropped" number by our coefficients of $q(x)$ $$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & 2\\ {-\frac{10}{9}}& & & -\frac{10}{3} &\\\hline & & 3 & & \end{array}$$

We now perform add vertically in the second column $$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & 2\\ {-\frac{10}{9}}& & & -\frac{10}{3} &\\\hline & & 3 & \frac{5}{3} & \end{array}$$

Repeating the last couple steps until the middle row is filled $$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & 2&\frac{10}{9}\\ {-\frac{10}{9}}& & & -\frac{10}{3} &-\frac{50}{27}\\\hline & & 3 & \frac{5}{3} & \end{array}$$

$$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & 2&\frac{10}{9}\\ {-\frac{10}{9}}& & & -\frac{10}{3} &-\frac{50}{27}\\\hline & & 3 & \frac{5}{3} & \frac{158}{27} \end{array}$$ Now we just add the last column vertically $$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & 2&\frac{10}{9}\\ {-\frac{10}{9}}& & & -\frac{10}{3} &-\frac{50}{27}\\\hline & & 3 & \frac{5}{3} & \frac{158}{27} &-\frac{8}{9} \end{array}$$ Now, the we look at the degree of $q(x)$ and draw a dividing line that far from the right; here $q(x)$ is of degree $2$, so we put a dividing line $2$ from the right

$$\begin{array}{cc|rrrr}& & x^3 & x^2 & x^1 & x^0\\ \hline& & 3 & 5 & -6 & -2\\ & \frac{2}{3} & & & 2&\frac{10}{9}\\ {-\frac{10}{9}}& & & -\frac{10}{3} &-\frac{50}{27}\\\hline & & 3 & \frac{5}{3} &|\phantom{-} \frac{158}{27} &-\frac{8}{9} \end{array}$$
The left side of the dividing line has the coefficients of the result of our division, and the right side has the coefficients of the remainder. Both are written from largest power to smallest power. Since both sides have $2$ coefficients, both the result and remainder are of degree $1$. To get our answer we must write the result and remainder in standard form and remember that we divided by $9$ in the denominator $$\frac{3x^3 + 5x^2 - 6x- 2}{9x^2 + 10x - 6} = \frac{1}{9}\left(3x+\frac{5}{3}+\frac{\color{red}{\frac{158}{27}x-\frac{8}{9}}}{9x^2 + 10x - 6}\right)$$
Now, since all you need for Sturm's Method is the remainder, you can just stop after drawing the dividing line, which saves time.

Answer 2

Sturm polynomials are very powerful but I am afraid the time consuming part is inevitable. Are you trying to do this on a computer? For example Mathematica can do this very fast. Below is an example. Hope it helps. (I've added couple of related commands.)