Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving an Equation Numerically

  1. Dec 4, 2004 #1
    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

    [tex]f(x) = \left\{ \begin{array}{rcl}
    1 & \mbox{for}
    & x \neq a \\ 0 & \mbox{for} & x=a

    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.
    [tex]g(x) = f(\lfloor{x}\rfloor) + (f(\lfloor{x}\rfloor+1)-f(\lfloor{x}\rfloor))(x-\lfloor{x}\rfloor)[/tex]

    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.
    Last edited: Dec 4, 2004
  2. jcsd
  3. Dec 4, 2004 #2


    User Avatar
    Science Advisor
    Gold Member

    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 ?
  4. Dec 4, 2004 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  5. Dec 4, 2004 #4
    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.
  6. Dec 5, 2004 #5
    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 [itex]f(x) \geq 0[/itex], but the function has all sorts of crazy shapes on it, is it impossible for you to find an algorithm which will always work?
  7. Dec 5, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  8. Dec 5, 2004 #7


    User Avatar
    Science Advisor
    Gold Member

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook