0
$\begingroup$

While programming an equation solver (using trial and error), I came across the fact that there are multiple real and complex bounds in which all of the solutions should be. For my case, only real solutions matter. Of course, the width of this ranges is crucial to the efficiency of my algorithm, so I am trying to find the smallest range. Considering the fact that, when working with polynomial divisions, you only need one solution at a time, I was wondering if there are special limits which guarantee that at least one solution is located within them. Of course, this would only make sense if this special range - let's call it "one-solution-range" - is significantly smaller than a regular range like $B_+ = \max(1,\sum_{i=0}^n |a_i|)$. Please let me know if there is such a thing, I would also be happy if you add serious sources to the formulas.

EDIT 1:

I am aware of the fact that there are a lot of highly efficient algorithms and formulas for solving high-degree algebraic equations. However, I am not looking for these. This question is not a problem-solving type question; I just want to know if there is a smaller "one-solution-range" for algebraic equations in general.

$\endgroup$
  • $\begingroup$ What is the problem with taking some outer root radius $R$ and then applying a bracketing method like a fast variant of regula falsi or Dekker's method? A good and fast root radius is obtained by applying Newtons's method to find the one positive root of $0=R^n-|a_{n-1}|R^{n-1}-|a_{n-2}|R^{n-2}-...-|a_0|$. On the deflated quartic polynomial you can then apply Bairstow's method to get all 4 remaining roots at once. $\endgroup$ – Lutz Lehmann Nov 6 '18 at 18:50
  • $\begingroup$ @LutzL Thank you very much for this suggestion! Unfortunately, this is not the type of answer I was looking for. I am not trying to solve a problem or finding the best possible equation-solving algorithm. What I want is simply an answer to my question. Is there a smaller root radius for just one root or not? $\endgroup$ – Raphael Tarita Nov 6 '18 at 19:10
  • $\begingroup$ There are the Cauchy bounds that also use the signs of the coefficients to build a bound. I think the wikipedia page on root bounds has that too. If you can access the work of A. Akritas and blend out the proselytizing, then his implementation of M. Vincent's algorithm gives an application of this bound to find small intervals containing real roots. Under the name bisection-exclusion you can find a method that uses the inner root radius, enhanced by Graeffe iterations, to narrow down on the intervals that may contain a root. There is a real and a complex variant of that idea. $\endgroup$ – Lutz Lehmann Nov 6 '18 at 20:05
  • $\begingroup$ @LutzL Thank you, this seems helpful. I will look this up. $\endgroup$ – Raphael Tarita Nov 6 '18 at 20:15
  • $\begingroup$ On perso.math.univ-toulouse.fr/yak/curriculum-vitae you can read 21– Jean-Pierre Dedieu, Jean-Claude Yakoubsohn. Computing the real roots of a polynomial by the exclusion algorithm. If you take the target precision large enough this can serve to find bounds on the real roots. $\endgroup$ – Lutz Lehmann Nov 6 '18 at 20:28
0
$\begingroup$

What are the fast and sharp bounds on real roots of $$ f(x)=x^5+a_4x^4+...+a_1x+a_0\,? $$ As the polynomial has degree $5$ it has at least one real root. If $0$ is not a root, that is $a_0\ne 0$, then either the sequence of coefficients $(1,a_4,a_3,a_2,a_1,a_0)$ or the sign-alternated sequence $(1,-a_4,a_3,-a_2,a_1,-a_0)$ has an odd number of sign variations. Some further thought reduces this to the sign of $a_0$, the first case holds if and only if $a_0<0$. By Descartes rule we then know that in the first case there is a positive root and in the second that there is a negative real root.

Reduce the case of a negative root per the sign flips to the case of a positive root. Now apply the (Cauchy?) bound for positive roots (which I believe is older than the 2005 paper of Stefanescu that google finds first; if I remember correctly, Akritas attributes it to Cauchy):. If $N=\bigl\{k\in\{0,..,4\}:a_k<0\bigr\}$ is the set of indices of negative coefficients and $n=|N|$ then we know that for $x>0$ $$ f(x)\ge x^5-\sum_{k\in N} |a_k|x^k \ge x^5-n\cdot\max_{k\in N} |a_k|x^k=\min_{k\in N} \bigl[x^k(x^{5-k}-n⋅|a_k|)\bigr] $$ If we select $R$ as the only positive root of that last expression then we know that there can be no roots with $x>R$. Let $m$ be the index that is active at the root, then $$ R^5=n\cdot|a_m|R^m\iff R=(n⋅|a_m|)^{1/(5-m)}=\max_{k\in N}(n⋅|a_k|)^{1/(5-k)} $$ As we know from the odd number of sign variations, $a_0<0$. With $a_5=1$, $P=\{0,..5\}\setminus N$ and $p=|P|=6-n$ one finds similarly an inner root radius $r=1/s$ by considering the outer root radius by the above formula of the reversed polynomial $s^5+\frac{a_1}{a_0}s^4+...+\frac{a_4}{a_0}s+\frac1{a_0}$. Thus $$ r=\min_{k\in P}\left(\frac{|a_0|}{p⋅|a_k|}\right)^{1/(5-k)} $$ and we know that there is a positive root in $[r,R]$.

Bounded by the number of sign variations, there might be $1$, $3$ or $5$ real roots in that interval. Any further reduction of the interval to reduce the sign variations to a single one (see also Budan-Fourier, the difference in sign variations is a bound on the number of roots in that interval in extension of Descartes rule) requires the construction of a new polynomial, for instance by shifting the origin to the midpoint of the interval and then exploring the parts the same way as above.

$\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.