EXPLANATION FILE OF PROGRAM HORNER
                   ==================================


  Shifting the Expansion Point with Horner's Rule
  -----------------------------------------------

    The most difficult source of inaccuracy that must be dealt with in numerical 
  analysis is round-off error. ln many cases, it is unavoidable. However, it is
  often possible to restructure the calculation to minimize the influence of
  round-off error. In this subsection, we will examine how this can be accom-
  plished for some polynomial calculations. 

    Consider the following quartic polynomial: 

                               2      3    4
             y(x) = 1 + 4x + 6x  + 4 x  + x

  If this polynomial appeared within a calculation and were to be evaluated near
  x=-1, there is a strong possibility that round-off error would seriously
  affect the accuracy of the computation. The reason for this is that ideally
  y(-1) = 1 - 4 + 6 + 4 + 1 = O. However, numerically the result would be E,
  and the relative error would be infinite. If y(x) is a multiplier in an analy-
  sis, the results can be useless. 

    If it were known beforehand that the calculations would involve x values in
  the vicinity of -1, y(x) could be replaced with a better conditioned form: 

                           4
             y(x) = (x + 1) 

  Now if there is round-off errer, its influence is mu ch reduced.
   
    What we have done in the above example is to shift the expansion point so
  that 

                              2                                 2
         y(x) = a  + a x + a x  + ... = b  + b (x-x ) + b (x-x )  + ...  (2.6.5)
                 0    1     2            0    1    0     2    0

  The problem is therefore one of determining the coefficients b. (i = 0, 1,
  ... ). To solve for the bi coefficients in terms of the ai and xo values, we
  again equate like powers:
                             2
	 a  = b  - b x + b  x  - ...
          0    0    1 0   2  0
          	                2
	 a  = b  - 2b x  + 3b  x  - ...		. 
          1    1     2 0     3  0

  and so on. For an Nth-degree polynomial, there are N + 1 equations in the
  N + 1 unknowns (bo, b1, ... , bn), and the problem is, in principle, soluble.
   
    Homer developed an algorithm for quartic polynomials that is relatively
  simple. We will start with the definition 

          -1
         b   = a     for n = 0, 1, 2, 3, 4
          n     n
                                                  m
  Next, for m = 0, 1, 2, 3, 4 we will calcula te b :
                                                  0
          m     m-1
         b  = b
          0     0

          m       m      m-1   
         b  = x  b    + b        for n = 1, 2, 3, 4 - m
          n    0  n-1    n

  Finally,
                 4-m
         b    = b                for m = 0, 1, 2, 3, 4
          m      m

  This algorithm can be generalized for polynomials beyond the quartic, but for
  the purposes of this discussion, we willlimit ourselves to the quartic case. 


  A subroutine for applying Horner's algorithm is given in program Horner.

  This program is easy to use and requires no special precautions. As a simple
  exercise, extend HORNER to polynomials of a higher degree than the quartic.

From [BIBLI 01].
-------------------------------------------------------
End of file horner.txt