0
$\begingroup$

When computing the nth root of a polynomial equation using bisection search, how does one find the upper and lower bounds of where to search?

Is there some kind of formula to bound the nth root to a polynomial equation should be?

Take for example cube roots.

Take the cube root of any number, where is it at least and at most?

$\endgroup$
0
$\begingroup$

All polynomials are continuous, which is essentially saying that their graph could be traced without lifting your pencil from the paper. So then, if $\alpha$ is a root of a nonconstant polynomial, $p$,* the polynomial should pass $0$ at $\alpha$ and take a value near $0$ for $x$ near $\alpha$. But we made the assumption that $p$ is nonconstant so $p$ must take small positive/negative values. But then since $p$ is continuous, for a given side of $\alpha$, in the neighbourhood of $\alpha$, it should have the same sign for all values it takes. It should be strictly negative on one side and strictly positive on the other. This is essentially the intermediate value theorem.

By testing values near $\alpha$, we can check their sign and determine whether $p$ is above or below $0$. The root, $\alpha$ must always lie between an $a$ and $b$, such that $p(a)$ and $p(b)$ have opposite signs. When we test a value, $c$, between $a$ and $b$, we can check its sign and discern whether $\alpha$ is in $(a,c)$ or $(c,b)$. This is the method of bisection. We are iteratively improving the bounds by testing values in the interval. I believe there is no general closed formula for the $n$'th bound without a recurrence relation, since it relies on you actively choosing which side of $c$ contains $\alpha$.

enter image description here


* Ignoring roots of even multiplicity; if that is the case, the function would not have a change of sign and the method of bisection would fail.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Is there some kind of formula to bound the $n$th root to a polynomial equation should be?

If you mean a bound for the (complex) roots of an univariate$^1$ polynomial over $\mathbb R$ (or $\mathbb C$) of degree $n$: there are many upper bounds, see for example bounds on all roots in wikipedia.

These bounds are usually in terms of the polynomial's coefficients; just from the degree alone without any further knowledge you cannot give such bounds.

$^1$A polynomial in 1 variable.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy