Research On The Clipping Methods For The Roots-Finding Of Polynomial Equations

The problem of computing roots of polynomial equations is a core problem in the field of Computer Aided Geometry Design. It has many applications in the fields of collision detection and interference checking. With the advance of computer science and technology, we need to deal with more data and do more calculations, so we have more requirements for root-finding algorithms.For computing roots of polynomial equations rapidly and accurately, in this paper, based on the theory of SLEFE (Subdividable Linear Efficient Function Enclose), combine with the advantages of clipping methods, the SLEFE isolation algorithm and the SLEFE clipping are proposed. For the given polynomial equations, the SLEFE isolation algorithm can compute all the subintervals that contain the roots of polynomial equations rapidly and accurately. For each subinterval that contains the root, the SLEFE clipping algorithm can obtain the approximate solution of polynomial equations by iterations. Comparing with other clipping methods, the SLEFE clipping algorithm requires fewer iterations and consumes less computation time to solve the root-finding problems which have only one root within a given interval. The convergence rate of the SLEFE clipping algorithm is 2 for a single root. If the polynomial curves are confirmed convex, we use the special SLEFE clipping algorithm instead of the SLEFE clipping algorithm for higher efficiency and accuracy. An example is given to show the special SLEFE clipping algorithm can obtain better approximation effect and higher efficiency then the SLEFE clipping algorithm if the polynomial curves are confirmed convex. Finally, by analyzing the Hybrid curves and the Hybrid clipping algorithm, we proved that using the Hybrid clipping algorithm of degree k, can achieve a convergence rate of k+1 for a single root.