Ten methods to bound multiple roots of polynomials

摘要

Given a univariate polynomial P with a k-fold multiple root or a k-fold root cluster near some z̃, we discuss nine different methods to compute a disc near z̃ which either contains exactly or contains at least k roots of P. Many of the presented methods are known, some are new. We are especially interested in the behaviour of methods when implemented in a rigorous way, that is when taking into account all possible effects of rounding errors. In other words every result shall be mathematically correct. We display extensive test sets comparing the methods under different circumstances. Based on the results we present a tenth, a hybrid method combining five of the previous methods which, for given z̃, (i) detects the number k of roots near z̃ and (ii) computes an including disc with in most cases a radius of the order of the numerical sensitivity of the root cluster. Therefore, the resulting discs are numerically nearly optimal.