UKP said:
I'm kind of unsure whether to go for root finding or approximation to
solve this.
Well, right now we're covering equation solving in my numerical analysis
class, so I'll do my best to answer.
Solving f(x) = y is trivially transformed into g(x) = 0 by setting
g(x)=f(x)-y, so I will assume without loss of generality that you are
trying to find f(x) = 0.
The simplest method is the bisection method. If you know an a and b such
that sgn(f(a)) = -sgn(f(b)) and a<x<b, then you can apply the following
iterative process continuously:
c = (a+b)/2
if f(c)*f(a) > 0; then
a = c
else
b = c
fi
if (a-b)/2 < epsilon then quit
The bisection method, however, cannot find roots such that are local
optima (comparing the derivative will then work in that case).
Given that you know f(x), you can iteratively apply a fixed-point
iteration scheme using Newton's method. Fixed-point iteration transforms
f(x) = 0 to an equation g(x) = x; Newton's method is an analytic way to
find g(x) that makes g'(0) = 0 (and thus converges really quickly if it
actually converges. Convergence not guaranteed).
Newton's method finds g(x) = x - f(x)/f'(x), and then you can
iteratively apply x_{i+1} = g(x_i) until x_i/x_{i+1} < epsilon.
If you need better accuracy or convergence (depends on the problem),
then
http://en.wikipedia.org/wiki/Root-finding_algorithm will be
sufficient to help you (Brent's Method is the most commonly used but
probably the most difficult to write).
P.S. In case you couldn't tell, yes, the root-finding algorithm is the
way to go here.
