EXPLANATION FILE OF PROGRAM ROOT4
                        =================================


  The program root4 calculates the real or complex roots of a polynomial of degree two, 
  three or four.

  1. Numerical Methods
     -----------------

     1.1  Case 2nd degree: x^2 + bx + c = 0   (1)

          The real roots depend on the sign of q = sqrt(b*b-4*c).

          a) q >= 0: two real roots exist:

             x1 = -b/2 - sqrt(q)/2

             x2 = -b/2 + sqrt(q)/2

          b) q < 0: two complex roots exist:

             x1 = -b/2 - i * sqrt(-q)/2

             x2 = -b/2 + i * sqrt(-q)/2

     1.2  Case 3rd degree: x^3 + a2 x^2 + a1 x + a0 = 0   (2)

          Let be lambda the greatest absolute value of a  coefficients.
                                                        i
          It is known that:

          a) if a0 > 0, one real negative root exists in interval [-(1+lambda), 0].

          b) if a0 < 0, one real positive root exists in interval [0, (1+lambda)].

          First, we calculate this real root x1  by the bisector method.

          Then we divide equation (2) by (x - x1 ), the other two roots are solutions
          
          of quadratic equation:

             x^2 + (a2 + x1) x + (a1 + (a2 + x1) x1) = 0   (3)

          that can be easily solved.

     1.3 Case 4th degree: x^4 + a x^3 + b x^2 + c x + d = 0   (4)

         Let us put x = y - a/4, then equation (4) can be transformed into a product
         of two quadratic equations (2nd degree):

            (y^2 + 2ky + l)(y^2 - 2ky + m) = 0   (5)

         where:  l + m -4k^2 = q      (q = b - 3a^2/8)

                 2k (m - 1)  = r      (r=c-(ab/2)+(a^3/8) )               (6)

                 lm = s               (s=d-(ac/4)+(a^2b/16)-(3a^4/256) )


                 k^2 = z is a real root of cubic equation:

                 z^3 + alpha z^2 + beta z + gamma = 0                     (7)

                 with   alpha = q/2, beta = (q^2-4s)/16, gamma = -r^2/64

         So the method consists in:

            a) solving equation (7) as shown in § 1.2

            b) solving linear system (6) to find l and m

            c) solving the two equations (5) to find the four roots of (4).

              
  2. Programming Technique
     ---------------------

     We define a vector R of size 4 to store roots and a matrix A of size (4,4)

     to store the coefficients of equation of degree N:

                  i=N
                  Sum A(N, i) x^i = 0    (N=2,3,4)
                  i=0

     In the Quick Basic program, subroutine 1000 is the main search root driver,

     subroutine 2000 solves equation x^3 + A(3,2) x^2 + A(3,1) x + A(3,0) = 0,

     subroutine 3000 solves equation x^2 + A(2,1) x + A(2,0) = 0 .


     Except the bisector method (not explained here), the program is linear.

     However, please note the different ways to solve the linear system (6):


            a) if gamma <> 0, then k^2 <> 0 and (6) can be solved by:

                  l + m = q + 4 k^2
                                       (8)
                  l - m = r / 2k

            b) if gamma = 0, then k=0 is a solution of (7)

               1) if q^2 - 4s >= 0, we have:  l + m = q and lm = s

                  id est  l + m = q and l - m = sqrt(q^2 - 4s)

                  easily solved.

               2) if q^2 - 4s < 0, the above method does not work. However,

                  in that case, equation(7) is reduced to z^2 + alpha z + beta =0

                  and has two real roots (because beta < 0) with opposite signs.

                  We then choose the positive root and can use (8) to calculate

                  l and m.

  -------------------------------------------------------------

  End of file root4.txt