Horner Scheme Rationale

# 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 xp, 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 xp, 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 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:

[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 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 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: