User Tools

Site Tools


gibson:teaching:fall-2016:math753:horner

Horner's method for polynomial evaluation

Horner's method without base points

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

\begin{equation*}
P(x) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + c_4 x^4
\end{equation*}

would require 4 adds and 10 multiplies, if it were evaulated as written. But if we rewrite $P(x)$ as

\begin{equation*}
P(x) = c_0 + x \, [c_1 + x \, [c_2 + x \, [c_3 + x \, c_4]]]
\end{equation*}

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.

Horner's method with base points

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

\begin{equation*}
P(x) = c_0 + (x - b_0) \, [c_1 + (x - b_1) [c_2 + (x - b_2) [c_3 + (x - b_3) \, c_4]]]
\end{equation*}

The above polynomial is still 4th order, and it is clearly possible to write any polynomial in a form like this for arbitrary $b$'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:

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