A method computing multiple roots of inexact polynomials

ABSTRACT

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 nonsingular least squares problem on a pejorative manifold, and calculates multiple roots simultaneously. To fulfill the input requirement of Algorithm I, we design a numerical GCD-finder, including a partial singular value decomposition and an iterative refinement, as the main engine for Algorithm II that calculates the multiplicity structure and the initial root approximation. The combined method calculates multiple roots with high forward accuracy without using multiprecision 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.

REFERENCES

• 1: Paulina Chin , Robert M. Corless , George F. Corliss, Optimization strategies for the approximate GCD problem, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.228-235, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281622]
• 2: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
• 3: J. P. Dedieu , M. Shub, Newton's method for overdetermined systems of equations, Mathematics of Computation, v.69 n.231, p.1099-1115, July 2000 [doi>10.1090/S0025-5718-99-01115-1]
• 4: J. W. Demmel, On condition numbers and the distance to the nearest III-posted problem, Numerische Mathematik, v.51 n.3, p.251-289, July 1987 [doi>10.1007/BF01400115]
• 5: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 6: I. Z. Emiris, A. Galligo, and H. Lombardi. Certified approximate univariate GCDs. J. Pure Appl. Algebra, 117/118:229--251, 1997.
• 7: M. R. Farmer and G. Loizou. An algorithm for the total, or partial, factorization of a polynomial. Math. Proc. Camb. Phil. Soc., 82:427--437, 1977.
• 8: W. Gautschi. Questions of numerical condition related to polynomials. In G. H. Golub, editor, MAA Studies in Mathematics, Vol. 24, Studies in Numerical Analysis, pages 140--177, USA, 1984. The Mathematical Association of America.
• 9: Masao Igarashi , Tjalling Ypma, Relationships between order and efficiency of a class of methods for multiple zeros of polynomials, Journal of Computational and Applied Mathematics, v.60 n.1-2, p.101-113, June 20, 1995
• 10: W. Kahan. Conserving confluence curbs ill-condition. Technical Report 6, Computer Science, University of California, Berkeley, 1972.
• 11: N. K. Karmarkar , Y. N. Lakshman, On approximate GCDs of univariate polynomials, Journal of Symbolic Computation, v.26 n.6, p.653-666, Dec. 1998 [doi>10.1006/jsco.1998.0232]
• 12: Victor Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, v.39 n.2, p.187-220, June 1997 [doi>10.1137/S0036144595288554]
• 13: D. Rupprecht. An algorithm for computing certified approximate GCD of n univariate polynomials. J. Pure and Appl. Alg., 139:255--284, 1999.
• 14: H. J. Stetter. Condition analysis of overdetermined algebraic problems. In e. a. V.G. Ganzha, editor, Computer Algebra in Scientific Computing--CASC 2000, pages 345--365, Springer, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
polynomial root-finding