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:
P(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0}
or in the ascending order of the exponents:
P(x) = a_{0} + a_{1}x + ... + a_{n-1}x^{n-1} + a_{n}x^{n}.
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}:
(1) | b_{k} = t·b_{k+1} + a_{k}, |
k = n - 1, n - 2, ..., 1, 0 and b_{n} = a_{n}, with b_{0} = P(t). This follows from a special form of the polynomial
P(x) = ( ... (a_{n}x + a_{n-1}) x + ... + a_{1}) x + a_{0}
in the descending order of the exponents or in the ascending order as in
P(x) = a_{0} + x (a_{1} + x (a_{2} + x (... + x (a_{n-1} + x a_{n}) ... ).
For example, the polynomial P(x) = 2x^{4} - 3x^{3} + x + 7 can be written as
P(x) = (((2x - 3) x + 0) x + 1) x + 7,
or else as
P(x) = 7 + x (1 + x (0 + x (-3 + x·2))).
According to (1), say P(2) comes out as the last term in the sequence
b_{4} | = a_{4} | = 2 |
b_{3} | = 2·b_{4} + a_{3} | = 1 |
b_{2} | = 2·b_{3} + a_{2} | = 2 |
b_{1} | = 2·b_{2} + a_{1} | = 5 |
b_{0} | = 2·b_{1} + a_{0} | = 17 |
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
The other terms in the last row also come in handy. By direct verification one can check that
P(x) = 2x^{4} - 3x^{3} + x + 7 = (x - 2)(2x^{3} + x^{2} + 2x + 5) + 17.
So the coefficients b in the last row comprise both the quotient of the division of P(x) by
Note also that P(x) = (x - 2)Q(x) + 17 implies
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.)
What if applet does not run? |
Let's now see what additional use can be made of the quantity Q(t) in
(2) | P(x) = (x - t)Q(x) + r, |
where Q(x) is the quotient of
P'(x) | = [(x - t)Q(x) + r]' |
= (x - t)'Q(x) + (x - t)Q'(x) | |
= Q(x) + (x - t)Q'(x). |
It follows that
P'(t) | = Q(t) + (t - t)Q'(t) |
= Q(t). |
Using the example of P(x) = 2x^{4} - 3x^{3} + x + 7, we see that, in addition to
References
- K. Atkinson, Elementary Numerical Analysis, John Wiley & Sons, 1985
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71531985