Ken Ward's Mathematics Pages
Polynomials Horner Scheme Rationale
For an explanation of the Horner Scheme see: Horner Method
Page Contents
Suppose we have a polynomial:
f(x)=anxn+an−1xn−1+an−2xn−2+... + a0 , n=0, 1, 2...n [1.01]
We wish to divide it by a linear polynomial, say x−p, where p is a constant.
We remain silent on the nature of the x's, p's and a's, but they can be any number, real or imaginary. The n's are integers.
Say, we wish to divide [1.01] by x−p, and we proceed using elementary school long division and obtain the following result.
[1.02]
Looking at this pattern we can see that each coefficient of the new function (the quotient) form a pattern. It seems each term is derived from a coefficient of the old function (the numerator) and p times the previous coefficient of this new function. It suggests there may be an easier way to divide one function by a linear function. (Which is, of course, Horner's scheme).
Now let us playfully re-write the above, with the idea of making the pattern clearer. Let:
By comparing them with [1.02], we find:
[1.04]
This makes the pattern clearer. The first coefficient of g(x) is an the first coefficient of f(x) [1.01]. The next coeffient of g(x) is Bn-1
which is the corresponding coefficient of f(x) plus p times the previous
coefficient of f(x). A pattern may become clearer.
We can re-write these terms of g(x) by substituting the B's as appropriate, so we have a recursive formula:
The following table illustrates Horner's scheme using the previous symbols:
Ken Ward's Mathematics Pages
Looking at this pattern we can see that each coefficient of the new function (the quotient) form a pattern. It seems each term is derived from a coefficient of the old function (the numerator) and p times the previous coefficient of this new function. It suggests there may be an easier way to divide one function by a linear function. (Which is, of course, Horner's scheme).
Now let us playfully re-write the above, with the idea of making the pattern clearer. Let:
By comparing them with [1.02], we find:
[1.04]This makes the pattern clearer. The first coefficient of g(x) is an the first coefficient of f(x) [1.01]. The next coeffient of g(x) is B
We can re-write these terms of g(x) by substituting the B's as appropriate, so we have a recursive formula:
The following table illustrates Horner's scheme using the previous symbols:
| an | an-1 | an-2 | |
| p | 0 | pan | p (an-1+pan) |
| an | an-1+pan |
an-2+p (an-1+pan) |
|
| Bn | Bn-1=an-1+pan |
Bn-2=an-2+
pBn-1 |
Ken Ward's Mathematics Pages
Faster Arithmetic - by Ken Ward
Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: