8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ IIRC, none of the coefficients are superfluous; you need to know their values to compute the later polynomials in the sequence. That said, you can do other things, e.g. multiplying $p_2$ through by $27$ to clear denominators. (or, actually, tweak how you do the calculation of $p_2$ to avoid fractions entirely) $\endgroup$
    – user14972
    Commented Dec 10, 2016 at 19:00
  • 1
    $\begingroup$ Do you know any faster way to find number of real roots ? $\endgroup$
    – S.H.W
    Commented Dec 10, 2016 at 20:00
  • $\begingroup$ @Hurkyl Can you help ? $\endgroup$
    – S.H.W
    Commented Dec 16, 2016 at 19:30

2 Answers 2

3
+100
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Thank you , Your answer is very good but I'm looking for a way that we don't perform division . Because we only need to determine the sign of polynomial and for doing it , we only need to first term of reminder with its degree and other terms are useless . $\endgroup$
    – S.H.W
    Commented Feb 9, 2017 at 5:02
  • $\begingroup$ @S.H.W I'm fairly certain that this is the fastest way in general (this is really just shorthand long division of course). All you have to do is carry it out to the term you want — this took me 20 seconds to do by hand with a calculator (MathJax is a different story). You could of course replace the coefficients with variables and get a formula involving only addition and multiplication for the first term by doing synthetic division, but remembering the formula wouldn't be easy and it's really not any faster than just doing plain old synthetic division $\endgroup$ Commented Feb 9, 2017 at 5:06
  • $\begingroup$ @S.H.W the easiest way in general is still to start with Descartes rule of signs and do some analysis, if you ask me...but perhaps not the fastest $\endgroup$ Commented Feb 9, 2017 at 5:08
  • $\begingroup$ The Descartes rule of signs gives us only upper bound for roots and also doesn't determine that roots are real or complex. $\endgroup$
    – S.H.W
    Commented Feb 9, 2017 at 5:14
  • $\begingroup$ @S.H.W sure, hence the "with analysis" part of my comment above $\endgroup$ Commented Feb 9, 2017 at 5:15
0
$\begingroup$

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

enter image description here

$\endgroup$
6
  • 1
    $\begingroup$ No , I know that sturm's method using computer is very good. But I want to use it with hand $\endgroup$
    – S.H.W
    Commented Feb 2, 2017 at 12:39
  • $\begingroup$ In other words , I'm looking for method that helps me to find number of real roots for polynomials in general. (Without using computer) $\endgroup$
    – S.H.W
    Commented Feb 2, 2017 at 12:41
  • $\begingroup$ Then I would probably not start with Sturm since it is very powerful but very tedious instrument. Starting with Descarte's rule of signs? Checking which infinity the polynomial diverges to? Investigating its shape? I am afraid when it comes to simplicity, there is very little that would be general. $\endgroup$
    – Jan
    Commented Feb 2, 2017 at 12:46
  • $\begingroup$ The Descarte's rule of signs only gives us a upper bound and also doesn't care about real or complex roots $\endgroup$
    – S.H.W
    Commented Feb 2, 2017 at 12:50
  • $\begingroup$ Well, the last thing I can offer, since I do not know more, is this book on polynomials (especially 1.4 helped me in the past): springer.com/gb/book/9783540407140 $\endgroup$
    – Jan
    Commented Feb 2, 2017 at 13:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .