PUMA
Istituto di Informatica e Telematica     
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



Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional