We present a combination of two novel algorithms that accurately calculate multiple roots of general polynomials. For a given multiplicity structure and initial root estimates, Algorithm I transforms the singular root-finding into a nonsin-gular least squares problem on a pejorative manifold, and calculates multiple roots simultaneously. To fulfill the input requirement of Algorithm Ⅰ, we design a numerical GCD-finder, including a partial singular value decomposition and an iterative refinement, as the main engine for Algorithm Ⅱ that calculates the multiplicity structure and the initial root approximation. The combined method calculates multiple roots with high forward accuracy without using multipreci-sion arithmetic, even if the coefficients are inexact. This is perhaps the first blackbox-type root-finder with such capabilities. To measure the true sensitivity of the multiple roots, a pejorative condition number is proposed and error bounds are given. Extensive computational experiments are presented. The error analysis and numerical results confirm that a polynomial being ill-conditioned in conventional sense can be well conditioned pejoratively. In those cases, the multiple roots can be computed with remarkable accuracy.
展开▼
