I'm writing a program for my AP Calculus class, and I'm trying to write an equation solver that approximates the zeros of functions. Right now it can take symbolic derivatives and evaluate functions. The plan is that, given a function and an interval, it will tell you the points of inflection, critical points, zeroes, and such on that interval. I have written the solver using Newton's method, which relies on a decent first approximation. Getting that approximation is easy for a human, but I'm not sure how to tackle it in a program.
I have considered the following ideas
- Brute force an approximation by splitting the interval into $n$ subintervals, and checking whether the sign of the function changes on that interval, then using the midpoints of those as a guess
- Split it into some $n$ subintervals again, but instead of checking whether the sign changes, check whether the sign of the first derivative changes, and use points to the left and right of the mins and maxes to find zeroes, if they exist.
- Find the first zero by using the endpoints as initial guesses, and then moving the guesses to the left or right
The problem I see with the first method is that if you have a function like $f(x)=(x+2)^2$, it won't catch the zero since the sign of $f(x)$ is always positive
All of these seem pretty brute-forcey, so I was wondering if there was a way to definitively find rough approximations of zeros of functions to use to find more accurate approximations using Newton's method.
In sufficient generality, this is an unsolvable problem. However, you might do something like this. Suppose you can get an upper bound $|f'(x)| \le C$ for all $x$ in the interval $[a,b]$ in question. Then if $f(t) \ne 0$ you know there is no zero $x$ with $|x - t| < |f(t)|/C$. Doing this for $n$ evenly spaced points in your interval will hopefully rule out most of the interval as possible locations for zeros (if it doesn't, try a larger $n$), and then you can try initial points in what remains for your Newton iteration.