[TIB] Re: solver

[Prev][Next][Index][Thread]

[TIB] Re: solver


On Thu, 12 Jun 2003, Ecartis wrote:
> Date: Tue, 10 Jun 2003 22:06:16 -0400
> From: Aaron Sarna <shoofy@rcn.com>
> Subject: [TIB] solver
>
> I know that this doesn't really belong on the Basic mailing list, but
> just out of curiosity, does anyone know how Solver works? Does it just
> do trial and error progressively getting farther from your guess, or is
> there actually some math involved?

You've already gotten some generic answers, but here's some of the "actual
math" you wanted.

BINARY SEARCH
  Get the function F(X) from the user.
  Get a lower bound X1 and an upper bound X2 from the user.
    The zero in which the user is interested should lie somewhere between
    X1 and X2, and the function should be basically increasing or
    decreasing (what mathematicians call "monotonic") between X1 and X2.
  Let X3 = (X1+X2)/2, the X-coordinate right between X1 and X2.
  If sign(F(X1)) != sign(F(X3)), let X2 = X3.  [!= means "not equal to"]
  Otherwise, let X1 = X3.
  Repeat the above three steps over and over until either X1 == X2, or
    F(X1) == 0, or F(X2) == 0.  At that point, either you've found a zero
    or one doesn't exist between the original bounds the user provided.


NEWTON'S METHOD (NEWTON-RAPHSON METHOD)
  Get the function F(X) from the user.
  Also get an initial guess, X0, from the user.  The zero he will get will
    depend on his initial guess.  Usually, the closer the guess the
    better, but this method can get chaotic for certain choices of F(X).
  For this method, the calculator must be able to take derivatives of
    arbitrary functions.  It can do this either by actually performing
    the differentiation as a human would (analyzing the symbols in F(X)),
    or simply by approximating the derivative (F(X1+eps)-F(X1))/(eps) for
    some really small value 'eps'.
  Starting with the user's initial guess X0, perform the following step
    until you reach F(X[n]) == 0:
  X[n+1] = X[n] - F(X[n]) / deriv(F)(X[n]).  [The notation 'deriv(F)(X)'
    means to take the derivative of F(T) at T==X, by one of the methods
    outlined above.]
  The values X[1], X[2], X[3]... should eventually converge on one of the
    zeros of the function.  Once they do, return that value to the user.

Both of these methods can be done pretty quickly in assembler, yes.
They're not too shabby in Basic, though, either. :)

HTH,
-Arthur
Follow-Ups: