Fast approach for computing roots of polynomials using cubic clipping

This paper presents a new approach, called cubic clipping, for computing all the roots of a given polynomial within an interval. In every iterative computation step, two cubic polynomials are generated to enclose the graph of the polynomial within the interval of interest. A sequence of intervals is then obtained by intersecting the sequence of strips with the abscissa axis. The sequence of these intervals converges to the corresponding root with the convergence rate 4 for the single roots, 2 for the double roots and super-linear 4 3 for the triple roots. Numerical examples show that cubic clipping has many expected advantages over Bezier clipping and quadratic clipping. We also extend our approach by enclosing the graph of the polynomial using two lower degree k < n polynomials by degree reduction. The sequence of intervals converges to the corresponding root of multiplicity s with convergence rate k+1/s. (C) 2009 Elsevier B.V. All rights reserved.