A rational cubic clipping method for computing real roots of a polynomial

• Use two rational cubics as bounding polynomials.
• Achieve a convergence rate 7 for a single root.
• It can achieve linear computational complexity O(n)O(n) for improved cases.

Many problems in computer aided geometric design and computer graphics can be turned into a root-finding problem of a polynomial equation. Among various solutions, clipping methods based on the Bernstein–Bézier form usually have good numerical stability. A traditional clipping method using polynomials of degree r   can achieve a convergence rate of r+1r+1 for a single root. It utilizes two polynomials of degree r   to bound the given polynomial f(t)f(t) of degree n  , where r=2,3r=2,3, and the roots of the bounding polynomials are used for clipping off the subintervals containing no roots of f(t)f(t). This paper presents a rational cubic clipping method for finding the roots of a polynomial f(t)f(t) within an interval. The bounding rational cubics can achieve an approximation order of 7 and the corresponding convergence rate for finding a single root is also 7. In addition, differently from the traditional cubic clipping method solving the two bounding polynomials in O(n2)O(n2), the new method directly constructs the two rational cubics in O(n)O(n) which can be used for bounding f(t)f(t) in many cases. Some examples are provided to show the efficiency, the approximation effect and the convergence rate of the new method.