A rapid robust rootfinder

Abstract:

A numerical algorithm is presented for solving one nonlinear equation in one real variable. Given ${F_X}$ with brackets A and B, i.e., $\operatorname {sign}({F_A}) = - \operatorname {sign}({F_B}) \ne 0$, the algorithm finds a zero of F, $A < X < B$. Alternately, a crossover pair is found, i.e., (X, Y): $\operatorname {sign}({F_X}) = - \operatorname {sign}({F_Y}) \ne 0$ where there is no floating-point number in the system between X and Y. This feature allows full use of machine precision. Optionally, a tolerance ${\text {TOL}} > 0$ may be given, to permit termination when $|Y - X| < {\text {TOL}}$. The method, once rapid convergence sets in, is alternation of one linear interpolation or extrapolation with one inverse quadratic interpolation. The resulting asymptotic convergence rate is competitive with other methods that refine both brackets and do not require $dF/dX$. Other merits of the algorithm are: robust calculation, efficient three-point interpolation, and superior behavior in bad cases. The algorithm is tested and compared with others.