I have a slightly annoying problem that at first seems almost trivial, but actually seems quite tricky.
Long story short, I have a function (a polynomial in this particular case) and an interval where my function is strictly monotonically increasing and positive.
My problem is that I need to find the closest zero of the function to the left of my interval (given that it exist, of course) using some numerical algorithm. The function can be assumed to be sufficently nice, lets say $C^2$, with a finite number of zeros.
The problem trying to use standard methods like Newtons method is that there is no guarantee that the solver converge to the correct zero. Also interval based methods like Brent requires an interval where we know we can find the zero. If an interval is just guessed at random it might contain no zero as well as several.
So my question is if anyone can think of a smart algorithm to solve this problem which is decently effective and fast?
In my particular case, I have a polynomial function and I am aware of the Jenkins-Traub algorithm which can be used to find all zeros of a polynomial. While this solves my problem, it seems a bit overkill to have to calculate all zeros just to find one.
Also it would not work for a more general function.
(Actually, while writing this, I think I can use parts of the Jenkins-Traub method to solve my problem in the polynomial case. This algorithm first finds the zero/zeros of smallest absolute value and then search for zeros in order of magnitude measured by the absolute value.
Noticing this, I will typically just have to find at most a few zeros before I encounter my correct one, which might be identified as the first real zero smaller than the left endpoint of my interval obtained by the algorithm)
I assume that the root exists and I use the key fact that $f(a)$ is positive (with $a<b$).
So, two cases
-$\color{red}{f''(a) >0}$ : just start Newton method which will converge to the solution without any overshoot (this is by Darboux theorem). So, $50$% of the problems are solved.
-$\color{red}{f''(a) <0}$ : define a "small" stepsize $\Delta$ and compute $f(a-\phi^n\,\Delta)$ ($\phi$ being the golden ratio) until you find a negative value. When done, the solution is such that $$a-\phi^n\,\Delta<x < a -\phi^{n-1}\,\Delta$$ Select as the starting point the bound for which $f(x)\times f''(x) >0$ and start Newton method.