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
Say, we wish to divide [1.01] by x−p,
and we proceed using elementary school long division and obtain the following
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:
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:
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
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 an so we can get
the second term by taking an-1 and adding p times the previous
coefficient of f(x), an, and following the same rule, compute all the
coefficients. The following table illustrates Horner's scheme using the