1
$\begingroup$

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

  1. 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
  2. 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.
  3. 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.

$\endgroup$
2
  • $\begingroup$ Your first method sounds good for finding everything you're looking for (extrema and inflection points included). I'd think that, if you're using Newton for the second method, you might be opening up opportunities for it to go haywire--say, if an extremum exists but there are no nearby roots. There is something unsatisfying about brute force, but as long as you're not looking at something like $\sin(1/x)$, it should find everything you're looking for, even with a relatively coarse resolution. $\endgroup$
    – dmk
    May 16, 2014 at 1:51
  • $\begingroup$ @dmk If there is an extremum with no roots, it will return saying that the answer was not accurate or within the given tolerance range. $\endgroup$
    – scrblnrd3
    May 16, 2014 at 13:47

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .