An improved rational cubic clipping method for computing real roots of a polynomial

摘要

The root-finding problem has wide applications in geometric processing and computer graphics. Previous rational cubic clipping methods are either of convergence rate 7/k with O(n2) complexity, or of convergence rate 5/k with linear complexity, where n and k are degree of the given polynomial and the multiplicity of the root, respectively. This paper presents an improved rational cubic clipping of linear complexity, which can achieve convergence rate 7/k, or a better one for a multiple root such that k ≥ 2. Numerical examples illustrate both efficiency and convergence rate of the new method.