TOPIC: Polynomial root solving PRODUCT: TI-85 A question has been asked about why the polynomial root finder on the TI-85 sometimes returns roots that look "messy" in that perhaps they are off in digits past the middle or have small imaginary parts when the "exact" roots are real. Let's look at a specific example to understand the basic difficulty and then discuss the characteristics of the method used for polynomial roots. For our example let's use: x^5-6x^4+2x^3+36x^2-27x-54. The 85 gives: x1=(-2e0) x2=(3.00004761348e0,8.24750177574e-5) x3=(3.00004761348e0,8.24750177574e-5) x4=(2.99990477304,0) x5=(-1,0) Before going further, lets look at the value of our polynomial around x=3. We want to look about +/- .00015 either side, which includes the range of the roots we are getting for x2, x3 and x4. We can do this easily with the TI-85. y1=x^5-6x^4+2x^3+36x^2-27x-54 y2=log(abs(y1)) Graph y2 in the range: x: 2.99985 to 3.00015 and y: -15 to -5 You notice that this graph is a ragged trace around -11, which means that y1 evaluates to approximately 1e-11 throughout this region. If you move the trace cursor to 3.00005 or to 2.99995, you will see that y2 is undefined because y1 evaluates to zero. You will notice that between these two values there are points fairly uniformly distributed where y1 evaluates to zero. So this is the problem for any process that has to depend on function evaluations to determine zeros - we have a range around the exact root where we have a fairly high probability of hitting an exact zero evaluation anywhere in the range. You will also note that the evaluation is not monotonically decreasing within this range either, so that if a method is trying to determine a "downhill" direction from function evaluations, it will tend to be "trapped" in one of the "valleys" and likely find an exact zero evaluation sooner or later. This effect is due to subtractive cancellation caused by the subtraction of relatively large almost equal values. The width of this erratic region is approximately 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 used on the TI-85. A function evaluation that must be made on the y1 expression above (as opposed to a better conditioned form such as a factored form) cannot reliably detect that the function is not zero throughout this "erratic" range. You may want to compare the evaluation when the equation is written in the factored form: y3=(x+2)(x-3)^3(x+1) y4=log(abs(y3)) Compare the graph of y4 with y2 above. Of course, there are closed form equations for the quadratic, cubic and quartic cases. These equations, if carefully coded, avoid the situation described here, because they do not depend on an evaluation of the entire polynomial. The specific method used on the TI-85 makes serendipitious use of the QR method eigenvalue solver. Given the coefficients of a polynomial, we can easily construct a matrix which will have an equivalent characteristic polynomial. For instance, the polynomial 3x^2-2x+3 has roots that are equivalent to x^2-2/3x+1 which is the characteristic polynomial of the matrix: [[ 2/3 -1 ] 1 0 ]] Since the eigenvalues of a matrix are the roots of its characteristic polynomial, once we have this matrix, we simply compute the eigenvalues and we have our roots. This has the advantage of working for real or complex polynomial coefficients and yields all the roots without complex search heuristics. The method does have the general characteristic that it tends to find its roots at the ends of the erratic region described above. This means that the error in multiple roots gets exaggerated to a sort of worst case. While we can always wish for an algorithm that would always find exactly 3 for the triple root in the example above, this is not possible in general with fixed precision arithmetic. This method normally does behave like the case above though in that it returns multiple roots which lie on a circle in the complex plane centered on the exact root. Therefore, if you suspect a multiple root, you can get a good estimate by averaging all the values for the suspected multiple root. If you want to "confirm" further, you can remove this factor by synthetic division (a simple TI-85 program could be used for this). Once one of the multiple roots is removed, the "erratic region" will be reduced accordingly, allowing the polynomial root finder to give more accurate values each time it is used. While this may look "messy" for a simple integer root of a low order polynomial, the effects we see here are in another sense a reminder of practical problems to be faced with multiple roots of polynomials. The TI-85 could have used special code for closed form solutions to polynomials up to quartic which would have avoided this in those cases only. We opted to use the same method across the board due to the expected use for engineering problems and the fact that this problem has to be recognized for quintics and up anyway. ------------------------------------------------------------------------- TI GRAPHICS TEAM Internet: ti-cares@lobby.ti.com Texas Instruments (Consumer Products) P.O. Box 650311 M/S 3908 Fax: 214-917-7103 Dallas, Texas 75265 ---------------