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ϵ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 log2 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(n3 log4 n) for the bit complexity of the mentioned stability problems.