For an explanation of the Horner Scheme see:
Horner Method
Page Contents
Suppose we have a polynomial: f(x)=a_{n}x^{n}+a_{n−1}x^{n−1}+a_{n−2}x^{n−2}+...
+ a_{0 }, 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:
[1.03]
Where g(x) is our quotient, [1.01] divided by x−p,
and the B's are the coefficients of our new equation.
By comparing them
with [1.02], we find:
[1.04]
This makes the pattern clearer. The first coefficient of g(x) is a_{n}
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:
[105]
This shows that each term of the function g(x) is composed of the corresponding
term in f(x) plus p times the previous term in g(x). So, if we know the previus
coefficient in g(x), then we can, successively, compute all of its coefficients. We do
know the previous term in g(x), so we can systematically compute all the terms
in g(x). We know the first coefficient of g(x) is a_{n} so we can get
the second term by taking a_{n-1} and adding p times the previous
coefficient of f(x), a_{n}, and following the same rule, compute all the
coefficients. The following table illustrates Horner's scheme using the
previous symbols:
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: