[TIB] Re: solver
[Prev][Next][Index][Thread]
[TIB] Re: solver
My idea was much like the binary search method if you disassemble much of my
rambling. Main thing is look for sign changes, of course there can be ways
to trick it, if all 3 sections contain the same sign within the constraints
of the domain and the mean.
----- Original Message -----
From: "Arthur J. O'Dwyer" <ajo@andrew.cmu.edu>
To: <ti-basic@lists.ticalc.org>
Sent: Thursday, June 12, 2003 9:20 AM
Subject: [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
>
>
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.488 / Virus Database: 287 - Release Date: 6/5/2003
References: