Descartes rule of sign can be used to isolate the intervals containing the real roots of a real polynomial. The rule bounds the number of roots from above, that is, it is exact only for intervals having zero or one root. In methods like VCA, VAS and similar, it is used to count the number of sign changes to determine the number of roots.My question is, what to do if the rule reports, say, two sign changes for interval which does not contain any roots?

Question

empatteMattmkezo · Accepted Answer

Unfortunately the answer is: subdivide and go on. The rule-of-signs-predicate is not able to tell whether there are any roots, and if you have no additional means to do so, you have no other option.However, there are theorems which tell you that this won&#039;t happen too often. Short summary of the &quot;easy&quot; cases: If you count the sign variations v of the polynomial which &quot;describes&quot; the interval   [  a  ,  b  ], then-   v will be 0 if no (complex) root of the input polynomial is contained in the disc in the complex plane with diameter   a  b, and-   v will be 1 if only one (complex) root of the input is contained un the union of the circumcircles of the two equilateral triangles that have   a  b as one side, assuming that this root is simple.There are more detailed versions of these theorems, but in a nutshell it boils down to: you will count the right thing unless there is a cluster of complex roots close to the interval (w.r.t. the scale/precision you are currently considering), and you have to &quot;zoom in&quot; to deblur and resolve the situation.However, if you have reasons to believe that there is a wide range without any roots, note that &quot;subdivide&quot; is not necessarily the same as &quot;bisect&quot;. You are free to choose other subdivision methods; this eventually leads to fancier algorithms like Continued Fraction solver (VAS; praised in practice, at least for some benchmarks, but their actual merit is disputed) or combinations of Newton iteration and Descartes

Descartes rule of sign can be used to isolate the intervals containing the real roots of a real poly

Answered question

Answer & Explanation

New Questions in College Statistics