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