The computation of multiple roots of a polynomial using structure preserving matrix methods.

Solving polynomial equations is a fundamental problem in several engineering and
science fields. This problem has been handled by several researchers and excellent
algorithms have been proposed for solving this problem. The computation of the
roots of ill-conditioned polynomials is, however, still drawing the attention of several
researchers. In particular, a small round off error due to floating point arithmetic is
sufficient to break up a multiple root of a polynomial into a cluster of simple closely
spaced roots. The problem becomes more complicated if the neighbouring roots are
closely spaced. This thesis develops a root finder to compute multiple roots of an
inexact polynomial whose coefficients are corrupted by noise. The theoretical development
of the developed root solver involves the use of structured matrix methods,
optimising parameters using linear programming, and solving least squares equality
and nonlinear least squares problems.
The developed root solver differs from the classical methods, because it first computes
the multiplicities of the roots, after which the roots are computed. The experimental
results show that the developed root solver gives very good results without the
need for prior knowledge about the noise level imposed on the coefficients of the
polynomial.