TOPIC: fMin and fMax
PRODUCT:  TI-85 and TI-82
DATE: October 5, 1993

A question has been asked about the algorithms for fMin and fMax on the
TI-82 and TI-85, especially what determines a particular one of several
possible solutions to be returned.

First, fMax simply applies fMin to the opposite of the function.  So
in the following discussion, what is said about fMin also applies to
fMax.  The algorithm basically begins with the two end points of the
range bounding the function, samples two points between these end
points and based on the four values moves in one of the end points to
reduce the interval.  This process continues until the interval
is reduced to approximately "tol" but not less than about
1E-7 * abs(x) for reasons discussed below.  A parabolic interpolation
is used on some iterations to speed up the method, but that is not
central to understanding the global behavior.  The method is well
known and rather than describe it here in detail, we refer you to the
references below.	It is called a golden section search and is
closely related to a Fibonacci search.

The following comments apply to using the function on the TI-85.

1. Conceptually, golden section search treats the function within
its bounds as "unimodal", ie one in which the function strictly
decreases for values approaching the minimum from the left and
strictly increases for values leaving the minimum to the right.
It only samples a finite number of points and does not use any
slope or derivative information.  In practice, this means that
any local minimum will satisfy it and if the function has several
local minima within the bounds, the one it converges on will not
be particularly "intuitive", especially since the sampling points
are on either side of the midpoint of the interval at each
iteration (about 38.2% and 61.8% of the interval).

2. Keep in mind that if a function is decreasing as it passes
through the bounds (either to the left or right), it qualifies
to the algorithm as a local minimum, because the algorithm only
deals with the function within the bounds.

3. The accuracy of a minimum determined just from function
evaluations is limited to about one-half the calculator digits
simply because the function is "flat" at the minimum.  You can
see this qualitatively when you zoom in on a minimum until the
function graphs completely within one pixel on the y-axis for
the many pixels along the x-axis.	We can further understand
this from the Taylor series for F(x+e), where e is small.

F(x+e) = F(x) + eF'(x) + e^2 (F''(x) / 2) + ...

At a minimum, F'(x) = 0, so the second term vanishes.  F''(x)/2
will be approximately constant, so we see that as we move from
the exact minimum by an amount e, the function evaluation will
be approximately F(xmin) + k e^2 .  When e is less than 1E-7,
e^2 will be less than 1E-14 and at about this point will make the
second term negligible for the addition.  This is the reason that
results from fMin sometimes look like they have "garbage" digits
in the last six digits or so.

From the above Taylor series, we can also see that if we are finding
a root (ie F'(x) is not zero), F(x+e) varies linearly with e.  So
numerically, the TI-85 can compute a minimum to about full
precision if you find a root on the derivative computed with der1,
but only half that precision with fMin.

4. For the reason above, "tol" on the TI-85 should be about 1E-7 when
using fMin or fMax.  The default value for tol of 1E-5 will give
slightly less accuracy, while values smaller than 1E-7 will generally
not provide any accuracy increase.  Large values of tol are usually
to be avoided when using fMin and fMax.

5. On the TI-85, fMin and fMax do not use a guess.  When used
interactively from the graph screen, the trace cursor can be moved
prior to executing fMin/fMax, but this has no effect on the result.
For best behavior, these functions should be bounded by "lower" and
"upper" to the region you want.  The use of a guess was incorporated
on the TI-82.  On the TI-82, the algorithm is still satisfied by a
local minimum, but will not return a result greater than the
function value at the guess, so some additional control is gained.

6. One way to observe this algorithm is to plot the result of fMin.
For example if y1=sin 3x + sin 7x, then y2=fMin(y1,x,x-24dx,x+24dx),
where dx is the delta x value from the range vars menu, will plot
the result of moving a 48 pixel wide window (for bounds) over the
function.	In this case, having a tol of about one-half dx can
increase the graphing speed significantly, with no loss of accuracy
for the graph.

References:

"Numerical Recipes, the Art of Scientific Computing", Willian H.
Press, Brian P. Flannery, Saul A. Teukolsky and William T. Vetterling,
Cambridge University Press, 1988, 1992, Chapter 10.

"Numerical Methods and Software", David Kahaner, Cleve Moler and
Stephen Nash, Prentice Hall, 1989, Chapter 9.

 ---------------------------------------------------------------------------
  TI GRAPHIC PRODUCTS TEAM
  Texas Instruments (Consumer Products)
  P.O. Box 650311  M/S 3908		  Internet: ti-cares@lobby.ti.com
  Dallas, Texas  75265			  Fax: 214-917-7103
---------------------------------------------------------------------------