Quadratic Interval Refinement for Real Roots
It provides a faster root refinement method for polynomials and well-behaved functions, combining the robustness of bisection with the speed of Newton's method.
The paper introduces a hybrid Bisection-Newton algorithm for refining real root intervals that achieves quadratic convergence without requiring derivative evaluation, using arbitrary precision rational arithmetic.
We present a new algorithm for refining a real interval containing a single real root: the new method combines characteristics of the classical Bisection algorithm and Newton's Iteration. Our method exhibits quadratic convergence when refining isolating intervals of simple roots of polynomials (and other well-behaved functions). We assume the use of arbitrary precision rational arithmetic. Unlike Newton's Iteration our method does not need to evaluate the derivative.