Favati P., Lotti G., Menchi O., Romani F. An infinite precision bracketing algorithm with guaranteed convergence. Technical report, 1995. |

Abstract (English) |
The computational cost of a bracketing algorithm in the bit model of computation is analyzed, when working with a finite arithmetic of unbounded accuracy. The complexity measure here used is the number of bit operations, seen as a function of the required absolute error of the result. In this model the convergence of the classical bisection method (as well as that of any bracketing method which requires the function sign) is not ensured when no information on the behaviour of the function is available. A modified bisection algorithm with guaranteed convergence is proposed and an upper bound to its computational cost is given. | |

Subject | G.1.5 Roots of Nonlinear Equations 65H05 Single equations |

Open access Restricted Private