Solving an Equation Numerically

[Manchot]

Hey everyone. I've been looking for a method to find a zero of a certain equation numerically, but I've been having a problem doing so. I guess that I could do some form of transformation on it, but I haven't been successful thus far. Basically, the equation's in the form

f(x) = \left\{ \begin{array}{rcl}<br /> 1 &amp; \mbox{for}<br /> &amp; x \neq a \\ 0 &amp; \mbox{for} &amp; x=a<br /> \end{array}\right.

I'd like to be able to solve for a. Now, I do know the interval that a's in: it's between c and d. We also know that a is a positive integer. Now, one idea I had was able to use the floor function to make an "indentation" in the graph.
g(x) = f(\lfloor{x}\rfloor) + (f(\lfloor{x}\rfloor+1)-f(\lfloor{x}\rfloor))(x-\lfloor{x}\rfloor)

Another idea that I had was to try to "flip" half of the graph around by negating it. I could then use the binary search algorithm. Unfortunately, to know which half to flip, I'd have to use a itself, which I don't know.

Is there any sort of transformation that I can do on the function to get it to "behave" smoothly, and allow me to use Newton's method on it (or any other quick approximation) in a computer? Keep in mind that I can only evaluate the function or its derivative, since I'm using numerical methods. Thanks.

 

[PerennialII]

I'm not sure if I'm getting this right but is it possible to modify the var(s) causing the step - like behavior by replacing them with something like a smoothened-over-interval stepfunction (with continuous derivatives to the required extent) or such a construct ? Then solving numerically for that problem and by modifying the smoothening seeing that it converges to the correct a. Or you've probably thought about something like this already / is prevented by something ?

 

[Integral]

Since a is given in the problem definition, for this to make any sense at all, a must be know by someone or something else (a computer) and you are doing a search to find it. You need directional information like High or low, which is not available for a binary search to work.
What you are given is essentially a mathematical statement of "What number am I thinking" with the only responses being Yes or NO. The only possible systematic search is a sequential one.

Generally speaking the more functional information you use in your root finding routine the quicker the method will converge. Here there is no functional information as to the location of the root. It is a guessing game.

 

[Manchot]

Whoops, you're right. I had basically neutered my function to be information-less. (f wasn't the original one, it was the signum'ed version). Thanks.

 

[Manchot]

I have another question. In general, then, is it impossible to find an algorithm which can find the zero of a function which "bounces" off the x-axis? That is, if f(x) \geq 0, but the function has all sorts of crazy shapes on it, is it impossible for you to find an algorithm which will always work?

 

[matt grime]

For an arbitrary function? No.
For a differentiable one there are numerical ways of finding roots. See eg, Newton raphson. Of course, if the function really is never negative, and it is differentiable, the roots are repeated, and hence local minima too.

 

[PerennialII]

I have another question. In general, then, is it impossible to find an algorithm which can find the zero of a function which "bounces" off the x-axis? That is, if LaTeX graphic is being generated. Reload this page in a moment., but the function has all sorts of crazy shapes on it, is it impossible for you to find an algorithm which will always work?

As above + for some really pathological cases it's possible to try something like arc - length methods + optimization routines to creep through a section and work with local min/max.