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) = anxn + an-1xn-1 + ... + a1x + a0
or in the ascending order of the exponents:
P(x) = a0 + a1x + ... + an-1xn-1 + anxn.
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 an:
(1) | bk = t·bk+1 + ak, |
k = n - 1, n - 2, ..., 1, 0 and bn = an, with b0 = P(t). This follows from a special form of the polynomial
P(x) = ( ... (anx + an-1) x + ... + a1) x + a0
in the descending order of the exponents or in the ascending order as in
P(x) = a0 + x (a1 + x (a2 + x (... + x (an-1 + x an) ... ).
For example, the polynomial P(x) = 2x4 - 3x3 + 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
b4 | = a4 | = 2 |
b3 | = 2·b4 + a3 | = 1 |
b2 | = 2·b3 + a2 | = 2 |
b1 | = 2·b2 + a1 | = 5 |
b0 | = 2·b1 + a0 | = 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 bi's. The auxiliary quantities 2·bi's are placed diagonally from bi's and under the ai-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) = 2x4 - 3x3 + x + 7 = (x - 2)(2x3 + x2 + 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) = 2x4 - 3x3 + 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
72022613