Mathematical background

Budan-Fourier algorithm is a simple method which enable to determine easily some information on the number of root of a given univariate polynomial within a given interval. Let $P$ the polynomial:

$$P=a_0+a_1x+\ldots+a_nx^n$$

and $P^{(n)}$ its n-th derivative. Let the interval $(\underline{x},\overline{x})$ the interval in which we are looking for roots. We assume that $P(\underline{x}) \not=0$, $P(\overline{x}) \not=0$ and $a_0 \not= 0$. We construct the sequence $L=\{P(\underline{x}),P^{(1)}(\underline{x}),\ldots,P^{(n)}(\underline{x})\}$ from which we exclude the 0 element. Similarly we construct the sequence $U=\{P(\overline{x}),P^{(1)}(\overline{x}),\ldots,P^{(n)}(\overline{x})\}$ (a special treatment has to be applied for the zero element of $U$, see [13]). Let $\underline{N}$ the number of change of sign in $L$ and $\overline{N}$ the number of change of sign in $U$. Then the number of real roots of $P$ in $(\underline{x},\overline{x})$, counted with their order of multiplicity, is $\underline{N}-\overline{N}$ or lower than this number by an even number.