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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)40-50
Journal / PublicationComputer Aided Geometric Design
Volume38
Publication statusPublished - 1 Oct 2015

Abstract

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+1 for a single root. It utilizes two polynomials of degree r to bound the given polynomial f(t) of degree n, where r=2,3, and the roots of the bounding polynomials are used for clipping off the subintervals containing no roots of f(t). This paper presents a rational cubic clipping method for finding the roots of a polynomial 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), the new method directly constructs the two rational cubics in O(n) which can be used for bounding f(t) in many cases. Some examples are provided to show the efficiency, the approximation effect and the convergence rate of the new method.

Research Area(s)

  • Approximation order, Convergence rate, Rational cubic clipping method, Root-finding