Solution 10410: Algorithm for the Solver Function on the TI-85 and TI-86.
What algorithm is used for the Solver on the TI-85 and TI-86?
The TI-85 root finder or solver is a purely numeric method for finding zeros of a function. It does not use any information other than function evaluations in its search for a root. The basic concept is to work between two "end points" and draw a secant line through them, projecting this line to its intersection with the x-axis. If the intersection is between these end points, the function value there is used to determine how to reduce the x-range while maintaining a sign change (if it exists) or following lower function values. If the secant intersection is out of bounds or will not reduce the x-range as much as bisection, then the x-range is bisected instead. This continues until the x-range has been reduced to a very small range.
For example y1 = 3x^3 - 2x^2 - 13x - 8 in the viewing rectangle of [-5,5] by [-30,15], the function returns the root at x = 8/3, even when the cursor is pointed to the root at x = -1.
Prior to getting into the routine described above, the solver attempts through some heuristics to get two "good" end points to start with. The guess provided is one of these, the other depends on a lot of factors, but the solver prefers a sign change if it can find it. The calculator spends some time "going downhill" in the neighborhood of the even multiple root at -1, then "sees" the function begin increasing. It then checks the function values at the bounds, continuing to try to find a sign change. It finds one at the right bound and then begins the routine above using the guess and the right hand bound as the end points.
Because an even multiple root doesn't have a sign change, the solver must be "forced" into doing the bisections needed to reduce the range around this "minimum" that (to it) may or may not be a root. In fact, for the calculator to call this a root, it requires a function evaluation of opposite sign or exactly zero. For this equation, in exact arithmetic we should not get a change of sign in the neighborhood of -1 and we may not be likely to evaluate the function at -1 exactly. But due to round off error, we may (and usually do) get either a function evaluation of either exactly zero for an argument other than -1 or a function evaluation of opposite sign (positive in this case).
Subtractive cancellation can be observed; which is a fact of life for fixed precision arithmetic in evaluating polynomials at multiple roots. Plot the equation
y2=sign(y1)*abs log y1 in the window [-1.000001 -.999999] by [-18 15]. (Set the graph format to DrawDot).
Observe near the outside of this range, the function evaluates to about -1E-11 (-11 on the graph). Close to x=-1 in the center, the function evaluates to about -3E-13 (-12.5 on the graph). However, in the range of about +/- 2E-7 either side of x=-1, the function evaluation becomes erratic, with exact zero evaluations where pixels are blank and evaluations with positive sign at the top of the graph. The width of this erratic region can be roughly predicted by the formula:
2*R*10^-(14/M) where R is the value of the root and M is the multiplicity of the root. The 14 represents the 14 digit arithmetic of the TI-85.
This is one of the fundamental reasons why it is numerically difficult to compute multiple roots of polynomials accurately.