gibson:teaching:fall-2016:math753:horner

Horner's method is a simple trick that reduces the number of operations needed to evaluate a polynomial. For example, the 4th order polynomial

would require 4 adds and 10 multiplies, if it were evaulated as written. But if we rewrite as

evaluation only requires 4 adds and 4 multiplies. It's easy to see that these are just two different ways of writing the exact same polynomial. The approach generalizes to arbitrary-order polynomials, and the payoff gets bigger as the order of the polynomial increases.

It's sometime convenient to introduce *base points* to Horner's method. That is, we write a polynomial in this form

The above polynomial is still 4th order, and it is clearly possible to write any polynomial in a form like this for arbitrary 's. The base points require an additional set of subtractions, but it's often worth the trouble, primarily because this is the most natural form for polynomial interpolation via Newton's Divided Differences.

Further reading:

- Horner's method (wikipedia).

Strangely, there aren't many good online resources for Horner's method. Perhaps it's too simple. so

gibson/teaching/fall-2016/math753/horner.txt · Last modified: 2016/11/11 11:37 by gibson