[net.math] Polynomial Roots

leimkuhl@uiucdcsp.UUCP (02/18/85)

   Dahlquist & Bjork, NUMERICAL METHODS, has a section (6.8) on
   finding all the roots of an nth degree algebraic equation Pn(x)=0.

   For the 4th degree case, with real roots, one should probably make
   use of the fact that Prod(roots)=a4, the constant coefficient, so
   that if roots r1, r2, and r3 are known, we get r4=a4/r1*r2*r3 which
   is well conditioned.   The problem is that cancellation errors in the
   4th degree formulas can be very seriously magnified.  Working in double
   precision might improve results.

   Actually, it might be best to compute r1,r2,r3,and r4 via the quartic
   formulas and use r1*r2*r3*r4 = a4 as a check.

   The method suggested by Ashby, creating the companion matrix and 
   computing the eigenvalues is quite reasonable and is frequently used,
   due to fast methods for approximating the eigenvalues such as shifted
   QR iteration with reduction to Upper Hessenberg (See Golub&Van Loan,
   MATRIX COMPUTATIONS, for example).  

   However, it is possible that the existence of a direct method 
   for 4th order makes all other techniques inefficient.

   I suspect, though, that if high accuracy is not needed, the fast iterative
   methods are worth trying.