# Numerical solution w/o derivative

• Oct 30th 2007, 05:13 PM
Optiminimal
Numerical solution w/o derivative
I know the function y = f(x).

I have observed the true y-value and want to find the x that it implies.

It is impossible to invert the function, i.e. to analytically solve for x=g(y).

The derivative of the function is unavailable, so I cannot use the Newton-Raphson method.

It isn't difficult to come up with a way of trial and error which work. But I want to check with you if there is some intelligent way to deal with such iterations in order to make the procedure reasonably efficient?

While it is possible to formulate the derivative of y=f(x), it is impractical to use it because it is a formula which fills an entire page! (According to Mathematica) I need to implement a way to solve this problem in c++.
• Oct 30th 2007, 07:28 PM
ThePerfectHacker
You can use the bisection method it does not require derivatives and works fast.
• Oct 31st 2007, 10:45 AM
Optiminimal
Thanks! That's a pretty intuitive solution.

Of course, the catch is that one has to find one point on each side of the solution before one can proceed like that.

I have now looked at the derivative (which is too extensive to use in the real time code where I need to solve this problem). I see that the derivative of the function obviously is negative but increasing in the interval of interest, under all reasonably expected parameter values.

Based on this, I'm thinking about using linear extrapolation like this:

If the two first guesses x=a and x=b both yield too high y-values, then I would consider a straight line through those two points a and b and choose the third guess x=c on that same line. I would choose x=c so that it would be right on target if y(x) was a straight line from y(a) to y(c). Because the derivative of y(x) is increasing and negative, then I suppose that y(c) must give a solution which is too low. From there on I would be able to use the bisection method with b and c.
• Oct 31st 2007, 04:47 PM
Optiminimal
No, my thinking above was wrong. I cannot choose an x-value which surely gives me a y-value "on the other side" of the observed y-value. Not by only knowing that the first derivative is negative and the second derivative is positive.

I must use more specific expectations about the slope of y=f(x) in order to do that.