There exist variants of Newton’s method with safeguards against non-convergence (escape bracket, not converging “fast enough”, etc, in which case they switch to a bracketing method like Brent’s or bisection). Various implementations I found differ in details, and I could not find a paper with convergence analysis.
Is there a reference that discusses these methods in detail?
For a while, anytime I needed to solve a new univariate problem I tried different univariate solvers and always found that Brent’s method (from Optim.jl) was performing the best. So now I just always reach for that.
I do remember seeing recently a post here about someone implementing the ITP method in a new package but I have not given it a try. This method would be more similar to what you described.
Just to clarify: I am not asking for recommendations on rootfinding methods.
The question is about a very specific family of methods, and is mainly motivated by curiosity. Two general recommendations I encounter are
get close to a root, then use Newton-Raphson for “polishing”,
try Newton-Raphson, fall back to some bracketing method if it “fails”
But in practice I find it hard to implement these in a robust and practical way, because the criteria for switching are quite fuzzy. This is a shame, since for some functions derivatives are readily available, so a bracketing method that uses derivatives would be useful.
If we are talking about a continuous function and a bracket which is always at least cut in half, then we have a guarantee that the method converges by the intermediate value theorem. Taking the newton step when it makes the interval smaller than half it’s current size and the bisection step otherwise can only make convergence faster as the interval will always be smaller than or equal to half it’s initial size at every step.
I vaguely remember W. Kahan giving a talk about how he got this idea into the solver (the solve button) for the HP35 programmable calculator. This was from the late 1970s and I do not know if he published it or not. I think the opening gambit was bisection and then the solver switched to Newton when the intervals got small.
I forget if the convergence analysis is in detail, but in the LithBoonkkampIJzermanBracket method of find_zero from Roots there is an implementation of this kind of algorithm and a reference to follow up on.
Thanks, the article (non-paywall version here) was extremely informative. This is the kind of answer I was looking for, and I am delighted to learn that it is already implemented in the excellent Roots.jl.