We encounter frequently polynomials. Therefore it would be nice to find an efficient algorithm for their evaluation. You might think that this is a trivial matter, but I will show you that there are several possibilities, one of which is more economical than the others. Consider the polynomial
I. If we compute each power xk by itself and multiply it by ak, we execute
multiplications and n additions.
II. If we produce the powers successively and multiply at each level by the corresponding ak, we have 2n multiplications and n additions.
III. However, if we rewrite the polynomial in the form
,
we have only n multiplications and additions! Horner's scheme is the most economical method for the evaluation of polynomials which you should always apply in your work when evaluating polynomials. It is readily used on a calculator, as you will easily convince yourself:
Compute for the value x = X
,
and see immediately that bn=P(x).
Evaluate for x = -2,-1,0,1,2 the polynomial
Consider once more the polynomial
In Horner's scheme, we formed for x = X the coefficients b0=a0,bj= aj+bj-1´ X, j = 1,2, ,n. This operation yielded bn=y(X). However, the coefficients bjare the coefficients in the polynomial
,
obtained by division of y(X) by (x - X), so that
.
Obviously, y(X) = bn. Multiplying out the last equation and collecting the coefficients of powers of x, we obtain Horner's scheme. Moreover, we can repeat the operations of this scheme on the bj, j=0,1,,n-1 in order to obtain C(x), D(x), until there is only one number left. Then bn, cn-1, dn-2, . . . are the coefficients in P(x) after setting x = z + X. However, that is the same thing as using the Taylor series to expand P(x) about the point X, so that the coefficients bn, cn-1, dn-2, . . . are the Taylor coefficients at the point X:
