Horner's Method

Horner's method (also Horner Algorithm and Horner Scheme) is an efficient way of evaluating polynomials and their derivatives at a given point. It is also used for a compact presentation of the long division of a polynomial by a linear polynomial. The method is named after the British mathematician William George Horner (1786 – 1837).

A polynomial P(x) can be written in the descending order of the powers of x:

or in the ascending order of the exponents:

The Horner scheme computes the value P(t) of the polynomial P at x = t as the sequence of steps starting with the leading coefficient a_n:

According to (1), say P(2) comes out as the last term in the sequence

These calculations are conveniently arranged into a table

or, in the ascending order, with calculations carried right to left,

where the first row lists the coefficients of the polynomial, the third row the sequence of computed b_i's. The auxiliary quantities 2·b_i's are placed diagonally from b_i's and under the a_i-1 they are summed with according to (1). Thus we see that P(2) = 17, the last of the b's.

The other terms in the last row also come in handy. By direct verification one can check that

So the coefficients b in the last row comprise both the quotient of the division of P(x) by (x - 2), viz. Q(x) = 2x³ + x² + 2x + 5, and the remainder 17. In fact if you carry out the multiplication (x - 2)Q(x) and observe the manner in which the like powers of x combine, you could not help but notice an additional justification for the algorithm (1).

Note also that P(x) = (x - 2)Q(x) + 17 implies P(2) = 17. This follows by substitution P(2) = (2 - 2)Q(2) + 17 and holds true regardless of the value Q(2). However the latter is also a meaningful quantity as we shall see shortly.

The applet below helps finding more examples of the workings of the Horner scheme. All blue numbers (the coefficients of P, the highest power of x and the specific value of x in the third line are clickable. Click on both sides of their vertical midline to see how they change.)

where Q(x) is the quotient of P(x) / ( x - t) and r is the remainder. Both appear in the third row of the Horner scheme. This material is intended for the beginning Calculus students. Let's differentiate (2). By the product rule,

It follows that

Using the example of P(x) = 2x⁴ - 3x³ + x + 7, we see that, in addition to P(2) = 17, we can obtain P'(2) by computing the quotient Q(x) = 2x³ + x² + 2x + 5 for x = 2, for P'(2) = Q(2). This calls for appending additional two rows two the Horner table to allow computing of Q(2) with the help of the Horner scheme.

References

1. K. Atkinson, Elementary Numerical Analysis, John Wiley & Sons, 1985

Copyright © 1996-2009 Alexander Bogomolny