Number of zeros of interval polynomials (Q455830)

An interval polynomial of degree \(n\) is defined by \[ [f](x):= \sum^n_{i=0} [a_i,b_i] x^i:= \Biggl\{\sum^n_{i=0} f_i x^i: f_i\in [a_i, b_i],\, i= 0,1,\dots, n\Biggr\}=: [{\mathcal L}f(x),{\mathcal U}f(x)], \] where \([a_i, b_i]\subset\mathbb{R}\), \(i= 0,1,\dots,n\), are bounded closed intervals. The real zero set \(Z([f])\) of \([f](x)\) is introduced as \(Z([f]):=\{t_0\in \mathbb{R}: \exists h\in [f](x): h(t_0)= 0\}\). This set is composed of several closed intervals. Each of these intervals is called an interval zero of \([f](x)\). The aim of the paper is to count the interval zeros of \([f](x)\) contained in some given interval \((a, b)\subseteq\mathbb{R}\) without computing the roots of any polynomials. It is shown that this number can be obtained by counting the roots of \(g(x):={\mathcal L}f(x)\cdot{\mathcal U}f(x)\) in \((a,b)\) and checking how many of them are simultaneously local minimizers and how many are local maximizers. This is done by means of an algorithm for univariate polynomials \(p\) which is based on the canonical Sturm sequence of \(p\), Sturm's theorem on it and Sylvester's extension of Sturm's result. An example illustrates the theory.