Multiplicative Updates for Polynomial Root Finding

Let $f(x)=p(x)-q(x)$ be a polynomial with real coefficients whose roots have nonnegative real part, where $p$ and $q$ are polynomials with nonnegative coefficients. In this paper, we prove the following: Given an initial point $x_0>0$, the multiplicative update $x_{t+1}=x_{t}p(x_t)\mathrm{/}q(x_t)$ ($t=0,1,\dots$) monotonically and linearly converges to the largest (resp. smallest) real roots of $f$ smaller (resp. larger) than $x_0$ if $p(x_0)<q(x_0)$ (resp. $q(x_0)<p(x_0)$). The motivation to study this algorithm comes from the multiplicative updates proposed in the literature to solve optimization problems with nonnegativity constraints; in particular many variants of nonnegative matrix factorization.