A Fast Iterative Method for Determining the Stability of a Polynomial

We present an iterative numerical method for solving two classical stability problems for a polynomial $p(x)$ of degree $n$: the Routh-Hurwitz and the Schur-Cohn problems. This new method relies on the construction of a polynomial sequence $\{ p^{(k)}(x) \}_ {k\in {\bf N}}$, $p^{(0)}(x)=p(x)$ , such that $p^{(k)}(x)$ quadratically converges to $(x-1)^p (x+1)^{n-p}$ whenever the starting polynomial $p(x)$ has $p$ zeros with positive real parts and $n-p$ zeros with negative real parts. By combining some new results on structured matrices with the fast polynomial arithmetic, we prove that the coefficients of $p^{(k)}(x)$ can be computed starting from the coefficients of $p^{(k-1)}(x)$ at the computational cost of $O(n\log^2 n)$ arithmetical operations. Moreover, by means of numerical experiments, we show that the $O(n\log n)$ bit precision of computations suffices to support the stated computational properties. In this way, apart from a logarithmic factor, we arrive at the current best upper bound of $O(n^3\log^4 n)$ for the bit complexity of the mentioned stability problems.