Efficient algorithms for computing the nearest polynomial with constrained roots
Markus A. Hitz, Erich Kaltofen · 1998
Continuous changes of the coecients of a polynomial move the roots continuously.We consider the problem nding the minimal perturbations to the coecients to move a root to a given locus, such as a single point, the real or imaginary axis, the unit circle, or the right half plane.We measure minimality in both the Euclidean distance to the coecient vector and maximal coecient-wise change in absolute value (in nity norm), either with entirely real or with complex coecients.If the locus is a piecewise parametric curve, we can give ecient, i.e., polynomial time algorithms for the Euclidean norm; for the in nity norm we present an ecient algorithm when a root of the minimally perturbed polynomial is constrained to a single point.In terms of robust control, we are able to compute the radius of stability i n t h e Euclidean norm for a wide range of convex open domains of the complex plane.