Polynomial real root approximation using continued fractions

Abstract

A method with polynomial computing time bound is presented for the approximation of real roots of polynomial equations using continued fractions; it is based on an idea by Lagrange [10] and Vincent's theorem [17], and it has been implemented using exact (infinite precision) integer arithmetic algorithms. A theoretical analysis of the computing time of this method is given along with some empirical results.

Keywords:

• Analysis of (exact) algorithms
• polynomial real root isolation and approximation
• Cauchy's rule
• Lagrange's method
• Vincent's theorem

C.R. Categories:

• 11
• G.1.5