Polynomials Root-Finding Using a SLEFE-Based Clipping Method

Abstract

For finding the real roots of a polynomial, we propose a clipping algorithm called SLEFE clipping and an isolation algorithm called SLEFE isolation algorithm. At each iterative step, the SLEFE clipping algorithm generates two broken lines bounding the given polynomial. Then, a sequence of intervals can be obtained by computing the intersection of the sequence of broken lines with the abscissa axis. The sequence of these intervals converges to the root with a convergence rate of 2. Numerical examples show that SLEFE clipping requires fewer iterations and less computation time than current algorithms, and the SLEFE isolation algorithm can compute all intervals that contain the roots rapidly and accurately.

Keywords

Polynomial / Root-finding / SLEFE clipping / Real root interval isolation

Funding

National Natural Science Foundation of China(No. 11471093)