# 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.